猴子选大王问题.doc

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。　　*问题分析与算法设计　　约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。　　题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。[编辑本段]约瑟夫问题的一般形式：　　约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。　　假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。　　C++代码示例:　　#includeiostream　　using namespace std;　　void main()　　{　　int n,m,a[101],k,i,j,num; //计数器是从1开始的,所以100个人用101　　cout请输入参加游戏的玩家人数(不超过100人):;　　cinn;　　cout----------------------------------------endl;　　if(n100)　　{　　cout玩家太多,请重新登陆此程序!endl;　　return;　　}　　cout输入游戏中要玩的数字:;　　cinm;　　cout----------------------------------------endl;　　for(i=1;i=n;i++)　　{　　a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号，　　}　　j=0;　　k=0;　　for(i=1;i=n+1;i++){　　if(a【i】==1){　　j=j+a【i】;　　if(j==m)　　{　　j=0;　　a【i】=0;　　k++;　　}　　if(k==n){　　num=i;　　break;　　}　　}　　if(i==n+1)　　i=0;　　}　　cout最后获胜的玩家是第 num 号玩家!endl;　　cout----------------------------------------endl;　　}　　　　写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法 很巧妙很简单 不过只能推出最后一个出列的人　　无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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个人玩游戏报m退出最后胜利者的编号，