歐拉項目＃8：是否有比蠻力計算更高效的算法？

Question

問題

有沒有更好的方式來尋找項目歐拉問題8，這是Find the greatest product of five consecutive digits in the 1000-digit number的解決方案，比蠻力方法。

我計算了所有可能的產品並選擇了最大的 - 強力算法。

有沒有更高效的算法？或者是蠻力方法的唯一方法。

旁註

• 這不是一門功課的問題。
• 我不要求用於將結果問題8.

Answer 1

由於議題要求連續數字，「蠻力」是指爲O（n）在這種情況下，Ñ作爲數字位數（1000）。只要數字中沒有某種模式，您只需要n步驟即可掃描數字，所以這是最快的解決方案。

您可以緩存最後4位數字的產品或執行類似的技巧，但絕對不會比O（n）更好。

Answer 2

您可以使用大小爲5的滑動窗口並在O(d)中解決此問題，其中d是輸入數字中的位數。

您可以通過窗口中起始編號的索引來表示窗口，並且窗口i的值是索引爲[i，i + 4]的元素的乘積。現在，在每次迭代中，將窗口向右滑動，有效地放下最左邊的元素並在右側添加新元素，並且窗口的新值爲old_value/left_most_ele * new_right_ele。繼續爲範圍[0,d-5]中的每個索引i執行此操作，並查找最大窗口值。

請注意，嵌套循環的內部循環運行五次的蠻力方法也是一個解決方案。但是上面的方法稍好一些，因爲我們在每個步驟中不做五次乘法，而是執行一次乘法和一次除法。

Answer 3

是的，沒有。您必須查看每個連續五位數字的序列，但是您不必每次都通過循環乘以每一個這樣的序列。有可以加快處理的捷徑。例如，如果下一個數字是0，則可以跳過。另外，如果下一個數字小於您從序列中刪除的最後一個數字，則知道與其他四個常用數字相乘的結果會更小，因此請跳過乘法運算並轉到下一個數字。這樣的竅門只有1000位數纔會產生很大的影響，但後面的問題將會相同，只是輸入較大。

Answer 4

一個優化是計算前五個數字的乘積，並在每次迭代中乘以下一個數字併除以前一個（移動窗口）。

另一個優化是立即丟棄0周圍的所有數字。