狐狸捉兔⼦问题1. 问题描述围绕着⼭顶有10个洞，狐狸想要吃兔⼦，兔⼦说：“可以，但必须找到我，我就藏⾝于这10个洞中，你从10号洞出发，先到1号洞找，第⼆次隔1个洞找，第三次隔2个洞找，以后如此类推，次数不限。
”但狐狸从早到晚进进出出了1000次，仍没有找到兔⼦。
问兔⼦究竟藏在哪个洞⾥？2. 问题分析(1) 把10个洞编上序号：1,2,3,4,5,6,7,8,9,0(2) 狐狸从0号洞出发，第1次在1号洞找；第2次隔1个洞，在3号洞找；第3次隔2个洞，在6号洞找；第4次隔3个洞，在0号洞找；第5次隔4个洞⼝，即在5号洞找；以此类推。
(3) 可见，其实上述问题其实是⼀个等差数列求和问题（⾸项为1，公差为1）。
将求和结果对10取余（求和结果%10），即可得到狐狸每次进去的洞⼝号。
(4) 如下图所⽰，仔细观察可以发现，如果狐狸连续两次都进⼊出发洞⼝（0号洞），表明接下来进⼊洞⼝的顺序与之前的顺序相同！因此遇到连续两次都进⼊出发洞⼝的情况，即可停⽌寻找，因为接下来只是重复之前找过的洞⼝。
3. 算法描述(1) ⾸项为1，公差为1的等差数列求和公式：n*(n+1)/2，n为寻找的次数(2) 狐狸每次进⼊的洞⼝号为：(n*(n+1)/2)%10，对10取余是因为有10个洞⼝(3) 设x为寻找的次数，连续两次进⼊都是出发时的洞⼝（0号洞），可停⽌寻找。
设HOLENUM为洞⼝的个数，本例是10即第x-1次：((x-1)*(x-1+1)/2)%HOLENUM == 0第x次：(x*(x+1)/2)%HOLENUM == 0⼀般的，x = 2*HOLENUM。
即如果洞⼝有10个，则需要找20次，就会在遇到连续两次进⼊出发的洞⼝（本例是第19次和第20次）特殊的，如果HOLENUM是(2^k +1)，则 x = HOLENUM，(k = 0,1,2,3......)。
即如果洞⼝有15个，则只需找15次，就会遇到连续两次进⼊出发时的洞⼝（第14次和第15次）(4) 可见，该算法的时间复杂度与洞⼝的个数有关，具体的时间复杂度为Θ(n)4. 代码实现1 #include <stdio.h>2#define HOLENUM 1034void FindRibbit(int Hole[HOLENUM]);56int main()7 {8int hole[HOLENUM] = {0}; // 10个⼭洞9 FindRibbit(hole);10return0;11 }1213void FindRibbit(int Hole[HOLENUM])14 {15int i = 0;16int currenthole = 0, nexthole = 0;17for(i = 1; i <= 2 * HOLENUM; ++i)18 {19 currenthole = (currenthole + i) % HOLENUM; // 当前进去的⼭洞20 Hole[currenthole % HOLENUM] = 1;21 nexthole = (currenthole + i + 1) % HOLENUM; // 下⼀次进去的⼭洞2223if(currenthole == 0 && nexthole == 0) // 如果连续两次进去的⼭洞都是出发时的洞⼝，则接下来的进洞顺序与前⾯的顺序重复，故可以跳出循环24break; // 本例是从10号(即0号)洞⼝出发25 }2628for(i = 0; i < HOLENUM; ++i) // 输出兔⼦可能躲藏的洞⼝29 {30if(Hole[i] == 0)31 printf("the ribbit may be in %d hole\n", i);32 }33 }5. 测试结果the ribbit may be in2 hole the ribbit may be in4 hole the ribbit may be in7 hole the ribbit may be in9 hole。
