5

问题

有没有比蛮力法更好的方法来找到 Project Euler 问题 8 的解决方案，即Find the maximum product of 1000-digit number 。

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

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

旁注

  • 这不是一个家庭作业问题。
  • 我不是要求问题 8 的结果。
4

4 回答 4

7

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

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

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

于 2012-10-08T19:09:08.583 回答
6

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

您可以缓存最后 4 位的乘积或做类似的技巧，但绝对不会比O(n)更好。

于 2012-10-08T19:08:57.257 回答
5

是和不是。您确实必须查看五个连续数字的每个序列，但您不必每次通过循环都将这些序列中的每一个相乘。您可以采取一些捷径来加快处理速度。例如，如果下一个数字是 0，您可以向前跳过。此外，如果下一个数字小于您从序列中删除的最后一个数字，您知道乘以其他四个常见数字的结果会更小，因此跳过乘法并转到下一个数字。当你只有 1000 位数字时，这样的技巧不会有太大的不同，但以后的问题将是相同的，只是输入更大。

于 2012-10-08T19:10:50.843 回答
2

一种优化是计算前五个数字的乘积，并在每次迭代中乘以下一个数字并除以前一个数字（移动窗口）。

另一个优化是立即丢弃 周围的所有数字0。

于 2012-10-08T19:14:52.530 回答