Euler项目8:有比蛮力计算更有效的算法吗？

Question

问题

是否有比蛮力法更好地解决Euler问题8 (即在1000位数中找出五个连续数字的最大乘积。 )的方法？

我计算了所有可能的产品，并选择了最大的一个-蛮力算法。

有没有更有效的算法？或者是蛮力法是唯一的方法。

Side notes

• 这不是家庭作业问题。
• 我并不是要求第八题的结果。

Answer 1

由于问题要求连续的数字，“蛮力”在这种情况下意味着O(n)，n是数字(1000)的数目。只要数字中没有某种模式，就需要n个步骤来扫描数字，所以这是最快的解决方案。

您可以缓存最后4位数字的乘积或执行类似的技巧，但您肯定不会比O(n)更好。

Answer 2

您可以使用大小为5的滑动窗口，并在O(d)中解决这个问题，其中d是输入数字中的数字数。

您通过窗口中起始数的索引来表示窗口，而窗口I的值是索引i，i+4的元素的乘积。现在，在每次迭代中，您将窗口滑动到右边，有效地删除最左边的元素，并向右边添加一个新元素，窗口的新值是old_value / left_most_ele * new_right_ele。继续对范围i中的每个索引[0,d-5]执行此操作，并找到最大窗口值。

注意，内循环运行5次的嵌套循环的蛮力方法也是一个O(d)解决方案。但是上面的方法稍微好一点，因为我们不是在每一步做五次乘法，而是做一次乘法和一次除法。

Answer 3

是也不是。你确实需要查看每一个连续五个数字的序列，但是你不必每次在循环中乘以每一个序列。有一些快捷键可以加快处理速度。例如，如果下一个数字是0，则可以跳过前面。另外，如果下一个数字小于您从序列中删除的最后一个数字，您知道被其他四个公共数字相乘的结果会更小，所以跳过乘法，转到下一个数字。当你只有1000位数字时，这样的技巧不会有太大的区别，但是以后的问题将是一样的，只是更大的输入。