猴王有关问题的公式分析
猴王问题的公式分析
猴王问题：
n只猴子，坐一圈，
从第一只开始点数，将第m只排除；
再从下一只重新数，又将第m只排除。。。。
直到剩下一只，为猴王，输出其序号x
程序模拟过程应该比较简单，只是模拟的就是复杂度很难降到0(n)
x(n,m)是有一定规律的，
有一个公式：
function x(n,m:Integer):Integer;
//n：开始时的人数；m：每次数数，第m个就要被剔除
var
s,i:Integer;
begin
s := 0;
//for i:=2 to n do //(1)这样的循环，结果是对的。
for i:=n downto 2 do //(2)这样的循环，结果是错的。
s:=(s+m) mod i;
result := s+1;
end;
2)这样的循环，结果是错的。
但是，它符合了，数数是从人数多时开始的，
没有考虑有人被剔除后，下标与人的起始编号已经不匹配了
(1)这样的循环，结果是对的。
按理说，数数是从人数多时开始的，它从少开始循环，却是对的！
可能这样反而已经考虑了 下标与人的起始编号已经不匹配 了！
不知道为什么会正好“错错得对”！
另外，不知道还能不能再进一步优化count函数为无须循环？
------解决方案--------------------
funtion x(n,m)
begin
result := ( (n+m) mod n ) + 1;
end;
------解决方案--------------------
学习了
JF
------解决方案--------------------
谢谢楼主分享
------解决方案--------------------
function x1(n,m:integer):integer;
begin
result := ( (n+m) mod n ) + 1;
end;
与LZ的结果完全不同
------解决方案--------------------
学习中
------解决方案--------------------
1就是从最后往前倒推，
------解决方案--------------------
谢谢楼主分享
------解决方案--------------------
function x1(n,m:integer):integer;
begin
result := ( (n+m) mod n ) + 1;
end;
假设n = 3， m = 1， 这个公式明显错误！
------解决方案--------------------
约瑟夫问题
------解决方案--------------------
经测试：
约瑟夫问题有两种解决方法：
一个是编程的循环链表求解约瑟夫问题，一个是数学方法。
用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂
度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号
。
我们知道第一个人(编号一定是m mod n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根
据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'
=(x+k) mod n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的
情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m) mod i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，
我们输出f[n]+1
由于是逐级递推，所以必须是FOR循环。
另外还有没有更加简单的运算方法就不知道了，想加快运算速度倒是有，改成汇编语言来运算，外加线程运算。
------解决方案--------------------
高，实在是高
------解决方案--------------------
看了题目，想了下，大概利用f(n)=f(n-1)公式可以把复杂度变为O(n)，不过详细的没有仔细想，不过看了lz的答案，感觉分析详细准确，lz确实比较牛。
------解决方案--------------------
用指针
------解决方案--------------------
mark...
猴王问题：
n只猴子，坐一圈，
从第一只开始点数，将第m只排除；
再从下一只重新数，又将第m只排除。。。。
直到剩下一只，为猴王，输出其序号x
程序模拟过程应该比较简单，只是模拟的就是复杂度很难降到0(n)
x(n,m)是有一定规律的，
有一个公式：
function x(n,m:Integer):Integer;
//n：开始时的人数；m：每次数数，第m个就要被剔除
var
s,i:Integer;
begin
s := 0;
//for i:=2 to n do //(1)这样的循环，结果是对的。
for i:=n downto 2 do //(2)这样的循环，结果是错的。
s:=(s+m) mod i;
result := s+1;
end;
2)这样的循环，结果是错的。
但是，它符合了，数数是从人数多时开始的，
没有考虑有人被剔除后，下标与人的起始编号已经不匹配了
(1)这样的循环，结果是对的。
按理说，数数是从人数多时开始的，它从少开始循环，却是对的！
可能这样反而已经考虑了 下标与人的起始编号已经不匹配 了！
不知道为什么会正好“错错得对”！
另外，不知道还能不能再进一步优化count函数为无须循环？
------解决方案--------------------
funtion x(n,m)
begin
result := ( (n+m) mod n ) + 1;
end;
------解决方案--------------------
学习了
JF
------解决方案--------------------
谢谢楼主分享
------解决方案--------------------
function x1(n,m:integer):integer;
begin
result := ( (n+m) mod n ) + 1;
end;
与LZ的结果完全不同
------解决方案--------------------
学习中
------解决方案--------------------
1就是从最后往前倒推，
------解决方案--------------------
谢谢楼主分享
------解决方案--------------------
function x1(n,m:integer):integer;
begin
result := ( (n+m) mod n ) + 1;
end;
假设n = 3， m = 1， 这个公式明显错误！
------解决方案--------------------
约瑟夫问题
------解决方案--------------------
经测试：
约瑟夫问题有两种解决方法：
一个是编程的循环链表求解约瑟夫问题，一个是数学方法。
用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂
度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号
。
我们知道第一个人(编号一定是m mod n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m mod n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根
据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'
=(x+k) mod n
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的
情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m) mod i; (i>1)
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，
我们输出f[n]+1
由于是逐级递推，所以必须是FOR循环。
另外还有没有更加简单的运算方法就不知道了，想加快运算速度倒是有，改成汇编语言来运算，外加线程运算。
------解决方案--------------------
高，实在是高
------解决方案--------------------
看了题目，想了下，大概利用f(n)=f(n-1)公式可以把复杂度变为O(n)，不过详细的没有仔细想，不过看了lz的答案，感觉分析详细准确，lz确实比较牛。
------解决方案--------------------
用指针
------解决方案--------------------
mark...