鱼C论坛

 找回密码
 立即注册
查看: 3212|回复: 5

[技术交流] python小练习(013):三角形从顶端到底端的最优路径

[复制链接]
发表于 2016-11-19 17:43:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2016-11-20 08:44 编辑

昨天python小练习我们研究了象棋中“马”的日字形走法,传送门

既然是路径问题,那么今天继续研究和路径相关的问题,我们来看看三角形从顶端到底端的最优路径。

下面的三角形从顶端到底端的最优路径(路径上的数字相加最小),已经用红色数字标出了。

                               
登录/注册后可看大图

规则是:三角形从顶端开始依次往下走一层,可以选择下方相邻的2个数字中的一个,但是不能逆向,不能横向行走。

那么对于一个有20层的三角形,从顶端到底端的最优路径的和又是多少呢?
  1. 59
  2. 73 41
  3. 52 40 09
  4. 26 53 06 34
  5. 10 51 87 86 81
  6. 61 95 66 57 25 68
  7. 90 81 80 38 92 67 73
  8. 30 28 51 76 81 18 75 44
  9. 84 14 95 87 62 81 17 78 58
  10. 21 46 71 58 02 79 62 39 31 09
  11. 56 34 35 53 78 31 81 18 90 93 15
  12. 78 53 04 21 84 93 32 13 97 11 37 51
  13. 45 03 81 79 05 18 78 86 13 30 63 99 95
  14. 39 87 96 28 03 38 42 17 82 87 58 07 22 57
  15. 06 17 51 17 07 93 09 07 75 97 95 78 87 08 53
  16. 67 66 59 60 88 99 94 65 55 77 55 34 27 53 78 28
  17. 76 40 41 04 87 16 09 42 75 69 23 97 30 60 10 79 87
  18. 12 10 44 26 21 36 32 84 98 60 13 12 36 16 63 31 91 35
  19. 70 39 06 05 55 27 38 48 28 22 34 35 62 62 15 14 94 89 86
  20. 66 56 68 84 96 21 34 34 34 81 62 40 65 54 62 05 98 03 02 60
复制代码

评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-11-20 08:28:25 | 显示全部楼层
解答:
思路:利用动态规划原理,把每一层的数字加上上一层相邻2个数字中最小的数字,依次类推,只要统计底层哪个数字最小就是答案。
  1. data = '''59
  2. 73 41
  3. 52 40 09
  4. 26 53 06 34
  5. 10 51 87 86 81
  6. 61 95 66 57 25 68
  7. 90 81 80 38 92 67 73
  8. 30 28 51 76 81 18 75 44
  9. 84 14 95 87 62 81 17 78 58
  10. 21 46 71 58 02 79 62 39 31 09
  11. 56 34 35 53 78 31 81 18 90 93 15
  12. 78 53 04 21 84 93 32 13 97 11 37 51
  13. 45 03 81 79 05 18 78 86 13 30 63 99 95
  14. 39 87 96 28 03 38 42 17 82 87 58 07 22 57
  15. 06 17 51 17 07 93 09 07 75 97 95 78 87 08 53
  16. 67 66 59 60 88 99 94 65 55 77 55 34 27 53 78 28
  17. 76 40 41 04 87 16 09 42 75 69 23 97 30 60 10 79 87
  18. 12 10 44 26 21 36 32 84 98 60 13 12 36 16 63 31 91 35
  19. 70 39 06 05 55 27 38 48 28 22 34 35 62 62 15 14 94 89 86
  20. 66 56 68 84 96 21 34 34 34 81 62 40 65 54 62 05 98 03 02 60'''
  21. tri = [[] for i in range(20)]
  22. lines = data.split('\n')
  23. for i in range(20):
  24.         line = lines[i].split()
  25.         for e in line:
  26.                 tri[i].append(int(e))
  27. for i in range(1,20):
  28.         for j in range(i+1):
  29.                 if j == 0:
  30.                         tri[i][j] += tri[i-1][j]
  31.                 elif j == i:
  32.                         tri[i][j] += tri[i-1][j-1]
  33.                 else:
  34.                         tri[i][j] += min(tri[i-1][j],tri[i-1][j-1])
  35. print (min(tri[19]))
复制代码


输出:
693
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-12 22:13:48 | 显示全部楼层
  1. data = '''59
  2. 73 41
  3. 52 40 09
  4. 26 53 06 34
  5. 10 51 87 86 81
  6. 61 95 66 57 25 68
  7. 90 81 80 38 92 67 73
  8. 30 28 51 76 81 18 75 44
  9. 84 14 95 87 62 81 17 78 58
  10. 21 46 71 58 02 79 62 39 31 09
  11. 56 34 35 53 78 31 81 18 90 93 15
  12. 78 53 04 21 84 93 32 13 97 11 37 51
  13. 45 03 81 79 05 18 78 86 13 30 63 99 95
  14. 39 87 96 28 03 38 42 17 82 87 58 07 22 57
  15. 06 17 51 17 07 93 09 07 75 97 95 78 87 08 53
  16. 67 66 59 60 88 99 94 65 55 77 55 34 27 53 78 28
  17. 76 40 41 04 87 16 09 42 75 69 23 97 30 60 10 79 87
  18. 12 10 44 26 21 36 32 84 98 60 13 12 36 16 63 31 91 35
  19. 70 39 06 05 55 27 38 48 28 22 34 35 62 62 15 14 94 89 86
  20. 66 56 68 84 96 21 34 34 34 81 62 40 65 54 62 05 98 03 02 60'''.split('\n')

  21. lt = [dt.split(' ') for dt in data]
  22. temp = [('0', lt[0][0])]
  23. for row in lt[1:]:
  24.     temp1 = []
  25.     for j in range(len(row)):
  26.         if j == 0:
  27.             rs = (temp[j][0]+'-'+str(j), int(temp[j][1])+int(row[j]))
  28.         elif j == len(row)-1:
  29.             rs = (temp[j-1][0]+'-'+str(j), int(temp[j-1][1])+int(row[j]))
  30.         else:
  31.             Num1 = int(temp[j][1]) + int(row[j])
  32.             Num2 = int(temp[j - 1][1]) + int(row[j])
  33.             if Num1 < Num2:
  34.                 rs = (temp[j][0] + '-' + str(j), Num1)
  35.             else:
  36.                 rs = (temp[j - 1][0] + '-' + str(j), Num2)
  37.         temp1.append(rs)
  38.     temp = temp1

  39. Path = [i[0] for i in temp]
  40. Total_num = [i[1] for i in temp]

  41. print('路径是:' + Path[Total_num.index(min(Total_num))] + '\n', '最小的和是:' + str(min(Total_num)))
复制代码

结果是:
  1. 路径是:0-1-2-2-3-4-5-5-6-7-7-7-8-9-10-11-12-13-14-15
  2. 最小的和是:693
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-7 21:47:24 From FishC Mobile | 显示全部楼层
楼主以前学c的吧,这么6
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-10 22:47:40 | 显示全部楼层
用递归写了一遍
  1. import copy

  2. data = '''59
  3. 73 41
  4. 52 40 09
  5. 26 53 06 34
  6. 10 51 87 86 81
  7. 61 95 66 57 25 68
  8. 90 81 80 38 92 67 73
  9. 30 28 51 76 81 18 75 44
  10. 84 14 95 87 62 81 17 78 58
  11. 21 46 71 58 02 79 62 39 31 09
  12. 56 34 35 53 78 31 81 18 90 93 15
  13. 78 53 04 21 84 93 32 13 97 11 37 51
  14. 45 03 81 79 05 18 78 86 13 30 63 99 95
  15. 39 87 96 28 03 38 42 17 82 87 58 07 22 57
  16. 06 17 51 17 07 93 09 07 75 97 95 78 87 08 53
  17. 67 66 59 60 88 99 94 65 55 77 55 34 27 53 78 28
  18. 76 40 41 04 87 16 09 42 75 69 23 97 30 60 10 79 87
  19. 12 10 44 26 21 36 32 84 98 60 13 12 36 16 63 31 91 35
  20. 70 39 06 05 55 27 38 48 28 22 34 35 62 62 15 14 94 89 86
  21. 66 56 68 84 96 21 34 34 34 81 62 40 65 54 62 05 98 03 02 60'''
  22. data=data.split('\n')
  23. for i in range(20):
  24.         data[i]=[int(s) for s in data[i].split(' ')]
  25. howLong=copy.deepcopy(data)
  26. def getlong(i,j,data=data,howLong=howLong):
  27.         if i==0 and j==0:
  28.                 return 59
  29.         elif howLong[i][j]!=data[i][j]:
  30.                 return howLong[i][j]
  31.         if j==0:
  32.                 howLong[i][j]=getlong(i-1,j)+data[i][j]
  33.         elif j==i:
  34.                 howLong[i][j]=getlong(i-1,i-1)+data[i][j]
  35.         else:
  36.                 howLong[i][j]=min(getlong(i-1,j-1),getlong(i-1,j))+data[i][j]
  37.         return howLong[i][j]
  38. for i in range(20):
  39.         getlong(19,i)
  40. print(min(howLong[19]))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-12 01:32:48 | 显示全部楼层
题目的例子标出的红色部分错了吧?红色的是最大路径,不是最小。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 09:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表