Python3 欧拉计划 问题81-85

EulerProject.png
问题76-80参见：https://www.jianshu.com/p/8d4d53f7d18e

81、最小路径和(初级)  2个方向

  在如下5*5的数字矩阵中，只能向右或向下移动，从左上角到右下角的最小路径和为2427=131+201+96+342+746+422+121+37+331，路径已由红色数字标出：

matrix.png

在文件matrix.txt中包含了一个80*80的矩阵，求该矩阵的左上角到右下角的最小路径和。

Python3解答 动态回归思想参见

import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p081_matrix.txt')
an =[]
#读取数据
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)#转化为np数组形式
#从左上角开始生成斜线坐标直到右下角
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]])

#开始逐斜线计算直到右下角【动态规划思想】
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])
#输出最终的结果
print(npan[len(npan) -1, len(npan) - 1])
答案：427337

82、最小路径和(中级)  3个方向

  在如下5*5的数字矩阵中，从最左列任意一格出发，只能向右、向上或向下移动，到最右列任意一格结束的最小路径和为994=201+96+342+234+103+18，路径已由红色数字标出：

matrix.png

在文件matrix.txt中包含了一个80*80的矩阵，求该矩阵的最左列到最右列的最小路径和。

Python3解答 动态回归思想参见

import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p082_matrix.txt')
an =[]
#读取数据
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#转化为np数组形式转置
copynpan = npan.copy()
#定义组合函数
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)):#开始逐行进行计算【动态规划】
    for gg in range(len(npan[jj])):#直接运算
        npan[jj, gg] += npan[jj-1, gg]
    if jj < len(npan) - 1:
        Dcopynpan = copynpan.copy()
        for ii in range(len(npan[jj])):#开始比较运算
            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、最小路径和(高级)  4个方向

  在如下5*5的数字矩阵中，从左上角到右下角任意地向上、向下、向左或向右移动的最小路径和为2297=131+201+96+342+234+103+18+150+111+422+121+37+331，路径已由红色数字标出：

matrix.png

在文件matrix.txt中包含了一个80*80的矩阵，求该矩阵的左上角到右下角的最小路径和。

Python3解答 Dijkstra 算法

import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p083_matrix.txt')
an =[]
#读取数据
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)#转化为np数组形式转置
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]
#构建联通字典
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、大富翁

答案参见： https://www.jianshu.com/p/758674dfe2cb

85、长方形个数

  正如下图所示，在一个3*2的长方形网格中含有18=6+4+2+3+2+1个不同大小的长方形：

image

  虽然不存在恰好含有200万个长方形的长方形网格，但有许多长方形网格中含有的长方形数接近200万，求其中最接近这一数的长方形网格的面积。

Python3解答

import numpy as np
i = 1
sanp = np.zeros((3000, 3000))#存储个数
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#动态规划方法
        #计算最小的差值
        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

持续更新，欢迎讨论，敬请关注！！！