欧拉项目413

Question

我想解决Project Euler's 413rd问题，我想欧勒试图给我造成巨大的影响。 说实话，这个问题似乎并不复杂，至少如果有人应用暴力。

但是，虽然我的F函数当参数是'10'时返回右边的'9'，但是当N = 10^3时它返回 ...对于基督的缘故，这是问题的索引。

还有其他人面临同样的问题吗？ F（10^3）也许是相同的数字？我不寻求数值解。

谢谢！

Answer 1

的时间来解决使用蛮力（或为什么你的方法是行不通的）：

每使用10个操作需要 10^19 * 10 = 10^20次。

如果你有3GHz的proc和10个核心，可以做到每个核心一个操作就需要

10^20 /（3 * 10^9 * 10）秒来解决。

大约是100年。

我可以证实测试用例正确

Answer 2

我得到了413的时候我isOneChild（n）函数递归删除数字，并在每一层检查。我得到了正确的答案，389。当我改变它索引到每个子字符串。

当前导0时，您的解决方案不能正确分支。例如，“00”应该分支到“0”和“0”，产生2的计数，但是你的解决方案只能到“0”，产生1的计数。同样，“01”只分支到“1” ，错误地产生计数为0.

最小修复：除了值之外，还跟踪字符串。