题目43：找出所有具有异常子串整除性的pandigital数之和

jerryxjr1220

迷雾少年 发表于 2016-8-30 19:04
1406357289
1430952867
1460357289

答案应该是对的，但是我换了一种算法，不要穷举所有数，不然效率太低。
我是生成pandigital，然后依次判断，27.3秒搞定。

1. ['4130952867', '1430952867', '4160357289', '4106357289', '1460357289', '1406357289']
   
2. [Finished in 27.3s]

复制代码

1. def getPan(n):
   
2.         if n == 2:
   
3.                 return ['210','120','102','201','021','012']
   
4.         if n>2:
   
5.                 pan = getPan(n-1)
   
6.                 length = len(pan[0])
   
7.                 pannew = []
   
8.                 for each in pan:
   
9.                         pannew.append(str(n)+str(each))
   
10.                         pannew.append(str(each)+str(n))
    
11.                         for j in range(1,length):
    
12.                                 pannew.append(str(each)[:j]+str(n)+str(each)[j:])
    
13.                 return pannew
    
14. 
    
15. def judge(plist):
    
16.         prime = [2,3,5,7,11,13,17]
    
17.         returnlist = []
    
18.         for each in plist:
    
19.                 if each[0] == '0':
    
20.                         pass
    
21.                 else:
    
22.                         flag = 1
    
23.                         for j in range(1,8):
    
24.                                 if each[j] == '0':
    
25.                                         if int(each[j+1:j+3]) % prime[j-1] != 0:
    
26.                                                 flag = 0
    
27.                                                 break
    
28.                                 else:
    
29.                                         if int(each[j:j+3]) % prime[j-1] != 0:
    
30.                                                 flag = 0
    
31.                                                 break
    
32.                         if flag == 1:
    
33.                                 returnlist.append(each)
    
34.         return returnlist
    
35. 
    
36. plist = getPan(9)
    
37. plist = judge(plist)
    
38. print (plist)

复制代码