鱼C论坛

 找回密码
 立即注册
查看: 4475|回复: 11

[技术交流] 小练习:20160523 找出从三角形顶端走到底端的最大和

[复制链接]
发表于 2016-5-23 10:00:00 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 冬雪雪冬 于 2016-5-30 21:00 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。
什么是欧拉计划: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 上传





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


本帖被以下淘专辑推荐:

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

使用道具 举报

发表于 2016-5-23 10:56:43 | 显示全部楼层
本帖最后由 caobynk 于 2016-5-23 11:13 编辑
  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. from functools import reduce
  32. num = 2**1000
  33. num = list(str(num))
  34. print(reduce(lambda x,y: int(x)+int(y), num))
复制代码

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-23 12:35:57 | 显示全部楼层
本帖最后由 holdme 于 2016-5-24 14:32 编辑

这道题挺有趣的:
  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. for i in range(1,15):
  20.     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]))]

  21. print('最大总和为:%s'%str(tri[0]))
  22. 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荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-23 20:34:47 | 显示全部楼层
  1. print(sum(int(x) for x in list(str(2**1000))))
复制代码

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
冬雪雪冬 + 2 + 2 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-24 00:36:59 | 显示全部楼层
  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. data = data.split()

  19. lst = [[] for i in range(15)]
  20. for i in range(15):
  21.     j = i
  22.     while j+1:
  23.         lst[i].append(int(data.pop(0)))
  24.         j -= 1

  25. for i in reversed(range(14)):
  26.     for j in range(i+1):
  27.         lst[i][j] +=   lst[i+1][j] if lst[i+1][j] > lst[i+1][j+1] else lst[i+1][j+1]

  28. 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荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-24 11:15:39 | 显示全部楼层
本帖最后由 小剑剑 于 2016-5-24 11:34 编辑

懒惰的斑猪,竟然贴图片
  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)
复制代码

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-24 15:29:43 | 显示全部楼层
本帖最后由 bacon6581 于 2016-5-24 15:33 编辑
  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. a=num.split('\n')
  19. b=[]
  20. c=[]
  21. for i in a:
  22.     b=i.split()
  23.     c.append(b)
  24.    
  25. value_max=0
  26. i_max=0
  27. for k in range(0,16385):
  28.     i=k
  29.     value=75
  30.     m=0
  31.     for j in range(1,15):
  32.         if i%2 == 1:
  33.             m+=1
  34.         i>>=1
  35.         
  36.         value+=int(c[j][m])
  37.     if value>value_max:
  38.         value_max=value
  39.         i_max=k
  40. print('最大值:'+str(value_max))
  41. print('路径:'+str(bin(i_max)))
  42. print('需时:'+str(time()-start))

  43. #####################
  44. print('附加题:')

  45. start=time()
  46. a=str(2**1000)
  47. value=0
  48. for i in a:
  49.     value+=int(i)
  50. print('值:'+str(value))
  51. print('需时:'+str(time()-start))
复制代码


1.jpg
165133zs8bl0susmaz3b89.png

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-25 11:04:04 | 显示全部楼层
本帖最后由 DingRan 于 2016-5-25 11:18 编辑

严重支持
  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. def func(path):
  18.     j = 0
  19.     s = 75
  20.     for i in range(14):
  21.         j += int(path[i])
  22.         s += int(a[i][j])
  23.     return s

  24. maxs = 0
  25. for num in range(2**14):
  26.     path = str(bin(num))[2:].rjust(14,'0')
  27.     s = func(path)
  28.     if s>maxs:
  29.         maxs = s
  30. print('最大总和:%d'%maxs)

  31. print('附加题:%d'%sum([int(each) for each in str(2**1000)]))
复制代码

运行结果
  1. >>>
  2. 最大总和:1074
  3. 附加题:1366
  4. >>>
复制代码

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

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-26 11:48:59 | 显示全部楼层
  1. import copy
  2. import time

  3. a = 100
  4. b = 0
  5. while a:
  6.     t1 = time.time()
  7.     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],
  8.             [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],
  9.             [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],
  10.             [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
  11.     for i in range(1, 15):
  12.         lt = copy.copy(data[i])
  13.         for j in range(i):
  14.             data[i][j] = max(data[i-1][j] + lt[j], data[i][j])
  15.             data[i][j+1] = max(data[i-1][j] + lt[j+1], data[i][j+1])
  16.     t2 = time.time()
  17.     a -= 1
  18.     b += t2 - t1
  19. print('最大值是:', max(data[-1]))
  20. print('运行100次所需的时间:', b)


  21. #附加题
  22. j = 100
  23. t = 0
  24. while j:
  25.     t3 = time.time()
  26.     r = 0
  27.     a = str(2**1000)
  28.     for i in a:
  29.         r += int(i)
  30.     t4 = time.time()
  31.     t += t4 - t3
  32.     j -= 1
  33. print('2^1000的各位数和:', r)
  34. print('附加题运行100次所需的时间:', t)
复制代码


运行结果是:
  1. 最大值是: 1074
  2. 运行100次所需的时间: 0.0250246524810791
  3. 2^1000的各位数和: 1366
  4. 附加题运行100次所需的时间: 0.01902151107788086
复制代码

评分

参与人数 1荣誉 +7 鱼币 +7 收起 理由
冬雪雪冬 + 7 + 7 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-5-26 19:55:53 | 显示全部楼层
  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.     source = []
  19.     for i in list:
  20.         source.append(i.strip().split(' '))

  21.     # 初始化第一列
  22.     for i in range(1, len(source)):
  23.         source[i][0] = int(source[i - 1][0]) + int(source[i][0])

  24.     # 动态规划思想
  25.     for i in range(1, len(source)):
  26.         for j in range(1, len(source[i])):
  27.             if j == len(source[i]) - 1:
  28.                 source[i][j] = int(source[i - 1][j - 1]) + int(source[i][j])
  29.             else:
  30.                 source[i][j] = max(int(source[i - 1][j]) + int(source[i][j]),int(source[i - 1][j - 1]) + int(source[i][j]))

  31.     # 求最后一行的最大值
  32.     return max(source[len(source) - 1])

  33. if __name__ == "__main__":
  34.     print(maxSum())
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5 热爱鱼C^_^

查看全部评分

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

使用道具 举报

发表于 2016-6-2 14:31:55 | 显示全部楼层
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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-6-2 14:34:51 | 显示全部楼层
1313
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-28 16:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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