2013-03-21 122 views
-2

首先這是問題: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它的工作原理)。

+0

你怎麼知道正確的答案是什麼?我沒有看到它的任何地方。 – Emily 2013-03-21 13:52:58

+2

@Emily該網站有一個註冊用戶的表單,您可以提交問題的答案並查看它是否正確。 – 2013-03-21 14:11:45

+0

@ LauritzV.Thaulow謝謝! – Emily 2013-03-21 21:22:51

回答

3

如果我理解的問題,你的代碼,並正確的算法,它看起來像你實際上並沒有計算最好的方式從一列去下一個,因爲你只考慮一對夫婦的可能途徑去下一個專欄。例如,考慮第一次迭代(當y=78)。然後我認爲你想要的是tmp[0]將從matrix[0][78]獲得的最小總和保留到第79列中的任何位置,但是你只考慮兩種可能性:向右走,或者向下走,然後向右走。如果從matrix[0][78]到下一列的最佳方式是下降6個條目然後向右走?你的代碼永遠不會考慮這種可能性。

您的代碼可能工作在小例子,因爲它恰巧最小路徑僅上升或下降在每列一次。但我認爲這是巧合(也可能是選擇不好的例子)。

解決此問題的一種方法是使用以下方法。當輸入是N×N矩陣時,定義一個NxN數組min_path。我們打算填寫min_path,以便min_path[x][y]是從輸入矩陣的第一列中的任意條目開始到最終的路徑總和爲[x][y]。我們一次填寫一列min_path,從最左列開始。爲計算min_path[i][j],我們查看min_path第(j-1)列中的所有條目以及從每個條目到(i,j)的成本。以下是一些顯示此解決方案的Python代碼:https://gist.github.com/estark37/5216851。這是一個O(N^4)解決方案,但它可能會更快! (也許通過預先計算的sum_to調用的結果?)