约瑟夫问题求解

云南大学物理实验教学中心实验报告课程名称：计算机软件技术基础实验项目：线性链表的应用学生姓名：学号：学院系级专业成绩指导教师：实验时间：年时分至时分实验地点：实验类型：教学（演示□验证□综合█设计□）学生科研□课外开放□测试□其它□一、实验目的：在实习四的基础上，用线性链表解决一个应用问题。

二、问题：约瑟夫问题（Joseph）的求解。

问题描述：n只猴子要选大王，选举方法是：所有猴子按1、2、3、……、n编号顺时针方向围坐一圈，从第1号开始按1、2、3、……、m报数，凡报到m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。

试设计一个程序，输出猴子出列顺序。

基本要求：利用单循环链表存储结构模拟此过程，n和m值由键盘输入，按照出列的顺序打印各个猴子的编号。

三、程序的编写与调试1、原程序：#include<stdio.h>#include<malloc.h>struct Node{ int data;struct Node *next;};int main(){ struct Node *head, *s, *q, *t;int n, m, count=0, i;printf("请输入猴子总数 m:");scanf("%d",&m);printf("请输入报数数n:");scanf("%d"；&n);for(i=0; i<m; i++){s=struct Node *malloc(sizeofstruct Node);//分配空间s->data=i+1;s->next=NULL;if(i==0){head=s;q=head;}else{q->next=s;q=q->next;}}q->next=head;printf("开始顺序:“);q=head;while(q->next!=head){printf("%d ",q->data); //开始时的顺序q=q->next;}printf("%d ",q->data);q=head;printf("\n");printf("出列顺序:");do {count++;if(count==n-1){t=q->next;q->next=t->next;count=0;printf("%d ", t->data); //出列顺序free(t); //释放空间}q=q->next;}while(q->next!=q);printf("\n");printf("猴子大王是: %d\n",q->data);}2、正确程序：#include<stdio.h>#include<malloc.h>struct Node{ int data;struct Node *next;};int main(){ struct Node *head, *s, *q, *t;int n, m, count=0, i;printf("请输入猴子总数 m:");scanf("%d",&m);printf("请输入报数数n:");scanf("%d",&n);for(i=0; i<m; i++){s=(struct Node *)malloc(sizeof(struct Node)); //分配空间s->data=i+1;s->next=NULL;if(i==0){head=s;q=head;}else{q->next=s;q=q->next;}}q->next=head;printf("开始顺序:");q=head;while(q->next!=head){printf("%d ",q->data); //开始时的顺序q=q->next;}printf("%d ",q->data);q=head;printf("\n");printf("出列顺序:");do {count++;if(count==n-1){t=q->next;q->next=t->next;count=0;printf("%d ", t->data); //出列顺序free(t); //释放空间}q=q->next;}while(q->next!=q);printf("\n");printf("猴子大王是: %d\n",q->data);}运行结果：四、实验总结通过此次试验，加深了我对线性表（链式存储）的学习，使我对线性表（链式存储）有了深刻地认识，尤其是循环链表，并学会了用线性链表解决实际应用问题；同时也提高了自己的编程能力，知道了自己在编程方面的不足之处以及常犯的错误，使自己得到了很好的锻炼。

约瑟夫问题与循环链表解决环状数据结构的应用问题约瑟夫问题是一个经典的数学问题，涉及到环状数据结构的应用。

在这个问题中，有n个人围成一圈，从第一个人开始依次报数，每报到第m个人就出列，直到剩下最后一个人。

本文将介绍约瑟夫问题的背景和解决方法，并探讨循环链表在解决环状数据结构问题中的应用。

一、约瑟夫问题的背景约瑟夫问题最早可追溯到两千多年前。

根据传说，犹太历史学家弗拉维奥·约瑟夫斯（Flavius Josephus）当时被罗马军队围困在一个洞穴中，他和其他39个犹太人决定宁愿自杀也不被俘。

他们决定站成一个圆圈，从第一个人开始，数到第三个人就将他杀死，直到最后一个人留下来。

通过解决这个例子中的问题，人们发现了一种递推模式，即每次被杀的人索引号是前一个被杀人索引号加上一个特定数（m）对人数（n）取余的结果。

二、求解约瑟夫问题1. 暴力法最简单的解法是通过一个数组，将每个人标记为存活或死亡。

然后从第一个人开始，按照指定的m值遍历循环，找到下一个存活的人，直到只剩下最后一个人。

这种方法的问题在于时间复杂度较高，特别是当人数和m值较大时，算法运行效率低下。

2. 循环链表循环链表是解决约瑟夫问题的一种有效数据结构。

在循环链表中，每个节点都包含一个指向下一个节点的指针，最后一个节点指向第一个节点，形成一个闭环。

通过使用循环链表，我们可以轻松地实现约瑟夫问题的求解。

首先，我们将n个人作为节点插入到循环链表中，并将最后一个节点指向第一个节点。

然后，我们从第一个人开始依次报数，每报到第m个人，就将该节点从链表中移除。

此时，链表的结构会自动调整，继续报数直到只剩下最后一个人。

这种方法只需要遍历一次链表，因此时间复杂度为O(n)。

相比暴力法，它的运行效率更高。

三、循环链表解决环状数据结构的应用问题除了约瑟夫问题，循环链表还可以应用于其他环状数据结构的解决方案中。

1. 环形队列环形队列是计算机科学中常用的一种数据结构，它可以实现缓冲区的循环利用。

“约瑟夫”问题及若干变种例1、约瑟夫问题(Josephus)[问题描述]M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N 报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。

例如，输入8 3，输出：7。

[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。

利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current 表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。

每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。

然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

参考程序如下：program josephus1a {模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。

实验一：约瑟夫问题求解一、问题描述1、实验题目：约瑟夫（Josephus）问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。

2、基本要求：试设计一个程序，按出列顺序印出个人编号。

3、测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。

ｍ的初值为6，正确的出列顺序应为：6，1，4，7，2，3，5。

二、需求分析１、本程序用来求出含有密码的约瑟夫问题，可以输出所有人的出列顺序。

2 、程序运行后显示提示信息，提示用户输入一圈的人数n，接着输入每个人的密码，最后提示输入初始密码。

3、用户输入完毕后，程序自动输出运算结果。

三、概要设计1、设计思路n个人围成一圈，每个人的手中都有一个密码，这个密码决定了下一次报数的上限。

游戏规则：①给定一个初始密码②循环报数，报到密码值的人要出列，依次类推，直到所有的人都出列本程序要求输入的内容：n个人的密码及初始密码；本程序要求输出的内容：n个人出列的顺序。

2、数据结构为了实现上述功能，可以采用链式存储结构。

采用链式存储结构，定义了一个存储个人信息的结构体，及两个自定义函数，分别用于创建链表和约瑟夫出列操作。

①链表抽象数据类型的定义： #define SLNODE struct slnodeADT SLNODE{数据对象：D={ i a |i a ∈SLNODE, i=1,2,3.... }数据关系：R=φ}ADT SLNODE;②自定义函数:void create_SLnode(SLNODE *p,int n)//创建队列{ 创建链表，为N 个人分配密码 }void Josef(SLNODE *p,int n)//进行约瑟夫操作{输入初始密码m;for(){ 将出列的结点删除，并输出出列序号；}}③本程序的保护模块：结构体模块主程序模块自定义函数模块调用关系：3、程序设计主要算法的流程图：create_SLnode( )算法流程图Josef( )算法流程图四、详细设计1、元素类型、结点的类型及指针#define SLNODE struct slnodeSLNODE//每个结点的结构体{int num;//num代表序号int code;//code代表密码SLNODE *next;};2、自定义函数：void create_SLnode(SLNODE *p,int n)//创建队列，并将其尾指针指向第一个序号{SLNODE *r,*s;s=p;int i,m;cout<<"请给这"<<n<<"个人分配密码："<<endl;for(i=0;i<n;i++){cout<<"请给第"<<i+1<<"个人输入密码："<<endl;cin>>m;r=(SLNODE *)malloc(sizeof(SLNODE));r->code=m;r->num=i+1;r->next=s->next;s->next=r;s=s->next;}p=p->next;s->next=p;}void Josef(SLNODE *p,int n)//进行约瑟夫操作{p=p->next;int m;int i,j;SLNODE *r;cout<<"请输入初始密码："<<endl;cin>>m;cout<<"依次出列的序号为:"<<endl;for(i=0;i<n-1;i++)p=p->next;for(i=0;i<n-2;i++){for(j=0;j<m-1;j++)p=p->next;cout<<(p->next)->num<<endl;m=(p->next)->code;r=p->next;p->next=r->next;}if(m%2==0)cout<<p->num<<endl<<(p->next)->num<<endl;elsecout<<(p->next)->num<<endl<<p->num<<endl;}3、主函数：int main(){SLNODE *p;int n;cout<<"请输入一圈的人数："<<endl;cin>>n;p=(SLNODE *)malloc(sizeof(SLNODE));p->next=NULL;create_SLnode(p,n);Josef(p,n);return 0;}4、函数的调用关系：主函数main()调用自定义函数void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/。

“约瑟夫”问题及若干变种林厚从例1、约瑟夫问题(Josephus)[问题描述]M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。

例如，输入8 3，输出：7。

[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m 个元素的数组monkey来实现。

利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。

每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。

然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

参考程序如下：program josephus1a {模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。

Java 约瑟夫环问题的两种解法（循环数组，单向环形链表）Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1=k=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

2.解决方法一：循环数组提示：每次报数，如果满足出圈的条件就将数组元素设置为-1,当下次报数时跳过-1。

直至数组最后一个元素变为-1，循环结束，数组的循环使用取模来完成。

--解决方法二:数组+取模public static void JosephuByArr(int total,int startNum,int m){ int []Arr=new int[total];int leave=total; --剩下的数量int count=0; --报数（0-1-2-3-4-5····）int index=startNum; --第一个元素--初始化数组（为了方便取模，最后一个元素放在数组的第0个,也可以先加一再取模）Arr[0]=total;for(int i=1;iArr.length;i++){Arr[i]=i;while(leave0){count++; --报数--找到报数为count的数组元素if(Arr[index%total]==-1){while(Arr[index%total]==-1){index++;--如果满足条件，输出（元素设置为-1）if(count%m==0){System.out.print(Arr[index%total]+"t");Arr[index%total]=-1;leave--;--下一个元素开始index++;3.解决方法二：单向环形链表提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

约瑟夫问题约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

举个例子：有64名战士被敌人俘虏了。

敌人命令他们拍成一圆圈，编上号码1，2，3…，64。

敌人把1号杀了，又把3号杀了，他们隔着一个杀一个这样转着圈杀。

最后只剩下一个人，这个人就是约瑟夫斯。

请问约瑟夫斯是多少号？（这就是“约瑟夫斯”问题。

）这个问题解答起来比较简单：敌人从1号开始，隔一个杀一个，第一圈把所有的奇数号码的战士圈杀光了。

剩下的32名战士需要重新编号，而敌人在第二圈杀死的是重新编号的奇数号码。

由于第一圈剩下的全部是偶数号2，4，6，…，64。

把它们全部用2去除，得1，2，3，…，32。

这是第二圈编的号码。

第二圈杀过以后，又把奇数号码都杀掉了，还剩16个人。

如此下去，可以想到最后剩下的必然是64号。

$64=2^6$，它可以连续被2整除6次，是从1到64中能被2整除次数最多的数，因此，最后必然把64 号留下。

如果有65名战士被俘，敌人还是按上述的方法残杀战士，最后还会剩下约瑟夫斯吗？经过计算，很容易得到结论，不是。

因为第一个人被杀后，也就是1号被杀后，第二个被杀的是必然3号。

如果把1号排除在外，那么还剩下的仍是64人，新1号就是3号。

这样原来的2号就变成了新的64 号，所以剩下的必然是2号。

进一步的归类，不难发现如果原来有$2^k$个人，最后剩下的必然$2^k$号；如果原来有$2^k+1$个人，最后剩下2号；如果原来有$2^k+2$个人，最后剩下4号……如果原来有$2^k+m$个人，最后剩下2m号.比如：原来有100人，由于$100=64+36=2^6+36$，所以最后剩下的就是36×2=72号；又如：原来有11 1人，由于$100=64+47=2^6+47$，所以最后剩下的就是47×2=94号传说古代有一批人被蛮族俘虏了，敌人命令他们排成圆圈，编上号码1，2，3，…然后把1号杀了，把3号杀了，总之每隔一个人杀一个人，最后剩下一个人，这个人就是约瑟夫斯。

实验一约瑟夫问题求解1）内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n 的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。

一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将它的密码作为新的m值，再从下个人开始新一轮报数，如此反复，直到剩下最后一人则为获胜者。

试设计一个程序求出出列顺序。

2）要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

3)测试数据:n=7，7 个人的密码依次为：3，1，7，2，4，8，4 。

m的初值为20，则正确的出列顺序应为6，1，4，7，2，3，5。

4）输入输出:输入数据：建立输入处理输入数据，输入n输入以及每个人的密码；m的初值。

输出形式：建立一个输出函数，输出正确的序列。

实验二停车场问题1）内容：设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的在最北端），若停车场内已经停满 n辆车，那么后来的车只能在场外等候，一旦有车开走，则等候在第一位的车即可开入（这是一个队列设长度为m）；当停车场内某辆车需要开出，则在它之后的车辆必须给它让道，当这辆车驶出停车场后，其他车辆按序入栈。

每辆车按时间收费。

2）要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。

每一组输入数据包括三个数据：汽车的“到达”（’A’表示）或“离去”（’D’表示）信息，汽车标识（牌照号）以及到达或离去的时刻。

对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。

栈以顺序结构实现，队列以链表结构实现。

3)测试数据:设 n＝3，m=4,停车价格为p=2。