作者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