猴王问题的公式分析
猴王问题：
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...
[解决办法]
看看
[解决办法]
顶一个
[解决办法]
要下点东西，赚分不容易啊
[解决办法]
谢谢楼主
[解决办法]
顶一个，好好的
[解决办法]
顶一个
[解决办法]
ding
[解决办法]
学习。。。。。。
[解决办法]
好好学习吧~``
[解决办法]
学习了
[解决办法]
/* HELLO.C -- Hello, world */
#include "stdio.h"
#include "conio.h"
struct hou
{
void *prev;
void *next;
int num;
}
void result(int n,int m);
void add(struct hou head,struct hou addone);
struct hou del(struct hou delone);
struct hou create(int n);
struct hou first;
struct hou curr;
main()
{
result(6,2);
getch();
}
void result(int n,int m)
{
int todo=n;
int i;
int j=0;
first->next = first;
first->prev = first;
first.num=1;
for(i=0;i<n;i++)
{
curr = create(i);
add(first,curr);
}
curr=first;
while(todo>1)
{
j++;
if(j=m)
{
curr =del(curr);
todo--;
}else
{
curr=curr->next;
}
}
printf("%d",first.num);
}
void add(struct hou head,struct hou addone)
{
head->prev->next=addone;
add->prev=head->prev;
addone->next=head;
head->prev=addone;
}
struct hou create(int n)
{
struct hou newone;
newone->next=first;
newone->prev=first;
newone.num=n;
}
struct hou del(struct hou delone)
{
delone->prev->next=delone->next;
delone->next->prev=delone->prev;
curr=delone->next;
}
[解决办法]
这个代码还有很多错误。我写代码还是有点问题。不好意思啊。但是大概知道了我的思路就行。用链表就可以一次搞定了。n次就可以直接搞定了。呵呵~
[解决办法]
..
[解决办法]
buhuia
[解决办法]
funtion x(n,m)
begin
result := ( (n+m) mod n ) + 1;
end;
[解决办法]
学习了...顶起来
[解决办法]
来学习的，这是个很好的地方
[解决办法]
我也是来学习的 嘎嘎
[解决办法]
强大，学习了
[解决办法]
好像这里的人都是高人啊，看来我真是落伍咯。大学里，学了一大堆没有用的东西。
[解决办法]
收藏啦！
[解决办法]
呵呵，好玩哈哈
[解决办法]
学习。
[解决办法]
好好学习吧
[解决办法]
记得数据结构的书本例题就是LZ的题目
链表是比较容易理解的做法 循环链表 数数删除
或者用数组存放猴子的状态（数过，未数），时间复杂度和链表是一样的
不知有没听说过“线段树",时间复杂度可以改进为O(n)
[解决办法]
约瑟夫问题 干吗叫厚望问题
[解决办法]
太难了。
[解决办法]
mark
[解决办法]
好好学习吧
[解决办法]
学习学习
JF
[解决办法]
学习中
[解决办法]
学习了谢谢了。
[解决办法]
还有个差不多的题目是竹排逃生，也是类似的题目。
[解决办法]
[解决办法]
学习了~~ 谢谢LZ分享哈
[解决办法]
[解决办法]
看看，动脑子太累
[解决办法]
学习了
[解决办法]
已阅
