EulerProject.png
問題76-80參見：http://www.itdecent.cn/p/8d4d53f7d18e
81、最小路徑和(初級(jí))? 2個(gè)方向
??在如下5*5的數(shù)字矩陣中，只能向右或向下移動(dòng)，從左上角到右下角的最小路徑和為2427=131+201+96+342+746+422+121+37+331，路徑已由紅色數(shù)字標(biāo)出：
matrix.png
在文件matrix.txt中包含了一個(gè)80*80的矩陣，求該矩陣的左上角到右下角的最小路徑和。
Python3解答 動(dòng)態(tài)回歸思想?yún)⒁?/a>
import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p081_matrix.txt')
an =[]
#讀取數(shù)據(jù)
while 1:
x=fan.readline()
if len(x) == 0:
break
du = []
for jjj in list(x.split(',')):
du.append(jjj)
an.append(du)
fan.close()
npan = np.array(an, dtype=int)#轉(zhuǎn)化為np數(shù)組形式
#從左上角開始生成斜線坐標(biāo)直到右下角
weizhi = []
for jj in range(2 * len(npan) - 2):
sonweizhi = []
if jj < len(npan):
for dd in range(jj + 1):
sonweizhi.append([dd, jj - dd])
else:
for dd in range(jj - len(npan) + 1, len(npan)):
sonweizhi.append([dd, jj - dd])
weizhi.append(sonweizhi)
weizhi.append([[len(npan) -1, len(npan) - 1]])
#開始逐斜線計(jì)算直到右下角【動(dòng)態(tài)規(guī)劃思想】
for jj in weizhi[1:]:
for ii in jj:
if ii[0] == 0:
npan[ii[0], ii[1]] += npan[ii[0], ii[1] - 1]
elif ii[1] == 0:
npan[ii[0], ii[1]] += npan[ii[0] -1, ii[1]]
else:
npan[ii[0], ii[1]] += min(npan[ii[0] -1, ii[1]], npan[ii[0], ii[1] - 1])
#輸出最終的結(jié)果
print(npan[len(npan) -1, len(npan) - 1])
答案：427337
82、最小路徑和(中級(jí))? 3個(gè)方向
??在如下5*5的數(shù)字矩陣中，從最左列任意一格出發(fā)，只能向右、向上或向下移動(dòng)，到最右列任意一格結(jié)束的最小路徑和為994=201+96+342+234+103+18，路徑已由紅色數(shù)字標(biāo)出：
matrix.png
在文件matrix.txt中包含了一個(gè)80*80的矩陣，求該矩陣的最左列到最右列的最小路徑和。
Python3解答 動(dòng)態(tài)回歸思想?yún)⒁?/a>
import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p082_matrix.txt')
an =[]
#讀取數(shù)據(jù)
while 1:
x=fan.readline()
if len(x) == 0:
break
du = []
for jjj in list(x.split(',')):
du.append(jjj)
an.append(du)
fan.close()
npan = np.array(an, dtype=int).T#轉(zhuǎn)化為np數(shù)組形式轉(zhuǎn)置
copynpan = npan.copy()
#定義組合函數(shù)
def combine(nplist, mcode):
comlist = []
for i in range(len(nplist)):
dnum = 0
if i < mcode:
cc = i + 1
while cc < mcode:
dnum += nplist[cc]
cc += 1
comlist.append(dnum)
elif i == mcode:
pass
else:
cc = i - 1
while cc > mcode:
dnum += nplist[cc]
cc -= 1
comlist.append(dnum)
return comlist
for jj in range(1, len(npan)):#開始逐行進(jìn)行計(jì)算【動(dòng)態(tài)規(guī)劃】
for gg in range(len(npan[jj])):#直接運(yùn)算
npan[jj, gg] += npan[jj-1, gg]
if jj < len(npan) - 1:
Dcopynpan = copynpan.copy()
for ii in range(len(npan[jj])):#開始比較運(yùn)算
if ii == 0:
copynpan[jj, ii] += min(copynpan[jj - 1, ii], np.min(npan[jj][1 :] + np.array(combine(Dcopynpan[jj], ii))))#需要比較所有路徑
elif ii == len(npan[jj]) - 1:
copynpan[jj, ii] += min(copynpan[jj - 1, ii], np.min(npan[jj][: -1] + np.array(combine(Dcopynpan[jj], ii))))#需要比較所有路徑
else:
addlist = np.array(list(npan[jj][: ii]) + list(npan[jj][ii + 1 :]))
copynpan[jj, ii] += min(copynpan[jj - 1, ii], np.min(np.array(combine(Dcopynpan[jj], ii)) + addlist))#需要比較所有路徑
npan = copynpan.copy()
else:
print(np.min(npan[-1]))
答案：260324
83、最小路徑和(高級(jí))? 4個(gè)方向
??在如下5*5的數(shù)字矩陣中，從左上角到右下角任意地向上、向下、向左或向右移動(dòng)的最小路徑和為2297=131+201+96+342+234+103+18+150+111+422+121+37+331，路徑已由紅色數(shù)字標(biāo)出：
matrix.png
在文件matrix.txt中包含了一個(gè)80*80的矩陣，求該矩陣的左上角到右下角的最小路徑和。
Python3解答 Dijkstra 算法
import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p083_matrix.txt')
an =[]
#讀取數(shù)據(jù)
while 1:
x=fan.readline()
if len(x) == 0:
break
du = []
for jjj in list(x.split(',')):
du.append(jjj)
an.append(du)
fan.close()
npan = np.array(an, dtype=int)#轉(zhuǎn)化為np數(shù)組形式轉(zhuǎn)置
copynpan = np.array(npan.copy(), dtype = float)
#開始
zuibiaoset = []
for jj in range(len(npan)):
for gg in range(len(npan)):
copynpan[jj, gg] = float('inf')
copynpan[0, 0] = npan[0, 0]
#構(gòu)建聯(lián)通字典
liantong = {}
for gg in range(len(npan)):
for hh in range(len(npan)):
dd = [[gg - 1, hh],[gg + 1, hh],[gg, hh - 1],[gg, hh + 1]]
liantong[(gg, hh)] = []
for ff in dd:
if ff[0] >=0 and ff[0] < len(npan) and ff[1] >=0 and ff[1] < len(npan):
liantong[(gg, hh)].append(ff)
#Dijkstra 算法
def Dijkstra(startlist, lidict = liantong, yuanshi = npan, com = copynpan):
start = []
if startlist == []:
return com
else:
for gg in startlist:
fulist = lidict[(gg[0], gg[1])]
for jjj in fulist:
comnumber = com[gg[0], gg[1]] + yuanshi[jjj[0], jjj[1]]
if comnumber < com[jjj[0], jjj[1]]:
com[jjj[0], jjj[1]] = comnumber
start.append(jjj)
return Dijkstra(start)
print(int(Dijkstra([[0, 0]])[-1,-1]))
答案：425185
84、大富翁
答案參見： http://www.itdecent.cn/p/758674dfe2cb
85、長方形個(gè)數(shù)
??正如下圖所示，在一個(gè)3*2的長方形網(wǎng)格中含有18=6+4+2+3+2+1個(gè)不同大小的長方形：
??雖然不存在恰好含有200萬個(gè)長方形的長方形網(wǎng)格，但有許多長方形網(wǎng)格中含有的長方形數(shù)接近200萬，求其中最接近這一數(shù)的長方形網(wǎng)格的面積。
Python3解答
import numpy as np
i = 1
sanp = np.zeros((3000, 3000))#存儲(chǔ)個(gè)數(shù)
start = 1
num = 100000
sign = 0
while 1:
for j in range(1, start + 1):
sanp[i, j] = sanp[j, i] = sanp[i - 1, j] + sanp[i, j - 1] - sanp[i - 1, j - 1] + i * j#動(dòng)態(tài)規(guī)劃方法
#計(jì)算最小的差值
result = abs(2e6 - sanp[i, j])
if num > result:
num = result
re =[i, j].copy()
if j == 1 and sanp[i, j] > 2e6:
sign = -1
break
if sanp[i, j] > 2e6:
sign = 1
start = j
if sign != 1:
start += 1
if sign == -1:
break
i += 1
print(re[0] * re[1])
答案：2772
持續(xù)更新，歡迎討論，敬請(qǐng)關(guān)注！??！??
