Re: [問題] 1~20數列,相鄰/頭尾和為質數
看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間13年前 (2011/11/29 23:11)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《EdisonX (閉上眼的魚)》之銘言：
: 這問題是逛網路時看到的。
: 1~20 排成一列，使得任二相鄰之和為質數，且第一個數與最後一個數之和也為質數。
: 要找出所有解。
: 我的想法也點暴力，因任何數最大和只到39，所以先建 39 以下的質數表，
: 又因相鄰之二數必為一奇一偶 (加起來才會是奇數)，所以分二個 array 做 permutation
: 這樣從 20P20 = 2.43E18 降到 (10P10)**2 = 1.32E13，
: 還是跑很久！
: 另外的想法是用 bool used[21]={fase};
: 再進行質數之拆解，像 19 可拆成 1/18 2/17 3/16....
: 不過想法到這裡就卡住了，不知各位版友對於這問題有何想法？
dfs，我沒有等他跑完就已經睡著了。
夢中的我現在在打字。
作法不外把1到20可以配對成為prime的number先找出來。
A[1]是跑1到20，同時可以決定A[20]，在A[20]時僅需檢查A[19]
基本上bool used[21]是dfs必備的陣列，用來決定是否重複。
連codepad那裏的顯示都timeout了。
http://codepad.org/fcXlNB4r
http://paste.plurk.com/show/774093/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.123.27
推
11/29 23:39, , 1F
11/29 23:39, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12
