Eratosthenes筛是动态编程的一个例子吗？ [英] Is the Sieve of Eratosthenes an example of Dynamic Programming?

问题描述

对于Eratosthenes筛（用所有数字组成的数组和标记复合数字的循环实现）是否是动态编程的示例，我有点困惑？有几个朋友告诉我它的实现方式是Bottom Up DP的一个示例，但我很难看到它。究竟是什么子问题，您将如何使用自顶向下/递归实现SoE？谢谢大家。

I'm a bit confused as to whether the Sieve of Eratosthenes (implemented with an array for all the numbers and a loop marking the composite numbers) is an example of Dynamic Programming? A couple of friends were telling me the way it's implemented is an example of Bottom Up DP, but I'm having trouble seeing it. Exactly what are the subproblems and how would you implement SoE with Top-Down / Recursion? Thanks guys.

推荐答案

当然，我们可以将Eratosthenes筛作为动态编程的示例。子问题将是所有组合数字。跳过标记的数字是子问题重叠的完美展示，因为如果它们不重叠，我们就不会跳过它们：）

Sure, we could think of the Sieve of Eratosthenes as an example of dynamic programming. The subproblems would be all the composite numbers. Skipping over marked numbers is a perfect demonstration of the subproblems overlapping since if they did not overlap we wouldn't be skipping over them :)

我们可以制定筛子的一种方法递归可以是：让 f（N）表示第 N 个素数及其相关的筛状态。然后：

One way we could formulate the sieve recursively could be: let f(N) represent the Nth prime and its associated sieve state. Then:

f(1) = (2, [4,6...])
f(N) = (q, join( Sieve, [q+q,q+q+q...]))
  '''a pair, of the next number q above p 
  _not_ in Sieve, and the Sieve with 
  all the multiples of this number q
  added into it (we'll place an upper
  bound on this process, practically)'''
    where (p, Sieve) = f(N - 1)
          q = next_not_in(p, Sieve)

让我们测试：

f(3) = 
    call f(2) =
        call f(1) =
        <-- return (2, [4,6...])
    <-- return (3, [4,6,8,9...])
<-- return (5, [4,6,8,9,10...])

这篇关于Eratosthenes筛是动态编程的一个例子吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！