趣味编程：狐狸捉兔子
问题：围绕着山顶有N个洞（编号为1...N），狐狸要吃兔子，兔子说：“可以，但必须找到我，?我就藏身于这N个洞中，你从N号洞出发，先到１号洞找，第二次隔１个洞找，第三次隔２个洞找，以后如此类推，次数不限。”狐狸就这样一直找下去，最终累死在山顶。。。。。问兔子究竟藏在哪个洞里？
输入：洞的个数N
输出：所在兔子可能的藏身之处（洞的编号）
[解决办法]
unsigned int n; for(;;){ do{ cin>> n; }while(! n); unsigned int * v = new unsigned int [n]; unsigned int iMax; if(n%2) iMax = n ; else iMax = n + n; for(unsigned int x = 0; x < iMax;++x){ v[(x *(x + 3)/2) % n] = 1; //cout<<x *(x + 3)/2<<"/"<<n<<"-"<<(x *(x + 3)/2) % n<<" "; } //cout<<endl; bool bMark = false; for(unsigned int x = 0; x < n;++x){ if(! v[x]){ bMark = true; break; } } if(bMark){ cout<<n<<"符合条件的"<<endl; for(unsigned int x = 0; x < n;++x){ if(!v[x]) cout<<x + 1<<" "; } cout<<endl; } else{ cout<< n<<"没有符合条件的"<<endl; } //cout<<endl; delete [] v; }
[解决办法]
我举个小例子。
N = 3的时候
兔子只要躲在2号洞，就是安全的。狐狸永远到达不了2号洞。至于为什么，你用手算一下就知道了。
而你的代码呢？对于N=3的情况，
由于2号洞不会到达，因此flag[2]永远等于0，所以count 永远不会等于0，导致循环永远不会退出。
直到当n非常非常大达到四万多时，将导致 pathLen = (n + 1)*n/2 的计算溢出 int 。才可能得出一些不可预料的数字，以致于让count = 0才结束。
你以为是运行时间不够长？ 我告诉你，错了，时间够长只是导致你计算溢出，溢出有可能让你终止循环，也有可能让你程序崩溃，不信？ 你自己试试。
[解决办法]
11L是对的，解释一下：
容易看出狐狸找洞的编号序列为a_k=k*(k+1)/2 mod N, 如果a_k=0，洞的编号为N，不为0的话a_k就是洞的编号
当N为奇数时，令k=N-1就得到a_k=0，也就是说寻找N-1次必回到编号为N的洞中，接下去的序列是跟前面重复的。
所以狐狸可以找到的洞的编号就是a_1,a_2,...,a_(N-1),这个编号数目比洞的数目N少（有可能不止小1）,也就是说N为奇数的时候这样的洞是肯定存在的。
当N为偶数时，令k=2N-1，同样发现洞的编号只可能在a_1,a_2,...,a_(2N-1)这2N-1个数中产生，这样有可能无解，例如N=4，兔子不管怎么藏都不行的。
按照N的奇偶性，线性时间内就可以找出狐狸能找到的所有洞的编号