注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

互联网产品经理的窝

梦想社:一个人为了梦想,始终没有停下自己的脚步

 
 
 

日志

 
 

求出从三角形数塔的顶层走到底层的最大值(Project Euler 18)  

2012-11-01 09:16:47|  分类: python |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
从下面这个三角数塔的顶端开始,可以走到下一层与之相邻的数,从顶部到底部能达到的最大和是23。

3
7 4
4 6
8 5 9 3


如上图红色所标记的,3+7+3+9=23。

求出下面三角形数塔从顶层走到底层的最大值:

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


注意:由于只有16384条路径,所以尝试暴力枚举每条路径的方法是可行的。但是,问题67是一个与此相似的题目,而且三角形的行数达到了100,暴力解决是不现实的,因而需要一个好的算法!  ;o)

原作者思路请点击我

triangle =(
    (75,                                                         ),
    (9564,                                                     ),
    (174782,                                                 ),
    (18358710,                                             ),
    (20,  4824765,                                         ),
    (19,  12375,  334,                                     ),
    (88,  27773,  76367,                                 ),
    (9965,  428,  6167092,                             ),
    (414126568340807033,                         ),
    (41487233473237169429,                     ),
    (5371446525439152975114,                 ),
    (701133287773177839681757,             ),
    (91715238171491435850272948,         ),
    (6366,  46889536730731669874031,     ),
    ( 462982723,  970987393385360,  423, ),
)
   

def path(triangle, num):
    s = triangle[0][0]
    col = 0
    for row in xrange(1, len(triangle)):
        if num % 2: col = col + 1
        num = num / 2
        s = s + triangle[row][col]
    return s

print max(path(triangle, n) for n in xrange(016384))


  评论这张
 
阅读(284)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017