作者bleed1979 (十三)
看板C_and_CPP
标题Re: [ACM ] 想请问524
时间Sun Mar 29 09:36:33 2009
※ 引述《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
1F：推 JLR521:谢谢，真强，大概懂!!! 03/29 10:17
2F：→ bleed1979:刚才玩了一下 stack要开到320k(64k*5)才跑得完16这组 03/29 10:28
3F：推 JLR521:递回真会吃.... 03/29 10:35