小题之2

itmwk

[狼追兔子问题]
一座山周国有n个洞，顺时针编号为0，1，2，…n。而一只狼从0号洞开始，顺时针方向计数， 每遇到m个洞就进洞找兔子。例如n＝5，m＝3，狼经过的洞依次为0，3，1，4，2， 0。
试问兔子有没有幸免的机会?如果有，该藏在哪儿?

不要用循环线性表。

chenchanggui

很

itmwk

对n=5,m=3的情形，洞口号分别为0,1,2,3,4，m=3，说明狼隔两个洞口进去一次，问羊有没有幸存的机会？

千年等一回

也就是类似，一群人站一圈循环报数，报的是m的倍数的出局。

itmwk

不，和报数的约瑟夫问题还有区别。
不好意思，可能我说的不太清楚，或许配张图就好了。
对n=5,m=3的情形我解释一下：n＝5，说明绕山按顺时针一圈的这些洞口共5个，并被分别标志为0，1，2，3，4。现在假设羊藏在2号洞，第一次狼进入0号洞，没找到羊，下一次，隔两（即隔m－1）个洞进了3号，再下一次又隔两个洞进1号，之后是4号，最后一次是2号，找到羊了。
在n＝5，m＝3的情况下，狼每个洞都有机会进去，也就说明羊没有幸存的机会。但在有些情况下，有的洞狼一直没进去过，如果羊藏在这样的洞中就可以幸存。
其实也就是要判断对某一个给定的n和m，是否存在狼不会进去的洞，并指出这样的洞。

最好不要用循环链表，对于n很大的情况，循环链表复杂度比较大

itmwk

我给点提示
这题和数论关系很大

donms

#define N 5
#define M 3

int pos[N];

main()
{
    int i = 0;
    for(;;)
    {
        i += M;
        pos[i%N]++;
        if (pos[i%N] > 1) break;
    }
    for(i = 0; i < N; ++i)
    {
        if (pos == 0) printf("%d\t",i);
    }
}

itmwk

嗯，楼上的做法不错。

我来说说用数论怎么解这东西：
（gcd(m,n)表示求m、n的最大公约数）
我们不妨让兔子躲在一号洞。因为若狼能从0号洞到达1号洞，则它必能从1号洞到达2…n-1号洞，兔子难逃厄运。反过来说．若有安全洞，则1号洞就是其中的一个。
再来看狼的运动。狼的第i次运动后的洞址应是(m*5)mod n(i为正整数)。若(m*i)mod n＝1，即狼第i次运动后到达1号洞，则gcd(m,n)＝1。因为若gcd(m,n)＝k>1，则由(m'*k*i)mod(n'*k)＝1，(设m'*k＝m,n'*k＝n)．m'*k*i-[(m'*k*i)/(n'k)]*(n'*k)=1,得出k整除1，与k>1矛盾。而若gcd(m,n)＝1，则那么一定存在i使(m*i)mod n=1,因而兔子幸免的条件为gcd(m,n)>1。在此情况下．它应选择除{i*gcd(m,n)|i=0...(n/gcd(m,n)-1)}外的洞躲藏。