歐拉項目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.

最小修復：除了值之外，還跟蹤字符串。