会编程的朋友请来啊

来源:百度知道 编辑:UC知道 时间:2024/06/20 01:31:33
一只兔子躲进了10个环行分布的某一个洞中,狼在第一个洞中没有找到兔子,就隔一个洞去找,到第三个洞中去找,也没有找到,就间隔两个洞去找,到第6个洞去找,以后每次多一个洞去找兔子....这样下去,如果狼一直找不到兔子.请问兔子可能躲在哪个洞中?给出算法步骤,并编程求出结果. 最好是用MatLab,别的也可以!
MILKSEA 你问这个问题做什么

可以模拟来做,这就是Joseph问题的变种,网上代码一大堆,很容易找到,略改改就行了。还是不给出具体做法了,而且我也从不用Matlab。
算法建议:不要用链表之类的数据结构模拟,直接用加法取模就可以了。与Joseph问题不同的是,这个问题的结束条件是狼开始走重复的路。由于狼走的步长不断加一,而洞数有限,所以走的路必然重复(隔10个洞就和隔1个洞是一回事)。每次走都做标记(要记下步长),以便判断重复,最后看还剩哪些(个)没标记的洞就可以了。

问题也可以用数学方法解,这样更有效一些。为计算方便,设第1、2、3、……、10个洞为1、2、3、……、10号。
狼第1次找的位置是:1
狼第2次找的位置是:1 + 2
狼第2次找的位置是:1 + 2 + 3
……
狼第 n 次找的位置是:(1 + 2 + 3 + ... + n) mod 10
(其中mod表示取模,模为0相当于位置10)
用公式表示,即狼位置为
W(n) = (1 + 2 + …… + n) mod 10
= ( n * (n + 1) / 2 ) mod 10.
如果我们可以算出W(n)的周期……唔,现在问题就变得越来越容易了。
如果喜欢数学的话,分析这个数论函数的周期是件令人愉快的事。
设狼第n次与第m次的位置是相同的,那么有
n (n + 1) / 2 ≡ m (m + 1) / 2 (mod 10)
于是就有
(n + m + 1)(n - m) / 2 ≡ 0 (mod 10)
也就是说(n + m + 1)/2或(n - m)/2被10整除,若m与n之间相距一个周期,那么(n + m + 1)不确定,只有m与n的差为定值。又注意到(n + m + 1)的奇偶性不确定,故应该为(n - m) / 2被10整除。
所以了,这个周期应是20。(可以验算一下)
啊哈,我们只要穷举出等差数列的前20项就行了,它们是:
1,3,6,10,15,21,28,36,45,55,
66,78,91,105,120,136,153,171,190,210
模10的结果,也就是