3

在 Project Euler 中，一个问题要求我编写一个程序来从谐波序列中找到 20 项的收敛值：

1/111, 1/222, 1/333, 1/444, 1/555, 1/666, 1/777, 1/888, 1/999, 1/1000, 1/1110, 1/1111, 1/1112, 1/1113, 1/1114, 1/1115, 1/1116, 1/1117, 1/1118, and 1/1119

我想自己编写程序来解决问题，但是，没有处理过 Calc II，我不得不阅读 Divergence/Convergence。所有解释都涉及可以用公式表示的系列。这个系列，据我所知，不能。

所以，问题是：

是否有一个公式来表示这个系列，或者有没有一种方法可以在没有公式的情况下找到这个系列的收敛性？

4

3 回答 3

9

以防万一有人认为暴力破解它：

与大多数高数量的 Project Euler 问题一样，这里的蛮力方法不会在合理的时间内完成。

假设您的计算机每秒可以处理 10 9 个数字（实际上它可以处理的数字要少得多）。将高达 10 n的有效术语相加n > 9大约需要 10 n-9秒。

你需要走多远才能确定小数点后十位的总和？

远远不够，所有较大的有效条款的总和小于 10 -10。10 12够远吗？不，考虑接下来的一千个数字

1001001001001

其中无效数字是

1001001001110
1001001001111
1001001001112
...
1001001001119
1001001001222
1001001001333
1001001001444
...
1001001001999
1001001002000

这些是 19，所以有 981 个有效数字，相应的总和大于 981/1001001002000，大于 9*10 -10。沿着这些思路进行一些进一步的推理表明，您必须暴力破解远高于 10 15 ——事实上，在剩余有效项的总和小于 10 -10之前，您必须超过 10 2000。

在宇宙之初开始的蛮力甚至还远未接近可靠的答案。

于 2012-01-26T23:37:01.663 回答
0

如果你仔细阅读这个问题，你会发现实际上有一个公式。您正在处理的序列是谐波序列，其中已删除具有 3 个或更多相等连续数字的项。这里的蛮力方法是将谐波级数的所有项求和，省略指定的项，直到达到所需的精度。Ruby 及其Rational类似乎是很好的候选者。

于 2012-01-26T20:53:04.590 回答
0

这个问题的天真和蛮力方法是编写一个循环迭代系列的分母，并将分母的倒数添加到总和，因为它没有被问题描述中所述的限制排除在外。

大纲将与此类似：

for i in (1..1200)
  if is_valid(i) then
    sum += 1.0 / i
  end
end

def is_valid(_i)
  # implement the check here. hint: use modulo operator ;-)
end
于 2012-01-26T20:59:32.727 回答