软件工程

本类阅读TOP10

·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八): CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
狼追兔子问题的解答

作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站

这道题的数论解法

这道题在许多教科书上都有,一般是用循环线性表来模拟狼的行动,找到安全的洞。但是,对于n很大的情况,一来线性表要占用很大的空间,二来循环搜索要花费很多时间,因此这种算法效率很低。下面我们利用数论知识设计一种高效算法。
不妨让兔子躲在1号洞,因为如果狼能从0号洞到1号洞,则它一定能够从1号洞到2号,3号,..n-1号洞,兔子无论躲在哪里都难逃厄运。换而言之,若有安全的洞,1号洞必然是其中之一。
再来看狼的运动。狼的第i次运动后的洞址应该是(m*i) mod n,若(m*i) mod n=1,即狼第i次运动后到达1号洞,则可以证明gcd(m,n)=1,其中gcd(m,n)表示m和n的最大公约数。因为若gcd(m,n)=k,设m'*k=m,n'*k=n,则(m'*k*i)mod(n'*k)=1,于是存在正整数t,使得m'*k*i=t*n'*k+1,两边同除以k得到:m'*i=t*n'+1/k。因为m'*i和t*n'同为正整数,所以1/k为整数,因此k只能为1。以上证明过程可逆,所以若gcd(m,n)=1,则必存在i使得(m*i)mod n=1。因而兔子能够幸免的充要条件为gcd(m,n)>1,在此条件下,它应该选择除了i*gcd(m,n),i=0,1,..,(n/gcd(m,n)-1),的洞躲藏。
至于求m,n的最大公约数gcd(m,n),用众所周知的辗转相除法即可。




相关文章

相关软件