来历

一般形式

猴子选大王

约瑟夫"密码问题"

笔算解决约瑟夫问题

约瑟夫问题

来历

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

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++代码示例：

#include<iostream>

using namespace std;

void main()

{

int n,m,a[101],k,i,j,num; //计数器是从1开始的，所以100个人用101

cout<<"请输入参加游戏的玩家人数(不超过100人):";

cin>>n;

cout<<"----------------------------------------"<<endl;

if(n>100）

{

cout<<"玩家太多，请重新登陆此程序！"<<endl;

return;

}

cout<<"输入游戏中要玩的数字：";

cin>>m;

cout<<"----------------------------------------"<<endl;

for(i=1;i<=n;i++)

{

a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号，

}

j=0;

k=0;

for(i=1;i<=n;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)

i=0;

}

cout<<"最后获胜的玩家是第 "<<num<<" 号玩家！"<<endl;

cout<<"----------------------------------------"<<endl;

}

写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法 很巧妙很简单 不过只能推出最后一个出列的人

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人（编号一定是（m-1） mod n) 出列之后，剩下的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

变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k) mod n

如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式

f[1]=0;

f=(f+m) mod i; (i>1）

有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1

由于是逐级递推，不需要保存每个f，程序也是异常简单：

c++

#include <stdio.h>

int main()

{

int n,m,i,s=0;

printf ("N M = "); scanf("%d%d",&n,&m);

for (i=2; i<=n; i++) s=(s+m)%i;

printf ("The winner is %d\",s+1）;

}

pascal

var n,m,i,s:integer;

begin

write('N M =');

read(n,m);

for i:=2 to n do

s:=(s+m) mod i;

writeln('The winner is ',s+1）;

end.

这个算法的时间复杂度为O(n），相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。

约瑟夫问题10e100版（from vijios)

描述 Description

n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。

输入格式 Input Format

一个正整数n，表示人的个数。输入数据保证数字n不超过100位。

输出格式 Output Format

一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。

样例输入 Sample Input

9

样例输出 Sample Output

3

时间限制 Time Limitation

各个测试点1s

注释 Hint

样例说明

当n=9时，退出圈子的人的编号依次为：

2 4 6 8 1 5 9 7

最后剩下的人编号为3

初见这道题，可能会想到模拟。可是数据实在太大啦！！

我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...

有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...

这样就好弄了！！

大体思路如下：

①read(a)

②b:=1,c:=1{b为某一组的元素个数，c为现在所加到的数}

③while c<a do (b:=b*2,c:=b+c){超过目标时停止加数}

⑥c:=c-b{退到前一组}

⑦x:=a-c{算出目标为所在组的第几个元素}

⑧ans:=x*2-1{求出该元素}

⑨write(ans)

有了思路，再加上高精度就可以了。我写的代码比较猥琐，因为是先把上面的思路敲进去，再写过程，又把一些简单的过程合到主程序中了，所以有点乱，也有点猥琐。起提供思路的作用还是完全可以的吧~~~

var a,b,c:array[1..105]of integer;

la,lb,lc,i:integer;

s:string;

procedure incc;

var i:integer;

begin

for i:=1 to 105 do c:=c+b;

for i:=1 to 104 do if c>9 then

begin

c:=c+c div 10;

c:=c mod 10;

end;

end;

function cxiaoa:boolean;

var i:integer;

begin

cxiaoa:=false;

for i:=105 downto 1 do

if c<a then begin cxiaoa:=true;break;end

else if c>a then break;

end;

procedure doubleb;

var i:integer;

begin

for i:=1 to 105 do b:=b*2;

for i:=1 to 104 do if b>9 then

begin

b:=b+b div 10;

b:=b mod 10;

end;

end;

procedure decc;

var i,j:integer;

begin

for i:=1 to 104 do

if c>=b then c:=c-b else

begin

j:=i+1;

while c[j]=0 do inc(j);

while j>i do

begin

c[j]:=c[j]-1;

c[j-1]:=c[j-1]+10;

dec(j);

end;

c:=c-b;

end;

end;

procedure fua;

var i:integer;

begin

for i:=1 to 104 do

if a>c then a:=a-c else

begin

a:=a-1;

a:=a+10;

a:=a-c;

end;

end;

procedure outit;

var i,j:integer;

begin

for i:=1 to 105 do a:=a*2;

for i:=1 to 104 do if a>9 then

begin

a:=a+a div 10;

a:=a mod 10;

end;

if a[1]>0 then a[1]:=a[1]-1 else

begin

j:=2;

while a[j]=0 do inc(j);

while j>1 do

begin

a[j]:=a[j]-1;

a[j-1]:=a[j-1]+10;

dec(j);

end;

a[1]:=a[1]-1;

end;

for i:=105 downto 1 do if a>0 then begin j:=i;break;end;

for i:=j downto 1 do write(a);

end;

begin

readln(s);

la:=length(s);

for i:=la downto 1 do a:=ord(s[la+1-i])-ord('0');

b[1]:=1;

c[1]:=1;

while cxiaoa do

begin

doubleb;

incc;

end;

decc;

fua;

outit;

end.

猴子选大王

一． 问题描述：

一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

二． 基本要求：

（1） 输入数据：输入m,n m,n 为整数，n<m

（2）中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能

C程序：

#include <stdio.h>

#include<malloc.h>

#define LEN sizeof(struct monkey) //定义struct monkey 这个类型的长度

struct monkey

{

int num;

struct monkey *next;

};

struct monkey *create(int m)

{

struct monkey *head,*p1,*p2;

int i;

p1=p2=(struct monkey*)malloc(LEN);

head=p1;

head->num=1;

for(i=1,p1->num=1;i<m;i++)

{

p1=(struct monkey*)malloc(LEN);

p1->num=i+1;

p2->next=p1;

p2=p1;

}

p2->next=head;

return head;

}

struct monkey *findout(struct monkey *start,int n)

{

int i;

struct monkey *p;

i=n;

p=start;

for(i=1;i<n-1;i++)

p=p->next;

return p;

}

struct monkey *letout(struct monkey *last)

{

struct monkey *out,*next;

out=last->next;

last->next=out->next;

next=out->next;

free(out);

return next;

}

int main()

{

int m,n,i,king;

struct monkey *p1,*p2;

printf("请输入猴子的个数m:\");

scanf("%d",&m);

printf("每次数猴子的个数n :\");

scanf("%d",&n);

if(n==1）

{

king=m;

}

else

{

p1=p2=create(m);

for(i=1;i<m;i++)

{

p2=findout(p1,n);

p1=p2;

p2=letout(p1）;

p1=p2;

}

king=p2->num;

free(p2）;

}

printf("猴王的编号是：%d\",king);

return 0;

}

pascal程序：

var

a:array[1..10000] of integer;

n,s,i,j:integer;

begin

read(m,n);

for i:=1 to m do a[i]:=1;

j:=0;

for i:=1 to m do

begin

s:=0;

while s<n do

begin

if j<m then inc(j)

else j:=1;

s:=s+a[j];

end;

write(j);

a[j]:=0;

end;

end.

#include <stdio.h>

int main()

{

int n,m,i,s=0;

printf ("N M = "); scanf("%d%d",&n,&m);

for (i=2; i<=n; i++) s=(s+m)%i;

printf ("The winner is %d\",s+1）;

return 0;

}

约瑟夫数学算法

#include <stdio.h>

#include <conio.h>

int main( void )

{

int n,i = 0,m,p;

scanf("%d%d",&n,&m); //n总人数，m步长

while( ++i <= n )

{

p = i * m;

while (p > n)

p = p - n + (p - n - 1）/(m - 1）;

printf("%d\",p);

}

getch();

return 0;

}

约瑟夫递推算法

#include<iostream>

using namespace std;

int king(int M,int N)

{

int k = 0;

for (int i = 2; i <= M; i++)

k = (k + N) % i;

return ++k;}i

nt main()

{

int n,m;

while(scanf("%d%d",&n,&m)&&n&&m)

{

cout<<king(n,m)<<endl;

}

return 0;

}

约瑟夫"密码问题"

问题描述：编号为1、2、3、...、N的N个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。从指定

编号为1的人开始，按顺时针方向自1开始顺序报数，报到指定数M时停止报数，报M的人出列，并将

他的密码作为新的M值，从他在顺时针方向的下一个人开始，重新从1报数，依此类推，直至所有的

人全部出列为止。请设计一个程序求出出列的顺序，其中N≤30，M及密码值从键盘输入。

------------------------c语言实现-------------------

笔算解决约瑟夫问题

在M比较小的时候 ，可以用笔算的方法求解，

M=2

即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。

当N=2^k的时候，第一个报数的人就是最后一个死的，

对于任意的自然数N 都可以表示为N=2^k+t，其中t<n/2

于是当有t个人去死的时候，就只剩下2^k个人 ，这2^k个人中第一个报数的就是最后去死的。这2^k个人中第一个报数的人就是2t+1

于是就求出了当M=2时约瑟夫问题的解：

求出不大于N的最大的2的整数次幂，记为2^k，最后一个去死的人是2(N-2^k)+1

M=3

即N个人围成一圈，1，2，3，1，2，3的报数，报到3就去死，直到只剩下一个人为止。

此时要比M=2时要复杂的多

我们以N=2009为例计算

N=2009，M=3时最后被杀死的人记为F（2009,3），或者可以简单的记为F（2009）

假设现在还剩下n个人，则下一轮将杀死[n/3]个人，[]表示取整，还剩下n-[n/3]个人

设这n个人为a1,a2,...,a(n-1）,an

从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1）,a(n-n mod 3+1）,..,an

于是可得：

1、这一轮中最后一个死的是a(n-n mod 3），下一轮第一个报数的是a(n-n mod 3+1）

2、若3|n，则最后死的人为新一轮的第F(n-[n/3]）个人

若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-（n mod 3）人

若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-（n mod 3）人

3、新一轮第k个人对应原来的第 3*[(k-1）/2]+(k-1）mod 2+1个人

综合1，2，3可得：

F（1）=1,F（2）=2,F（3）=2,F（4）=1,F（5）=4，F（6）=1，

当f(n-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-（n mod 3），F(n)=3*[(k-1）/2]+(k-1）mod 2+1

当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-（n mod 3） ，F(n)=3*[(k-1）/2]+(k-1）mod 2+1

这种算法需要计算 [log（3/2）2009]次 这个数不大于22，可以用笔算了

于是：

第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人，

第二圈，杀死446人，还剩下894人

第三圈，杀死298人，还剩下596人

第四圈，杀死198人，还剩下398人

第五圈，杀死132人，还剩下266人

第六圈，杀死88人，还剩下178人

第七圈，杀死59人，还剩下119人

第八圈，杀死39人，还剩下80人

第九圈，杀死26人，还剩下54人

第十圈，杀死18人，还剩36人

十一圈，杀死12人，还剩24人

十二圈，杀死8人，还剩16人

十三圈，杀死5人，还剩11人

十四圈，杀死3人，还剩8人

十五圈，杀死2人，还剩6人

F（1）=1,F（2）=2,F（3）=2,F（4）=1,F（5）=4，F（6）=1，

然后逆推回去

F（8）=7 F（11）=7 F（16）=8 f（24）=11 f（36）=16 f（54）=23 f（80）=31 f（119）=43 f（178）=62 f（266）=89 f（398）=130

F（596）=191 F（894）=286 F（1340）=425 F（2009）=634