小练习：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

# 小练习
data = '''
        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 = data.split()
num = []
for k in range(1, 16):
    num.append(list(map(int, data[int(k*(k-1)/2) : int(k*(k+1)/2)])))
for k in range(2, 16):
    num[k-1][0] = num[k-2][0] + num[k-1][0]
    num[k-1][-1] = num[k-2][-1] + num[k-1][-1]
    if len(num[k-1]) >2 :
        for i in range(1,len(num[k-1])-1):
            num[k-1][i] = max(num[k-2][i-1], num[k-2][i]) + num[k-1][i]
print(max(num[-1]))

# 附加题
from functools import reduce
num = 2**1000
num = list(str(num))
print(reduce(lambda x,y: int(x)+int(y), num))

holdme

这道题挺有趣的：

import time
start = time.clock()
tri = [[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]\
,[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,4,68,89,53,67,30,73,16,69,87,40,31]\
,[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

#由底部向上，逐层寻优
for i in range(1,15):
    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]))]

print('最大总和为：%s'%str(tri[0]))
print('用时%s秒'%str(time.clock()-start))

结果：

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

附加题：

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

结果是：

1366

小火木

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

挥舞乾坤

data ='''
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 = data.split()

lst = [[] for i in range(15)]
for i in range(15):
    j = i
    while j+1:
        lst[i].append(int(data.pop(0)))
        j -= 1

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

print(lst[0][0])

附加题:
方法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:

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

小剑剑

懒惰的斑猪，竟然贴图片

raw_number='''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'''
numlist=raw_number.split('\n')
hie=len(numlist)
for i in range(hie):
      exec("numlist[{0}]=numlist[{0}].split()".format(i))
      exec('''for ii in range(i+1):
           numlist[{0}][ii]=int(numlist[{0}][ii])'''.format(i))
for i in range(hie-2,-1,-1):
      for ii in range(i+1):
            if numlist[i+1][ii]>=numlist[i+1][ii+1]:
                  numlist[i][ii]+=numlist[i+1][ii]
            else:
                 numlist[i][ii]+=numlist[i+1][ii+1]

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

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

bacon6581

from time import time
start=time()
num='''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 14 23'''

a=num.split('\n')
b=[]
c=[]
for i in a:
    b=i.split()
    c.append(b)
    
value_max=0
i_max=0
for k in range(0,16385):
    i=k
    value=75
    m=0
    for j in range(1,15):
        if i%2 == 1:
            m+=1
        i>>=1
        
        value+=int(c[j][m])
    if value>value_max:
        value_max=value
        i_max=k
print('最大值：'+str(value_max))
print('路径：'+str(bin(i_max)))
print('需时：'+str(time()-start))

#####################
print('附加题：')

start=time()
a=str(2**1000)
value=0
for i in a:
    value+=int(i)
print('值：'+str(value))
print('需时：'+str(time()-start))

DingRan

严重支持

a = [
    ['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']
    ]

def func(path):
    j = 0
    s = 75
    for i in range(14):
        j += int(path[i])
        s += int(a[i][j])
    return s

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

print('附加题：%d'%sum([int(each) for each in str(2**1000)]))

运行结果

>>> 
最大总和：1074
附加题：1366
>>> 

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

WylLy

import copy
import time

a = 100
b = 0
while a:
    t1 = time.time()
    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],
            [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,4,68,89,53,67,30,73,16,69,87,40,31],
            [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
    for i in range(1, 15):
        lt = copy.copy(data[i])
        for j in range(i):
            data[i][j] = max(data[i-1][j] + lt[j], data[i][j])
            data[i][j+1] = max(data[i-1][j] + lt[j+1], data[i][j+1])
    t2 = time.time()
    a -= 1
    b += t2 - t1
print('最大值是：', max(data[-1]))
print('运行100次所需的时间：', b)


#附加题
j = 100
t = 0
while j:
    t3 = time.time()
    r = 0
    a = str(2**1000)
    for i in a:
        r += int(i)
    t4 = time.time()
    t += t4 - t3
    j -= 1
print('2^1000的各位数和：', r)
print('附加题运行100次所需的时间：', t)

运行结果是：

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

cold2wind

def maxSum():
    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
             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 4 68 89 53 67 30 73 16 69 87 40 31
             4 62 98 27 23 9 70 98 73 93 38 53 60 4 23'''
    list = data.split("\n")

    source = []
    for i in list:
        source.append(i.strip().split(' '))

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

    # 动态规划思想
    for i in range(1, len(source)):
        for j in range(1, len(source[i])):
            if j == len(source[i]) - 1:
                source[i][j] = int(source[i - 1][j - 1]) + int(source[i][j])
            else:
                source[i][j] = max(int(source[i - 1][j]) + int(source[i][j]),int(source[i - 1][j - 1]) + int(source[i][j]))

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

if __name__ == "__main__":
    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