作者EdisonX (闭上眼的鱼)
站内Prob_Solve
标题[问题] 1~20数列,相邻/头尾和为质数
时间Tue Nov 29 10:16:58 2011
这问题是逛网路时看到的。
1~20 排成一列，使得任二相邻之和为质数，且第一个数与最後一个数之和也为质数。
要找出所有解。
我的想法也点暴力，因任何数最大和只到39，所以先建 39 以下的质数表，
又因相邻之二数必为一奇一偶 (加起来才会是奇数)，所以分二个 array 做 permutation
这样从 20P20 = 2.43E18 降到 (10P10)**2 = 1.32E13，
还是跑很久！
另外的想法是用 bool used[21]={fase};
再进行质数之拆解，像 19 可拆成 1/18 2/17 3/16....
不过想法到这里就卡住了，不知各位版友对於这问题有何想法？
--
If there is no tomorrow,
I want to see u last time.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 180.177.78.41
1F：推 musie:我是会先想列出所有两者一组的和会是质数的配对 11/29 10:24
2F：→ musie:再从中挑出所有数不重复的组合，再串起来 11/29 10:25
3F：推 musie:其实能够挑出来就结束了..根本就不用串 11/29 10:30
我在想我的想法有没有问题。
若挑37去拆的话,有20.17/19.18/18.19/17.20,变 4*9P9*9P9
挑19去拆的话，就变 9*9P9*9P9, 挑哪个质数拆会影响吗？
另请教为何挑出来就结束了?指的是能找到一组解後便能由
Rotation + Reverse 变成其他解,所以不需串吗 ?
谢谢赐教。
4F：→ LPH66:说起来找出相加组合之後这问题就变成汉米尔顿圈问题了... 11/29 15:23
第一次听到汉米尔顿圈，谢谢提供 keyword.
5F：推 musie:数值不大，NPcom就硬干处理 11/29 17:02
听起来像是不好搞的感觉，想说我写的 code 跑非常久，
是不是单纯是我的问题 Orz. 谢谢 musie 大不吝赐教。
※ 编辑: EdisonX 来自: 180.177.78.41 (11/29 19:54)
6F：推 bigpigbigpig:其实只有56组数目需要尝试，这样sample space小很多 11/29 20:42