Re: [ACM ] 想請問524

[bleed1979 (十三)]

※ 引述《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
推 JLR521:謝謝，真強，大概懂!!!
→ bleed1979:剛才玩了一下　stack要開到320k(64k*5)才跑得完16這組
推 JLR521:遞迴真會吃....