Re: [ACM ] 想請問524

看板C_and_CPP (C/C++)作者bleed1979 (十三)時間16年前 (2009/03/29 09:36)推噓2(2推 0噓 1→)

留言3則, 2人參與討論串2/2 (看更多)

※ 引述《JLR521 (離開這傷心地)》之銘言： : Q524: Prime Ring Problem : 這題好像可以用 brute force, backtracking, number theory, sieve. : 等方法解決，我想請問backtracking該如何著手? 謝謝! 先大概看一下程式碼：http://rafb.net/p/WrgNQU68.html 你應該可以很明顯的看到這個table, 誰和誰加是primes則設1 /* 0 1 2 3 4 5 6 7 8 9 10111213141516 */ {0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0}, /*0*/ {0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1}, /*1*/ {0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0}, /*2*/ {0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1}, /*3*/ {0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0}, /*4*/ {0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0}, /*5*/ {0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0}, /*6*/ {0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1}, /*7*/ {0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0}, /*8*/ {0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0}, /*9*/ {0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0}, /*10*/ {0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0}, /*11*/ {0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0}, /*12*/ {0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1}, /*13*/ {0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0}, /*14*/ {0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1}, /*15*/ {0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0} /*16*/ 接下來設一個index陣列紀錄你的目標是找到所有可能為1, 且這些1的index都不超過N 如果找到一半有index超過N, 則pop出這個數, 再從前一個數繼續找下一個數(backtracking) 在自家電腦不設定的話, 遞迴會爆表, 不過 UVa 那裡不會所以你只要確定 N = 8 可以跑出對的結果就可以上傳了附上一個去年寫的非遞迴：http://rafb.net/p/eApGpT83.html Bleed -- World of bleed1979 http://bleed1979.myweb.hinet.net/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.128.48