python - Project Euler 8 程序未提供正确答案
问题描述
我在寻找问题的正确答案时遇到问题。
我有以下代码:
import time
print("This program will provide the largest product of 13 adjacent digits from a given number")
num = str(input("Enter the number from which you want to find the largest product"))
start = time.time()
biggest = 0
for i in range(len(num) - 12):
a = int(num[i])
b = int(num[i + 1])
c = int(num[i + 2])
d = int(num[i + 3])
e = int(num[i + 4])
f = int(num[i + 5])
g = int(num[i + 6])
h = int(num[i + 7])
i = int(num[i + 8])
j = int(num[i + 9])
k = int(num[i + 10])
l = int(num[i + 11])
m = int(num[i + 12])
product = a * b * c * d * e * f * g * h * i * j * k * l * m
if product > biggest:
biggest = product
print(biggest)
end = time.time()
print(end - start)
我最终得到 823011840 这是错误的答案,但我不知道这个程序有什么问题。
解决方案
i
在内循环中创建的变量之一与控制外循环的变量同名。这样变量j
, k
, l
,n
永远m
不会得到它们的预期值,而是得到j = int(num[int(num[i + 8]) + 9])
等。
循环的本质是:
for outer_i in range(len(num) - 12):
i = outer_i
a = int(num[i])
b = int(num[i + 1])
c = int(num[i + 2])
d = int(num[i + 3])
e = int(num[i + 4])
f = int(num[i + 5])
g = int(num[i + 6])
h = int(num[i + 7])
inner_i = int(num[i + 8])
i = inner_i
j = int(num[i + 9])
k = int(num[i + 10])
l = int(num[i + 11])
m = int(num[i + 12])
product = a * b * c * d * e * f * g * h * i * j * k * l * m
if product > biggest:
biggest = product
除了为外部变量使用不同的名称之外,这里还有一个使用滑动窗口方法来提高速度的建议:
- 将 num 拆分为零之间的部分
- 对于每个部分“num_part”:
- 如果元素少于 13 个则跳过它
- 计算 p,前 13 个元素的乘积
- 检验 p 的最大值
- 对于从 13 开始的每个 t:
- 将 p 除以 num_part[t-13] 并乘以 num_part[t]
- 检验 p 的最大值