Python3 欧拉计划 问题16-20

EulerProject.png

问题11-15参见：http://www.jianshu.com/p/c02f0a54052c

16、幂的数字和

  2^15=32768，32768的各位数字之和为 3 + 2 + 7 + 6 + 8 = 26。计算2^1000的各位数字之和。

Python3解答

fan=sum(int(i) for i in str(2**1000))
print(fan)
答案：1366

17、英文字母个数

  把1到5写成英文单词，分别是：one, two, three, four, five，这些单词一共用了3 + 3 + 5 + 4 + 4 = 19个字母。把1到1000都写成英文单词，共用多少字母。【注： 不要算上空格和连字符。例如，342（three hundred and forty-two）包含23个字母，而115（one hundred and fifteen）包含20个字母。单词“and”的使用方式遵循英式英语的规则】

Python3解答

an_dict={0:'',1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',
         8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',
         14:'fourteen',15:'fifteen',16:'sixteen',17:'seventeen',18:'eighteen',
         19:'nineteen',20:'twenty',30:'thirty',40:'forty',50:'fifty',60:'sixty',
         70:'seventy',80:'eighty',90:'ninety',100:'hundred',1000:'onethousand'}#数字英文字典
fan=[]
for i in range(1,1001):
    if i<=20:
        fan.append(an_dict[i])#不大于20都是固定的
    elif i>20 and i<=100:
        if i==100:
            fan.append('onehundred')#表示100
        else:
            fan.append(str(an_dict[int(i/10)*10])+str(an_dict[i-int(i/10)*10]))
    else:
        if i==1000:
            fan.append(an_dict[1000])
        else:
            if i-int(i/100)*100<=20 and i-int(i/100)*100>0 :
                fan.append(str(an_dict[int(i/100)])+str(an_dict[100])+
                           str('and')+str(an_dict[i-int(i/100)*100]))
            elif i-int(i/100)*100==0:
                fan.append(str(an_dict[int(i/100)])+str(an_dict[100]))
            else:       fan.append(str(an_dict[int(i/100)])+str(an_dict[100])+str('and')+str(an_dict[i-int(i/100)*100-(i-int(i/10)*10)])+str(an_dict[i-int(i/10)*10]))
#开始计数
fanan=''
for i in fan:
    if i!='':
        fanan+=i
print(len(fanan))
答案：21124

18、最大路径和(基础版)

  从下图三角形的顶端出发，不断移动到在下一行与其相邻的元素(例如数字7只能移动到下一行的2或者4，而不能到达6)，得到的最大路径和(红色数字表示的路径)是23。

1.png

  如上图，最大路径和为 3 + 7 + 4 + 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条路径，通过尝试所有的路径来解决问题是可行的。但是如果三角形变大，暴力破解将不能解决，而需要一个更加聪明的办法】

Python3解答

#动态规划的思想解决
#可参见：http://www.jianshu.com/p/558294dae12e
import copy#引入复制的包
#读取数据
fan=open(r'C:\Users\GWT9\Desktop\secries.txt')
an=[]#存储数据
weizhi=[]#存储位置，用于记录经过的数字的坐标
for i in range(15):
    an.append([])
    weizhi.append([])
    x=fan.readline()
    for j in range(15):
        try:
            an[i].append(int(x[j*3:(j*3)+2]))
            weizhi[i].append([[i,j]])
        except ValueError:
            pass
fan.close()
copyan=copy.deepcopy(an)#深度复制，记录经过的数字需要用到
#根据值得大小取坐标的函数
def GetCoordinate(shuzu,hang,lie):
    if shuzu[hang][lie]>shuzu[hang][lie+1]:
        return [hang,lie]
    else:
        return [hang,lie+1]
#开始计算
for ii in range(len(an)-2,-1,-1):
    for j in range(len(an[ii])):
        ff=GetCoordinate(an,ii+1,j)
        weizhi[ii][j]+=[weizhi[ff[0]][ff[1]]][0]#添加数字比较大的坐标  
        an[ii][j]=max(an[ii+1][j],an[ii+1][j+1])+an[ii][j]#选择数字和比较大的路径

record=[]#根据记录的坐标，选择数字
for ii in weizhi[0][0]:
    record.append(copyan[ii[0]][ii[1]])
print(record)#经过的数字列表，从顶端开始
#[75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93]
#最大的路径和
print(an[0][0])
答案：1074

19、星期日个数

  1900年1月1日是星期一；天数是30天的月份有四、六、九、十一，剩下的月份除了二月，其他都是31天；闰年的二月有29天，平年的二月是28天；闰年指的是能够被4整除却不能被100整除的年份，或者能够被400整除的年份。
  在二十世纪（1901年1月1日到2000年12月31日）中，有多少个月的1号是星期日。

Python3解答

an_month=['Jan','Feb','Mar','Apr','May','Jun','Jul','Aug','Sep','Oct','Nov','Dec']
def year_day(year):#判断一年的天数
    if year%400==0:
        day=366
    elif year%4==0 and year%100!=0:
        day=366
    else:
        day=365
    return day

def month_day(year,an_mo):#判断一年中一个月的天数字典
    day_dict={}
    for i in an_mo:
        if i=='Apr' or i=='Jun' or i=='Sep' or i=='Nov':
            day_dict[i]=30
        elif i=='Feb' and year_day(year)==366:
            day_dict[i]=29
        elif i=='Feb' and year_day(year)==365:
            day_dict[i]=28
        else:
            day_dict[i]=31
    return day_dict

anan_fan=[]#记录天数序列
for i in range(1901,2001):
    gh=month_day(i,an_month)
    for jjj in an_month:
        anan_fan.append(gh[jjj])
anan_fan.insert(0,year_day(1900))#天数序列加上1900年的天数
Sunday=0#记录1号是星期天
days=1#距离1900年1月1日的天数
for day in anan_fan:
    days+=day
    if days%7==0:#只要距离1900年1月1日的天数是7的倍数，这个月的第一天就是星期日
        Sunday+=1
print(Sunday)
答案：171

20、阶乘的数字之和

  n! 表示的是 n × (n − 1) × … × 3 × 2 × 1。例如：10! = 10 × 9 × … × 3 × 2 × 1 = 3628800，所以10的阶乘的数字之和是 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27。
  求出100!的各位数字和。

Python3解答

def an_product(n):#计算阶乘
    nu=1
    for i in list(range(1,n+1)):
        nu*=i
    return nu
print(sum(int(i) for i in str(an_product(100))))
答案：648

持续更新，欢迎讨论，敬请关注！！！