projectEuler的几个问题

在projectEuler上锻炼，捡了几个把代码贴出来分享一下，有点丑陋~~

Problem24

这里用了一个递归算法，如果不递归的话需要用Jhonson Trotter算法，python代码如下：takes 32secs in my laptop

from time import time
F = time()

a = []
def P22(string,beg,end):
    if beg == end:
        k = ''
        for i in range(end+1):
            k+=string[i]
        a.append(k)
        k = ''
    else:
        for i in range(beg,end+1):
            temp = string[beg];string = string[:beg]+string[i]+string[beg+1:];string = string[:i]+temp+string[i+1:]
            P22(string,beg+1,end)
            temp = string[beg];string = string[:beg]+string[i]+string[beg+1:];string = string[:i]+temp+string[i+1:]

P22('0123456789',0,9)
a.sort()
print a[1000000-1]
E = time()
print 'time:'
print (E-F)

Problem 22读取一个文件，没什么算法好说的，主要是python的优势体现了

def main():
    fp = open('names.txt')
    names = fp.read().split(',')
    names.sort()
    tot = 0
    for index, name in enumerate(names):
        # this is odd,name = "COLIN",why
        s = sum([ord(i)-64 for i in name[1:-1]])
        # print s, index, name, [ord(i)-64 for i in name[1:-1]]
        tot += s * (index+1)
    print tot
main()

Problem11：这个丑陋了

#!/usr/bin/env python
#Author：SigKill
import time
F = time.time()

f = open(r'f:\test.txt','r')
a = []
b = []

for i in f:
    a.append(i.strip().split(' '))
for i in range(len(a)):
    for j in range(len(a[0])):
        a[i][j] = int(a[i][j])
MAX = 0
down4 = right4 = diagright4 = diagleft4 = 0
for line in range(len(a)):
    for colum in range(len(a[0])):
        if line<=15:#可以向下减四
            down4 = reduce(lambda x,y:x*y,([a[i][colum] for i in range(line,line+4)]))
        
        if colum<=15:#可以向右减四
            right4 = reduce(lambda x,y:x*y,([a[line][i] for i in range(colum,colum+4)]))

        if line<=15 and colum<=15:#可做对角线右减
            diagright4 = a[line][colum]* a[line+1][colum+1]*a[line+2][colum+2]*a[line+3][colum+3]

        if line<=15 and colum >=4:#可做对角线左减
            diagleft4 = a[line][colum]* a[line+1][colum-1]*a[line+2][colum-2]*a[line+3][colum-3]
        c = []
        c.append(down4);c.append(right4);c.append(diagright4);c.append(diagleft4)
        max_in = max(c)
        if max_in > MAX:
            MAX = max_in
        down4 = right4 = diagright4 = diagleft4 = 0
print MAX
E = time.time()
print 'time:',E-F
        
                        
                
                        
                
                



Problem17，“读出数字”的题目

from time import time
from random import choice
F = time()
gewei = {1:'one',2:'two',3:'three',4:'four',\
         5:'five',6:'six',7:'seven',8:'eight',9:'nine'}
shiji = {11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'fifteen',\
         16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen'}
jishi = {10:'ten',20:'twenty',30:'thirty',40:'forty',50:'fifty',\
         60:'sixty',70:'seventy',80:'eighty',90:'ninety'}
jibai = {100:'onehundred',200:'twohundred',300:'threehundred',400:'fourhundred',\
         500:'fivehundred',600:'sixhundred',700:'sevenhundred',800:'eighthundred',\
         900:'ninehundred'}
yiqian = 'onethousand'
length = 0
a = 0
for i in range(1,1001):
    if len(str(i)) == 1:
        length += len(gewei[i])

    if len(str(i)) == 2:
        if i%10 == 0:
            length += len(jishi[i])

        else:
            if 11<=i<=19:
                length = length + len(shiji[i])

            else:
                ge = i%10;shi = (i/10)*10
                length = length + len(gewei[ge]) + len(jishi[shi])

    if len(str(i)) == 3:
        if i%100 == 0:#例如300
            length += len(jibai[i])

        if (i%100 != 0 and i%10 == 0):#例如320
            shi = i - (i/100)*100
            bai = i/100
            length = length + len(jibai[100*bai]) + len(jishi[shi]) + 3

        if (i%100 != 0 and i%10 != 0 and i%100/10 != 0):#例如213，567
            ge = i%10
            shi = i%100/10
            bai = i/100
            if 11<=10*shi+ge <=19:
                length = length + len(jibai[bai*100])+len(shiji[10*shi+ge]) + 3
            else:
                length = length + len(jibai[bai*100])+len(jishi[10*shi]) + len(gewei[ge]) + 3

        if (i%100 != 0 and i%10 != 0 and i%100/10 == 0):#例如102
            bai = i/100;ge = i%10
            length = length + len(jibai[100*bai]) + len(gewei[ge]) + 3
    if len(str(i)) == 4:
        length += len(yiqian)
    
print length
E = time()
print 'time:'
print (E-F)





Problem25：OH，Python，pretty NICE！！！要用别的语言，我。。。。。

#!/usr/bin/env python
#Author：SigKill
import time

F = time.time()
a,b = (1,1)
count = 2
while len(str(b)) < 1000:
    count += 1
    print b,count
    a,b = (b,a+b)
print count

E = time.time()
print 'time:',E-F

Problem28

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way？

#!/usr/bin/env python
#Author：SigKill
import time
F = time.time()

SUM = 0
n = 3
i = 2
a = []
while True:
    x = [j for j in range(n,n+3*i+1,i)]#每一拳的数字的步长有这个规律2，4，6，。。。
    for m in x:
        a.append(m)
    
    n = n + 3*i + i + 2 #下一圈开始时的起始起加数字
    i += 2
    if n >= 1001**2: #1001方阵的最右上角数字呦规律可得为1001的二次方
        break
SUM = sum(a)
print SUM + 1#开始是没有计算1
        
E = time.time()
print 'time:',E-F

Problem 35：这个题目要看清题目，所谓的circle primer是对这个数字始终做轮换，我刚开始以为是全排列，浪费时间啊，而且看例子中的37和73可以知道，前面数字轮换得到的结果对后面的没有影响，也就是说数字出现两次也都算，，这个也浪费了我一点时间，好了，代码如下，运行18secs

#!/usr/bin/env python
#Author：SigKill
import time
import math

F = time.time()
a = []
c = []
def P35(num):
    if num < 10:
        pass
    if 10<=num<100:
        a.append(num%10*10+num/10)
    else:
        STR = str(num)
        for i in range(1,len(STR)):
            STR = STR[1:] + STR[0]
            a.append(int(STR))
    return a

def is_primer(n):
    m = int(math.sqrt(n))+1
    for i in range(2,m):
        if n%i == 0:
            return False
    return True
count = 0
m = 1

for i in [x for x in range(2,1000001) if x&1]:
    if is_primer(i):
        b = P35(i)
        for j in b:
            if not is_primer(j):
                m = 0
                break
        if m:
            print i
            count += 1
        
    m = 1
    a = []
                
print count+1 #考虑到2也是
        
E = time.time()
print 'time:',E-F

事实上，可以用筛选法得到一群质数的集合来做这个题目，这样效率会高很多

def generate_primes(max):
    sand = list('00'+'1'*(max-1))
    for x in xrange(int(max**0.5)):
        if sand[x]=='1':
            for y in xrange(2*x,len(sand),x):
                sand[y]='0'
    primes = set(x for x in xrange(max) if sand[x]=='1')
    return primes