问题
在解决欧拉计划8号问题时（找出1000位数中相邻5个数字的最大乘积），是否有更好的方法，避免使用蛮力法计算所有可能的乘积并选择最大值。
有没有更有效率的算法？或者只能使用蛮力法？
附注
- 这不是一道作业题目。
- 我并不要求问题8的答案。
4个回答
7
您可以使用大小为5的滑动窗口并以
您可以通过窗口中起始数字的索引和窗口i的值来表示窗口，窗口i的值是具有索引[i，i + 4]的元素的乘积。现在，在每次迭代中，您将窗口向右滑动，有效地丢弃最左侧的元素并将一个新元素添加到右侧，窗口的新值为
请注意，嵌套循环的暴力方法，其中内部循环运行五次，也是一个O(d)的解决方案。但上述方法略微更好，因为我们不会在每个步骤中进行五次乘法，而是进行一次乘法和一次除法。
O(d)的时间复杂度解决此问题，其中d是输入数字的位数。您可以通过窗口中起始数字的索引和窗口i的值来表示窗口，窗口i的值是具有索引[i，i + 4]的元素的乘积。现在，在每次迭代中，您将窗口向右滑动，有效地丢弃最左侧的元素并将一个新元素添加到右侧，窗口的新值为
old_value / left_most_ele * new_right_ele。对于范围内的每个索引i [0，d-5]，继续执行此操作，并找到最大的窗口值。请注意，嵌套循环的暴力方法，其中内部循环运行五次，也是一个O(d)的解决方案。但上述方法略微更好，因为我们不会在每个步骤中进行五次乘法，而是进行一次乘法和一次除法。
- codaddict
2
1只要小心不要除以0就好了 :)。 - IVlad
1@IVlad：我已经把这些细节留给了OP :) - codaddict
6
由于这个问题要求 连续数字，所以在这种情况下，“暴力破解”意味着 O(n)，其中 n 是数字的位数（1000）。只要数字中没有某种模式，你就需要 n 步来扫描数字，因此这是最快的解决方案。
你可以缓存最后 4 个数字的乘积或进行类似的技巧，但你肯定不会比 O(n) 更好。
- tobias_k
5
是和不是。您确实需要查看每个连续五个数字的序列，但您不必在每次循环中乘以这些序列中的每一个。您可以采取一些快捷方式来加速处理。例如，如果下一个数字是0，则可以跳过它。此外，如果下一个数字比您从序列中删除的上一个数字小，那么您就知道通过其他四个常见数字相乘的结果将会更小，因此跳过乘法并进入下一个数字。像这样的技巧在只有1000个数字时不会有太大的差异，但稍后的问题将是相同的，只是输入更大而已。
- Bill the Lizard
2
优化之一是计算前五位数字的乘积，在每次迭代中乘以下一个数字并除以前一个数字（移动窗口）。
另一种优化是立即丢弃所有在0周围的数字。
- Tomasz Nurkiewicz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接