小练习：20170229 找出唯一具有循环性质的6个四位数定形数集合的元素和

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即2.27 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序



题目：

三角形数，四角形数，五角形数，六角形数，七角形数和八角形数都是定形数，他们分别由以下公式产生：

                               
登录/注册后可看大图

三个四位数形成的有序集合: 8128, 2882, 8281,有三个有趣的性质：

1. 这个集合是循环的：每个数的后两位数是下一个数的前两位数，包括第三个和第一个的关系。
2. 三种定形数中的每一种都能被这三个数中的一个不同的数代表：三角形数

                               
登录/注册后可看大图

, 四角形数

                               
登录/注册后可看大图

, 和五角形数

                               
登录/注册后可看大图

。
3. 这是唯一具有以上性质的四位数的集合。

找出唯一的一个六个四位数的循环集合，使得从三角形数到八角形数中的每一种都能由该集合中的一个不同的数代表。

求这个集合中元素之和。

jerryxjr1220

这题其实还是一道搜索算法题，当然如上周所说的用“深度优先”，“广度优先”和“A*算法”都能解决。

我就用A*算法吧，程序简单，效率也不低。

思路很简单，先建立从三角数到八角数所有的候选数列表，做成一个二维数组。
然后从第一层出发（假设为三角数），然后依次搜索下一层，看能否找到匹配的数，如果可以则加入候选列表，以此类推。列表从后往前开始pop（）
代码：

1. #coding:utf-8
   
2. import time
   
3. start = time.time()
   
4. lists = [
   
5. [str(int(n*(n+1)/2)) for n in range(200) if 1000<=n*(n+1)/2<10000],
   
6. [str(int(n*n)) for n in range(200) if 1000<=n*n<10000],
   
7. [str(int(n*(3*n-1)/2)) for n in range(200) if 1000<=n*(3*n-1)/2<10000],
   
8. [str(int(n*(2*n-1))) for n in range(200) if 1000<=n*(2*n-1)<10000],
   
9. [str(int(n*(5*n-3)/2)) for n in range(200) if 1000<=n*(5*n-3)/2<10000],
   
10. [str(int(n*(3*n-2))) for n in range(200) if 1000<=n*(3*n-2)<10000]]
    
11. 
    
12. def ispair(s1,s2):
    
13.         return True if s1[2:]==s2[:2] else False
    
14. 
    
15. queue = [[each,[0]] for each in lists[0]]
    
16. while len(queue) >0:
    
17.         q = queue.pop()
    
18.         row = len(q)-1
    
19.         if row == 6:
    
20.                 if ispair(q[-2],q[0]):
    
21.                         print('Bingo!', q[:-1])
    
22.                         break
    
23.         else:
    
24.                 for i in range(1,6):
    
25.                         if i in q[-1]: continue
    
26.                         for p in lists[i]:
    
27.                                 if ispair(q[-2],p) and i not in q[-1]:
    
28.                                         l = [e for e in q[-1]]
    
29.                                         l.append(i)
    
30.                                         queue.append(q[:-1]+[p]+[l])
    
31.                                         break
    
32. print('Time used: %.3f sec' % (time.time()-start))

复制代码

输出：
Bingo! ['8256', '5625', '2512', '1281', '8128', '2882']
Time used: 0.015 sec

飘飞的白杨

递归

1. import sys
   
2. from time import time
   
3. 
   
4. ttt = time()
   
5. 
   
6. def getlist(lam):
   
7.     '''获取x角形数的列表'''
   
8.     l = []
   
9.     for i in range(1, 1000):
   
10.         n = lam(i)
    
11.         if n < 1000: continue
    
12.         if n >= 10000: return l
    
13.         l.append(n)
    
14. 
    
15. def progrem61_2(numbers):
    
16.     if len(numbers) == 6 and numbers[-1] % 100 == numbers[0] // 100:
    
17.         print(numbers, sum(numbers), "\ntime:%.5fs"%(time()-ttt))
    
18.         sys.exit()
    
19.     for i in range(6):
    
20.         if flag[i]: continue
    
21.         flag[i] = True
    
22.         for j in p[i]:
    
23.             if j // 100 == numbers[-1] % 100:
    
24.                 progrem61_2(numbers+[j])
    
25.         flag[i] = False
    
26. 
    
27. def progrem61_1():
    
28.     flag[-1] = True
    
29.     # 八角形数最少，从八角形数中选择第一个数
    
30.     for i in p8:
    
31.         progrem61_2([i])
    
32. 
    
33. p3 = getlist(lambda n: n * (n + 1) // 2)
    
34. p4 = getlist(lambda n: n * n)
    
35. p5 = getlist(lambda n: n * (3 * n - 1) // 2)
    
36. p6 = getlist(lambda n: n * (2 * n - 1))
    
37. p7 = getlist(lambda n: n * (5 * n - 3) // 2)
    
38. p8 = getlist(lambda n: n * (3 * n - 2))
    
39. p = [p3, p4, p5, p6, p7, p8]
    
40. flag = [False] * 6 # 标志数组，用于判断是否遍历过
    
41. progrem61_1()

复制代码

余欲渔

for用的太多，自己都有点绕了

1. def fen(jh):          #把xxxx分成[xx,xx]的形式，4位数分成两个两位数，排除后面的两位数小于10的情况
   
2.     ls=[]
   
3.     for i in jh:
   
4.         if i%100>9:
   
5.             ls.append([i//100,i%100])
   
6.     return ls
   
7. 
   
8. jhsan,jhsi,jhwu,jhliu,jhqi,jhba=[],[],[],[],[],[]
   
9. 
   
10. for x in range(15,150):#根据题目的公式，把6种形式的4位数分别放入对应集合
    
11.     if x*(x+1)/2>1000 and x*(x+1)/2<9999      :jhsan.append(int(x*(x+1)/2))
    
12.     if x**2>1000 and x**2<9999                :jhsi.append(x**2)
    
13.     if x*(3*x-1)/2>1000 and x*(3*x-1)/2<9999  :jhwu.append(int(x*(3*x-1)/2))
    
14.     if x*(2*x-1)>1000 and x*(2*x-1)<9999      :jhliu.append(x*(2*x-1))
    
15.     if x*(5*x-3)/2>1000 and x*(5*x-3)/2<9999  :jhqi.append(int(x*(5*x-3)/2))
    
16.     if x*(3*x-2)>1000 and x*(3*x-2)<9999      :jhba.append(x*(3*x-2))
    
17. 
    
18. jhsan,jhsi,jhwu,jhliu,jhqi,jhba=fen(jhsan),fen(jhsi),fen(jhwu),fen(jhliu),fen(jhqi),fen(jhba) #6个集合的数分裂一下
    
19. cs=[[],[],[],[],[],[]]#数字分别带入之后测试是否满足条件的列表
    
20. huizong0=[jhsan,jhsi,jhwu,jhliu,jhqi,jhba]#汇总6个集合的数，huizong0-5决定第一个数到第六个数的取值范围
    
21. for s0 in huizong0:                       #huizong0里面是第一个数的可选范围
    
22.     huizong1=huizong0.copy()
    
23.     huizong1.remove(s0)
    
24.     for s1 in huizong1:                   #huizong1里面是把huizong0里面剔除一个集合之后的汇总，也就是第二个数的备选范围
    
25.         huizong2=huizong1.copy()
    
26.         huizong2.remove(s1)
    
27.         for s2 in huizong2:               #下面直到huizong5都是以此类推
    
28.             huizong3=huizong2.copy()
    
29.             huizong3.remove(s2)
    
30.             for s3 in huizong3:
    
31.                 huizong4=huizong3.copy()
    
32.                 huizong4.remove(s3)
    
33.                 for s4 in huizong4:
    
34.                     huizong5=huizong4.copy()
    
35.                     huizong5.remove(s4)   
    
36.                     for s5 in huizong5:
    
37.                         for cs[0] in s0:          #从这里开始是真正的验证排序是否符合题目要求，符合要求之后每两个两位数合成一个4位数
    
38.                             for cs[1] in s1:
    
39.                                 if cs[0][1]!=cs[1][0]:continue
    
40.                                 for cs[2] in s2:
    
41.                                     if cs[1][1]!=cs[2][0]:continue
    
42.                                     for cs[3] in s3:
    
43.                                         if cs[2][1]!=cs[3][0]:continue
    
44.                                         for cs[4] in s4:
    
45.                                             if cs[3][1]!=cs[4][0]:continue
    
46.                                             for cs[5] in s5:
    
47.                                                 if cs[4][1]!=cs[5][0]:continue
    
48.                                                 if cs[5][1]==cs[0][0]:
    
49.                                                     cs=[cs[0][0]*100+cs[0][1],cs[1][0]*100+cs[1][1],cs[2][0]*100+cs[2][1],cs[3][0]*100+cs[3][1],cs[4][0]*100+cs[4][1],cs[5][0]*100+cs[5][1]]
    
50.                                                     print(cs,sum(cs))
    
51.                                                     exit()

复制代码

1. == RESTART: C:\Users\ASUS\AppData\Local\Programs\Python\Python35-32\test.py ==
   
2. [8256, 5625, 2512, 1281, 8128, 2882] 28684
   
3. >>>

复制代码

Craigyu

数不多，就把数全列出来一个一个找。找到下一个添加进表，找不到下一个则将前一个POP掉，长度为6时比较第一个和最后一个数，为TRUE则结束。
[1281, 8128, 2882, 8256, 5625, 2512]
28684
0.0312192440032959

1. from time import time
   
2. start = time()
   
3. 
   
4. lst3 = []
   
5. lst4 = []
   
6. lst5 = []
   
7. lst6 = []
   
8. lst7 = []
   
9. lst8 = []
   
10. 
    
11. for n in range(45, 141):
    
12.     lst3.append(int(n * (n + 1)/2))
    
13. for n in range(32, 100):
    
14.     lst4.append(n * n)
    
15. for n in range(26, 82):
    
16.     lst5.append(int(n * (3 * n - 1)/2))
    
17. for n in range(23, 71):
    
18.     lst6.append(n * (2 * n - 1))
    
19. for n in range(21, 64):
    
20.     lst7.append(int(n * (5 * n - 3)/2))
    
21. for n in range(19, 59):
    
22.     lst8.append(n * (3 * n - 2))
    
23. 
    
24. lst = [lst3, lst4, lst5, lst6, lst7]
    
25. 
    
26. nums = []
    
27. pls = [8]
    
28. 
    
29. def judge(m, n):
    
30.     if str(m)[2:] == str(n)[:2]:
    
31.         return True
    
32. 
    
33. def polygonal(num):
    
34.     if len(nums) == 6:
    
35.         if judge(nums[-1], nums[0]) == True:
    
36.             return True
    
37.     else:
    
38.         for i in range(5):
    
39.             if i not in pls:
    
40.                 for each in lst[i]:
    
41.                     if judge(num, each) == True:
    
42.                         pls.append(i)
    
43.                         nums.append(each)
    
44.                         flag = polygonal(nums[-1])
    
45.                         if flag != True:
    
46.                             pls.pop()
    
47.                             nums.pop()
    
48.                         else:
    
49.                             return True
    
50. 
    
51. for num in lst8:
    
52.     nums.append(num)
    
53.     if polygonal(num) == True:
    
54.         print(nums)
    
55.         break
    
56.     else: nums.pop()
    
57. print(sum(nums))
    
58. print(time()-start)
    

复制代码

lovesword

这也是真的无聊 每天不是 质数就是 三角数 四角数。。。。旋转的质数，，质数的和 质数的差 质数的乘 质数的商，，python 的算法 就是为了处理质数 的？ 其他的题目都死绝了么？

NiceB

#这是我第一次在fishC论坛发帖，所以如果有什么不正确的地方还希望大佬可以指点一下，尽管我很早就开始看fishC的视频来学习编程，但是我是最近才开始学习的Python，所以代码里面可能有很多令人哭笑不得的地方，，各种变量和函数的命名也不太好，，望谅解
#关于这道题目，我之前没有见到过，也没有参考过网上的答案，，所以我很自知并不是最佳算法，但是我还是要发出来，鼓励一下自己

我的思路是 先把所有的六组定性数算出来然后从这六组数中找出所需要的list
六组（3-8组）定性数的过程并不复杂，这里不再说，具体看代码里面的注释
找出符合要求的数字，我的思路是 这样的， 要找到六个定性数，我先拿一组（比如3组）定性数，然后从这一组里面拿出来一个数字A，然后在剩下的数字里面找到和A首尾相接的数字（比如4组的B），然后在剩下的组（5,6,7,8）里面找和B首尾相接的数字，，直到找出最后一个数字（G），然后验证G是否和A是首尾相接，，
最终结果不会给出每一个数字来自哪组定性数，，还需要额外的过程来得知
上代码：
先贴一下环境：
Microsoft Windows [版本 6.1.7601]
版权所有 (c) 2009 Microsoft Corporation。保留所有权利。

C:\Users\****>python
Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 07:18:10) [MSC v.1900 32 bit (In
tel)] on win32

代码：

1. def findNum(x):                #定义一个算定性数的函数
   
2.         def _res(n):        #计算用的函数
   
3.                 #所有定性数的计算公式可以用这个来代表，，
   
4.                 #如果是x角定性数，那么公式就是n*((x-2)*n+(4-x))/2
   
5.                 #
   
6.                 return int(n*((x-2)*n+(4-x))/2)               
   
7.         _list=[]                #一个空列表用来存一组定性数
   
8.         i=1
   
9.         _tmp=_res(i)        #先算出第一个
   
10.         while _tmp<10000:                #while循环来算出所有小于10000的定性数
    
11.                 #我们所要求的数字并不能用上所有的定性数
    
12.                 #上面的while条件限制了要求的定性数的长度
    
13.                 #因为要求首尾相接的四位数，所以后两位小于10的数字肯定不符合要求
    
14.                 if _tmp>999 and _tmp%100>9:                #排除掉三位以下的和后两位小于10的
    
15.                         _list.append(_tmp)
    
16.                 i+=1
    
17.                 _tmp=_res(i)
    
18.         return _list        #返回的存了一组符合要求定性数的list
    
19. #先把所有的数字算出来再说后面的
    
20. numList=[]                        #在这里我打算把所有的8组定性数存到这个list里面
    
21. for i in range(3,9):
    
22.         numList.append(findNum(i))
    
23. 
    
24.        
    
25. num8=numList.pop()        #这里是文字介绍里面的先拿一组数出来
    
26. 
    
27. 
    
28. 
    
29. def fin(num,ii,mylist):               
    
30. #这个函数用来递归找数，num是首尾相接里面的首
    
31. #ii后面说
    
32. #mylist是（文字介绍里面说的）剩下的数组
    
33.         if len(mylist)==0:
    
34.                 return []
    
35.         else:
    
36.                 for sublist in mylist:                #遍历外层数组拿出一组定性数
    
37.                         for i in sublist:                #遍历内层数组，拿出一个数字
    
38.                                 tmplist=[]+mylist        #先把大数组留个备份，这里不能直接用=赋值
    
39.                                 #首尾相接就是前一个数字对100取余的结果和后一个数字整除100的结果相等
    
40.                                 if (num%100)==(i//100):               
    
41.                                         if len(mylist)==1:                #验证是不是最后一个数字
    
42.                                                 #如果是最后一个数字的话，还需要和A（文字介绍中的）首尾相接
    
43.                                                 #这里的ii就是函数的第二个参数，将来的数字A
    
44.                                                 if i%100!=ii//100:       
    
45.                                                         continue
    
46.                                         tmplist.remove(sublist)        #如果有匹配的值的话，那么这一组定性数都不应该再出现
    
47.                                         _res= [i]+fin(i,ii,tmplist)        #在这里递归
    
48.                                         if len(_res)==len(mylist):        #通过长度来保证这一列数字有六组定性数的成员
    
49.                                                 return _res
    
50.         return []
    
51.                
    
52. for i in num8:
    
53.         resultList=[i]+fin(i,i,numList)
    
54.         if len(resultList)==6:                #只有有结果的resultList的len是6，其他都只有一个
    
55.                 print(sum(resultList))        #打印结果

复制代码

wangzhenas

主要思路就是递归，传递的参数是 （当前值（int）， 已形成的链（list），还剩下哪几种数没找到（set))
把各种计算方法保存为lambda函数，用列表生成式生成5个字典｛前两位：数值｝
findchain函数通过对set做循环找出一条有效的链
耗时：0.01s
答案： 28684
i5-3210M

1. import time
   
2. t = time.time()
   
3. 
   
4. gens = (lambda n: n*n,
   
5.         lambda n: n*(3*n-1)//2,
   
6.         lambda n: n*(2*n-1),
   
7.         lambda n: n*(5*n-3)//2,
   
8.         lambda n: n*(3*n-2))
   
9. 
   
10. num_l = [{gen(i)//100:gen(i) for i in range(1,100) if 1000<gen(i)<10000} for gen in gens]
    
11. 
    
12. def find_chain(num, l=None, sel_set=set(range(len(gens)))):   
    
13.     chain_l = [num] if not l else l
    
14.     if sel_set:
    
15.         for p in sel_set:
    
16.             if num%100 in num_l[p]:
    
17.                 find_chain(num_l[p][num%100], chain_l+[num_l[p][num%100]], sel_set-{p})
    
18.             else:
    
19.                 continue
    
20.     else:
    
21.         if l[-1]%100 == l[0]//100:
    
22.             print(l, sum(l), time.time()-t)
    
23.         
    
24.         
    
25. for value in [n*(n+1)//2 for n in range(200+1) if 1000<n*(n+1)//2<10000]:
    
26.     find_chain(value)   
    

复制代码

aqiang159

题目没看懂