小练习：20160523 找出从三角形顶端走到底端的最大和

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即5.30 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。


题目：

从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为 23.

                               
登录/注册后可看大图

也就是 3 + 7 + 4 + 9 = 23.

找出从以下三角形的顶端走到底端的最大总和：

                               
登录/注册后可看大图

附加题：

                               
登录/注册后可看大图

BaiduShurufa_2015-4-21_16-37-7.png (3.19 KB, 下载次数: 0)
下载附件  [url=]保存到相册[/url]

[color=rgb(153, 153, 153) !important]2015-4-21 16:38 上传

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

caobynk

1. # 小练习
   
2. data = '''
   
3.         75
   
4.         95 64
   
5.         17 47 82
   
6.         18 35 87 10
   
7.         20 04 82 47 65
   
8.         19 01 23 75 03 34
   
9.         88 02 77 73 07 63 67
   
10.         99 65 04 28 06 16 70 92
    
11.         41 41 26 56 83 40 80 70 33
    
12.         41 48 72 33 47 32 37 16 94 29
    
13.         53 71 44 65 25 43 91 52 97 51 14
    
14.         70 11 33 28 77 73 17 78 39 68 17 57
    
15.         91 71 52 38 17 14 91 43 58 50 27 29 48
    
16.         63 66 04 68 89 53 67 30 73 16 69 87 40 31
    
17.         04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
    
18. '''
    
19. data = data.split()
    
20. num = []
    
21. for k in range(1, 16):
    
22.     num.append(list(map(int, data[int(k*(k-1)/2) : int(k*(k+1)/2)])))
    
23. for k in range(2, 16):
    
24.     num[k-1][0] = num[k-2][0] + num[k-1][0]
    
25.     num[k-1][-1] = num[k-2][-1] + num[k-1][-1]
    
26.     if len(num[k-1]) >2 :
    
27.         for i in range(1,len(num[k-1])-1):
    
28.             num[k-1][i] = max(num[k-2][i-1], num[k-2][i]) + num[k-1][i]
    
29. print(max(num[-1]))
    
30. 
    
31. # 附加题
    
32. from functools import reduce
    
33. num = 2**1000
    
34. num = list(str(num))
    
35. print(reduce(lambda x,y: int(x)+int(y), num))
    

复制代码

holdme

这道题挺有趣的：

1. import time
   
2. start = time.clock()
   
3. tri = [[75]\
   
4. ,[95,64]\
   
5. ,[17,47,82]\
   
6. ,[18,35,87,10]\
   
7. ,[20,4,82,47,65]\
   
8. ,[19,1,23,75,3,34]\
   
9. ,[88,2,77,73,7,63,67]\
   
10. ,[99,65,4,28,6,16,70,92]\
    
11. ,[41,41,26,56,83,40,80,70,33]\
    
12. ,[41,48,72,33,47,32,37,16,94,29]\
    
13. ,[53,71,44,65,25,43,91,52,97,51,14]\
    
14. ,[70,11,33,28,77,73,17,78,39,68,17,57]\
    
15. ,[91,71,52,38,17,14,91,43,58,50,27,29,48]\
    
16. ,[63,66,4,68,89,53,67,30,73,16,69,87,40,31]\
    
17. ,[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
    
18. 
    
19. #由底部向上，逐层寻优
    
20. for i in range(1,15):
    
21.     tri[-i-1] = [max(tri[-i-1][j]+tri[-i][j],tri[-i-1][j]+tri[-i][j+1]) for j in range(len(tri[-i-1]))]
    
22. 
    
23. print('最大总和为：%s'%str(tri[0]))
    
24. print('用时%s秒'%str(time.clock()-start))

复制代码

结果：

1. 最大总和为：[1074]
   
2. 用时0.00024412117514316378秒

复制代码

附加题：

1. print(sum(int(i) for i in list(str(2**1000))))

复制代码

结果是：

1. 1366

复制代码

小火木

1. print(sum(int(x) for x in list(str(2**1000))))

复制代码

挥舞乾坤

1. data ='''
   
2. 75
   
3. 95 64
   
4. 17 47 82
   
5. 18 35 87 10
   
6. 20 04 82 47 65
   
7. 19 01 23 75 03 34
   
8. 88 02 77 73 07 63 67
   
9. 99 65 04 28 06 16 70 92
   
10. 41 41 26 56 83 40 80 70 33
    
11. 41 48 72 33 47 32 37 16 94 29
    
12. 53 71 44 65 25 43 91 52 97 51 14
    
13. 70 11 33 28 77 73 17 78 39 68 17 57
    
14. 91 71 52 38 17 14 91 43 58 50 27 29 48
    
15. 63 66 04 68 89 53 67 30 73 16 69 87 40 31
    
16. 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
    
17. 
    
18. # 处理数据
    
19. data = data.split()
    
20. 
    
21. lst = [[] for i in range(15)]
    
22. for i in range(15):
    
23.     j = i
    
24.     while j+1:
    
25.         lst[i].append(int(data.pop(0)))
    
26.         j -= 1
    
27. 
    
28. for i in reversed(range(14)):
    
29.     for j in range(i+1):
    
30.         lst[i][j] +=   lst[i+1][j] if lst[i+1][j] > lst[i+1][j+1] else lst[i+1][j+1]
    
31. 
    
32. print(lst[0][0])

复制代码

附加题:
方法1:

1. print((lambda self,n,t=0: self(self,n // 10,t + n % 10) if n // 10 else t + n % 10)((lambda self,n,t=0: self(self,n // 10,t + n % 10) if n // 10 else t + n % 10),2**1000))

复制代码

方法2:

1. print(sum(map(int,list(str(2**1000)))))

复制代码

小剑剑

懒惰的斑猪，竟然贴图片

1. raw_number='''75
   
2. 95 64
   
3. 17 47 82
   
4. 18 35 87 10
   
5. 20 04 82 47 65
   
6. 19 01 23 75 03 34
   
7. 88 02 77 73 07 63 67
   
8. 99 65 04 28 06 16 70 92
   
9. 41 41 26 56 83 40 80 70 33
   
10. 41 48 72 33 47 32 37 16 94 29
    
11. 53 71 44 65 25 43 91 52 97 51 14
    
12. 70 11 33 28 77 73 17 78 39 68 17 57
    
13. 91 71 52 38 17 14 91 43 58 50 27 29 48
    
14. 63 66 04 68 89 53 67 30 73 16 69 87 40 31
    
15. 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
    
16. numlist=raw_number.split('\n')
    
17. hie=len(numlist)
    
18. for i in range(hie):
    
19.       exec("numlist[{0}]=numlist[{0}].split()".format(i))
    
20.       exec('''for ii in range(i+1):
    
21.            numlist[{0}][ii]=int(numlist[{0}][ii])'''.format(i))
    
22. for i in range(hie-2,-1,-1):
    
23.       for ii in range(i+1):
    
24.             if numlist[i+1][ii]>=numlist[i+1][ii+1]:
    
25.                   numlist[i][ii]+=numlist[i+1][ii]
    
26.             else:
    
27.                  numlist[i][ii]+=numlist[i+1][ii+1]
    

复制代码

答案1074
不知道有没有打错数字
从倒数第二行开始每个数判断下面一行的相邻数字的大小，自增大的数字，一直到第一行

1. su=0
   
2. for i in list(str(2**1000)):
   
3.       su+=int(i)
   

复制代码

bacon6581

1. from time import time
   
2. start=time()
   
3. num='''75
   
4. 95 64
   
5. 17 47 82
   
6. 18 35 87 10
   
7. 20 04 82 47 65
   
8. 19 01 23 75 03 34
   
9. 88 02 77 73 07 63 67
   
10. 99 65 04 28 06 16 70 92
    
11. 41 41 26 56 83 40 80 70 33
    
12. 41 48 72 33 47 32 37 16 94 29
    
13. 53 71 44 65 25 43 91 52 97 51 14
    
14. 70 11 33 28 77 73 17 78 39 68 17 57
    
15. 91 71 52 38 17 14 91 43 58 50 27 29 48
    
16. 63 66 04 68 89 53 67 30 73 16 69 87 40 31
    
17. 04 62 98 27 23 09 70 98 73 93 38 53 60 14 23'''
    
18. 
    
19. a=num.split('\n')
    
20. b=[]
    
21. c=[]
    
22. for i in a:
    
23.     b=i.split()
    
24.     c.append(b)
    
25.    
    
26. value_max=0
    
27. i_max=0
    
28. for k in range(0,16385):
    
29.     i=k
    
30.     value=75
    
31.     m=0
    
32.     for j in range(1,15):
    
33.         if i%2 == 1:
    
34.             m+=1
    
35.         i>>=1
    
36.         
    
37.         value+=int(c[j][m])
    
38.     if value>value_max:
    
39.         value_max=value
    
40.         i_max=k
    
41. print('最大值：'+str(value_max))
    
42. print('路径：'+str(bin(i_max)))
    
43. print('需时：'+str(time()-start))
    
44. 
    
45. #####################
    
46. print('附加题：')
    
47. 
    
48. start=time()
    
49. a=str(2**1000)
    
50. value=0
    
51. for i in a:
    
52.     value+=int(i)
    
53. print('值：'+str(value))
    
54. print('需时：'+str(time()-start))
    

复制代码

DingRan

严重支持

1. a = [
   
2.     ['95','64'],
   
3.     ['17','47','82'],
   
4.     ['18','35','87','10'],
   
5.     ['20','04','82','47','65'],
   
6.     ['19','01','23','75','03','34'],
   
7.     ['88','02','77','73','07','63','67'],
   
8.     ['99','65','04','28','06','16','70','92'],
   
9.     ['41','41','26','56','83','40','80','70','33'],
   
10.     ['41','48','72','33','47','32','37','16','94','29'],
    
11.     ['53','71','44','65','25','43','91','52','97','51','14'],
    
12.     ['70','11','33','28','77','73','17','78','39','68','17','57'],
    
13.     ['91','71','52','38','17','14','91','43','58','50','27','29','48'],
    
14.     ['63','66','04','68','89','53','67','30','73','16','69','87','40','31'],
    
15.     ['04','62','98','27','23','09','70','98','73','93','38','53','60','04','23']
    
16.     ]
    
17. 
    
18. def func(path):
    
19.     j = 0
    
20.     s = 75
    
21.     for i in range(14):
    
22.         j += int(path[i])
    
23.         s += int(a[i][j])
    
24.     return s
    
25. 
    
26. maxs = 0
    
27. for num in range(2**14):
    
28.     path = str(bin(num))[2:].rjust(14,'0')
    
29.     s = func(path)
    
30.     if s>maxs:
    
31.         maxs = s
    
32. print('最大总和：%d'%maxs)
    
33. 
    
34. print('附加题：%d'%sum([int(each) for each in str(2**1000)]))

复制代码

运行结果

1. >>>
   
2. 最大总和：1074
   
3. 附加题：1366
   
4. >>>

复制代码

ps:我能吐个槽么。。。。。。
pps:图片格式的数堆。。。。。。太反人类了。。。。。。
ppps:如果计算结果不对的话一定是我抄数抄错了口亨！(逃~

WylLy

1. import copy
   
2. import time
   
3. 
   
4. a = 100
   
5. b = 0
   
6. while a:
   
7.     t1 = time.time()
   
8.     data = [[75],[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,16,70,92],[41,41,26,56,83,40,80,70,33],
   
9.             [41,48,72,33,47,32,37,16,94,29],[53,71,44,65,25,43,91,52,97,51,14],[70,11,33,28,77,73,17,78,39,68,17,57],
   
10.             [91,71,52,38,17,14,91,43,58,50,27,29,48],[63,66,4,68,89,53,67,30,73,16,69,87,40,31],
    
11.             [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
    
12.     for i in range(1, 15):
    
13.         lt = copy.copy(data[i])
    
14.         for j in range(i):
    
15.             data[i][j] = max(data[i-1][j] + lt[j], data[i][j])
    
16.             data[i][j+1] = max(data[i-1][j] + lt[j+1], data[i][j+1])
    
17.     t2 = time.time()
    
18.     a -= 1
    
19.     b += t2 - t1
    
20. print('最大值是：', max(data[-1]))
    
21. print('运行100次所需的时间：', b)
    
22. 
    
23. 
    
24. #附加题
    
25. j = 100
    
26. t = 0
    
27. while j:
    
28.     t3 = time.time()
    
29.     r = 0
    
30.     a = str(2**1000)
    
31.     for i in a:
    
32.         r += int(i)
    
33.     t4 = time.time()
    
34.     t += t4 - t3
    
35.     j -= 1
    
36. print('2^1000的各位数和：', r)
    
37. print('附加题运行100次所需的时间：', t)

复制代码

运行结果是：

1. 最大值是： 1074
   
2. 运行100次所需的时间： 0.0250246524810791
   
3. 2^1000的各位数和： 1366
   
4. 附加题运行100次所需的时间： 0.01902151107788086

复制代码

cold2wind

1. def maxSum():
   
2.     data = '''75
   
3.              95 64
   
4.              17 47 82
   
5.              18 35 87 10
   
6.              20 4 82 47 65
   
7.              19 1 23 75 3 34
   
8.              88 2 77 73 7 63 67
   
9.              99 65 4 28 6 16 70 92
   
10.              41 41 26 56 83 40 80 70 33
    
11.              41 48 72 33 47 32 37 16 94 29
    
12.              53 71 44 65 25 43 91 52 97 51 14
    
13.              70 11 33 28 77 73 17 78 39 68 17 57
    
14.              91 71 52 38 17 14 91 43 58 50 27 29 48
    
15.              63 66 4 68 89 53 67 30 73 16 69 87 40 31
    
16.              4 62 98 27 23 9 70 98 73 93 38 53 60 4 23'''
    
17.     list = data.split("\n")
    
18. 
    
19.     source = []
    
20.     for i in list:
    
21.         source.append(i.strip().split(' '))
    
22. 
    
23.     # 初始化第一列
    
24.     for i in range(1, len(source)):
    
25.         source[i][0] = int(source[i - 1][0]) + int(source[i][0])
    
26. 
    
27.     # 动态规划思想
    
28.     for i in range(1, len(source)):
    
29.         for j in range(1, len(source[i])):
    
30.             if j == len(source[i]) - 1:
    
31.                 source[i][j] = int(source[i - 1][j - 1]) + int(source[i][j])
    
32.             else:
    
33.                 source[i][j] = max(int(source[i - 1][j]) + int(source[i][j]),int(source[i - 1][j - 1]) + int(source[i][j]))
    
34. 
    
35.     # 求最后一行的最大值
    
36.     return max(source[len(source) - 1])
    
37. 
    
38. if __name__ == "__main__":
    
39.     print(maxSum())

复制代码

yyb15

datastr="""75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"""
data=datastr.split(' ')
data=[int(i) for i in data]
linenum=1
import math
numcount=int(math.floor(math.sqrt(len(data)*2)))
print('numcount',numcount)
sumall=0
for i in range(1,numcount+1):
    print('i',i)
    print('linenum',linenum)
    maxval=0
    for j in range(1,linenum+1):
        print('j',j)
        if linenum==1:
            maxval=data[0]
        else:
            if(data[(linenum-1)*(linenum)/2+j-1]>maxval):
                maxval=data[(linenum-1)*(linenum)/2+j-1]
    print(maxval)
    linenum+=1
    sumall=sumall+maxval
print(sumall)

yyb15

1313