数模论坛

 找回密码
 注-册-帐-号
搜索
热搜: 活动 交友 discuz
查看: 3110|回复: 7

小题之2

[复制链接]
发表于 2004-3-17 17:26:28 | 显示全部楼层 |阅读模式
[狼追兔子问题]
一座山周国有n个洞,顺时针编号为0,1,2,…n。而一只狼从0号洞开始,顺时针方向计数, 每遇到m个洞就进洞找兔子。例如n=5,m=3,狼经过的洞依次为0,3,1,4,2, 0。
试问兔子有没有幸免的机会?如果有,该藏在哪儿?

不要用循环线性表。
发表于 2004-3-31 06:14:48 | 显示全部楼层
 楼主| 发表于 2004-3-17 20:51:40 | 显示全部楼层
对n=5,m=3的情形,洞口号分别为0,1,2,3,4,m=3,说明狼隔两个洞口进去一次,问羊有没有幸存的机会?
发表于 2004-3-19 17:50:51 | 显示全部楼层
也就是类似,一群人站一圈循环报数,报的是m的倍数的出局。
 楼主| 发表于 2004-3-20 00:01:10 | 显示全部楼层
不,和报数的约瑟夫问题还有区别。
不好意思,可能我说的不太清楚,或许配张图就好了。
对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很大的情况,循环链表复杂度比较大
 楼主| 发表于 2004-3-22 06:25:51 | 显示全部楼层
我给点提示
这题和数论关系很大
发表于 2004-3-22 06:33:17 | 显示全部楼层
#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);
    }
}
 楼主| 发表于 2004-3-22 07:18:50 | 显示全部楼层
嗯,楼上的做法不错。

我来说说用数论怎么解这东西:
(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)}外的洞躲藏。
您需要登录后才可以回帖 登录 | 注-册-帐-号

本版积分规则

小黑屋|手机版|Archiver|数学建模网 ( 湘ICP备11011602号 )

GMT+8, 2024-11-27 06:27 , Processed in 0.052793 second(s), 18 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表