2015年9月 的存档

素数求和的动态规划方法

2015年9月29日 没有评论

怎么求出从 $2$ 到 $N$ 之间的所有素数之和?

素数求和是数论中一个很典型的问题。这事情乍听起来并不难,只要把素数都求出来再加起来就好了嘛。可能你已经了解了一些求素数的方法,比如最简单的试除。写过这个程序的同学都知道这样搞有多慢。或者常用的是埃氏筛法,简单来说,就是列好从 $2$ 到 $N$ 的范围,先用 $2$ 去筛,把从 $2 \times 2$ 开始的 2 的倍数剔掉;再用下一个素数 3 筛,把 $3 \times 3$ 开始的 3 的倍数剔除掉…… 一直筛完不大于 $\sqrt{N}$ 所有素数为止。我直接从 wiki 上借了一个动画来演示这个过程,有兴趣的同学可以自己写一个试试看。

Sieve_of_Eratosthenes_animation

本文中的方法来自于解决了 ProjectEuler 全部问题的大神 Lucy_Hedgehog。
阅读全文…

0-1 背包问题详解 (4)

2015年9月7日 没有评论

前面的方法已经非常快了,应该说很满意。那还有没有再优化的余地呢?

我们再来仔细看一下这个过程:深度优先搜索,逐级回溯,典型的二叉树遍历方式。为了方便说明,我标出了结点遍历的顺序:
knapsack_tiny_arrow
阅读全文…