猴王问题可以做如下描述:
有n只猴子围成一圈,从第一个开始数,数到第m个将其踢出,接着后面继续从1数,如此循环,直到只剩最后一只z,那只就是猴王.输入n,m.输出z.
初次看到这个题目的时候,首先想到是实现一个循环列表,通过n次循环模拟该过程。
但是该方法有一个明显的缺点:
如果n的数值过大,程序很可能找不到足够的空间来实现循环列表。并且也有时间开销的问题。
-----------
这时需要分析数据特点,看看怎样才能在节约空间的情况下实现数据取值:
不用存储所有的数据,那就需要通过循环一个一个的去分析每个位置上的猴子。能够当王的猴子,必然不会在n-1次循环中被选中。那么可不可以对每一个猴子模拟挑选过程,最后通过判定是否能通过n-1次选择来判定谁是猴王?
假设猴子在经过j 轮循环之后当前位置是Aj,那么j+1轮循环之后该猴子在什么位置?
假设该猴子在j+1轮没有被选中那么我们需要首先计算出以下几个数值
1.j 轮之后还剩下n-j个猴子
2.j+1 轮选中的猴子其当前位置是 m%(n-j)
3.所以j+1轮之后该猴子的位置是
if Aj>m%(n-j)
下一轮的位置是
n-j-m%(n-j)-[(n-j)-Aj]=Aj-m%(n-j)
if Aj<m%(n-j)
下一轮的位置是
n-j-m%(n-j)+Aj
两个公式可以合并为:
Aj-m%(n-j)+(n-j)*{[m%(n-j)-Aj]/|[m%(n-j)-Aj]|+1}/2
即
Aj+1=Aj-m%(n-j)+(n-j)*{[m%(n-j)-Aj]/|[m%(n-j)-Aj]|+1}/2
---------这样我们就可以通过对比Aj和 m%(n-j)值来判定猴子每一个猴子在那一轮被选中,从而得到猴王。
----看文章的各位,现在我要提一个问题了。
我们知道在任何给定n,m值的情况下,当还剩下两只猴子的时候
Aj+1=1 , n-j=2 ,那么根据猴王选择本身的数据特性,逆推上面的公式我们能够得到在刚开始猴王的位置吗?
-------麻烦各位跟我一起思考!!!