首先這是問題:https://projecteuler.net/problem=82。 這是我的代碼:歐拉項目#82(Python)
# https://projecteuler.net/problem=82
matrice = open('matrix3.txt','r').read().split('\n')
m = []
for el in matrice:
if el=='':
continue
tmp = el.split(',')
m.append(tmp)
matrix = [[0 for i in range(80)]for j in range(80)]
x,y = 0,0
while(True):
matrix[x][y]=int(m[x][y])
y+=1
if y==80:
y=0
x+=1
if x==80:
break
tmp = [0]*80
x,y = 0,78
while(True):
if x==0:
tmp[x]=min(matrix[x][y+1],matrix[x+1][y]+matrix[x+1][y+1])
if x==79:
tmp[x]=min(matrix[x][y+1],matrix[x-1][y]+matrix[x-1][y+1])
else:
tmp[x]=min(matrix[x][y+1],matrix[x-1][y]+matrix[x-1][y+1],matrix[x+1][y]+matrix[x+1][y+1])
x+=1
if x==80:
for e in range(80):
matrix[e][y]+=tmp[e]
tmp = [0]*80
x=0
y+=-1
if y<0:
break
minimo = 10**9
for e in range(80):
if matrix[e][0]<minimo:
minimo=matrix[e][0]
print(minimo)
這段代碼背後的想法是這樣的: 我從第79列開始(第78,如果你從0開始計數),我計算出最佳(最小)的方式來獲得從該列中的任何給定條目到右側的列。 當列結束時,我用我發現的最小結果替換它,並開始對左邊的列執行相同的操作。
有沒有人能告訴我爲什麼我得到錯誤的答案?(我得到262716)
相同的代碼工作在例如矩陣(如果你改變當然的indeces它的工作原理)。
你怎麼知道正確的答案是什麼?我沒有看到它的任何地方。 – Emily 2013-03-21 13:52:58
@Emily該網站有一個註冊用戶的表單,您可以提交問題的答案並查看它是否正確。 – 2013-03-21 14:11:45
@ LauritzV.Thaulow謝謝! – Emily 2013-03-21 21:22:51