约瑟夫环问题-数据结构实现代码

#include<stdio.h>#include<stdlib.h>typedef struct LNode{//数据域int cipher; //密码int number; //编号struct LNode *next; //指针域}LNode,*LinkList;void InitList(LinkList &L) //创建一个只有头结点链表{L = (LinkList)malloc(sizeof(LNode));if(!L){exit(1);printf("/n/nError!/n/n");}L->next = L;}void CreateList(int n,LinkList &L) //初始化循环单链表{LinkList p,q;q = L;printf("分别输入每个人的密码：");for(int i = 1;i <= n;i++){int k;scanf("%d",&k);if(k <= 0){printf("\n\n密码有误!\n\n");exit(1);}p = (LinkList)malloc(sizeof(LNode));if(!p){exit(1);printf("/n/nError!/n/n");}p->cipher = k;p->number = i;L->next = p;L = p;}L->next = q->next;free(q);}void PrintList(int x,int n,LinkList L) //输出出列顺序{LinkList p,q;p = L;for(int i = 1;i <= n;i++){for(int j = 1;j < x;j++)p = p->next;q = p->next;x = q->cipher;printf("%d ",q->number);p->next = q->next;free(q);}}int main(){printf("=============约瑟夫环==============\n\n\n");int n,x;LinkList L;L = NULL;InitList(L); //构造空链表printf("输入初始密码：");scanf("%d",&x); //初始密码为xprintf("\n");printf("输入参与总人数：");scanf("%d",&n); //总共的人数nprintf("\n");CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n");printf("出列编号为：");PrintList(x,n,L); //输出出列顺序printf("\n\n");return 0;}。

#include <iostream.h>#include <stdlib.h>struct Member//定义结构体{int number;int password;Member *next;};class Joseph{public:Member *frist;//头指针int size;Joseph(void);~Joseph(void);int Size(void) const;//返回长度Member *Index(int i);//定位void Create(int i);//构造循环单链表int Delete(int i);//删除结点并返回number的值};Joseph::Joseph(){//frist=new Member;Member *p=new Member;frist=p;size=0;}Member *Joseph::Index(int i){if(i==0)return frist;Member *p=frist->next;int j=1;while(j<i){p=p->next;j++;}return p;}int Joseph::Size(void)const{return size;}void Joseph::Create(int i){for(int j=1;j<=i;j++){Member *p=Index(j-1);Member *q=new Member;q->number=j;p->next=q;size++;};//Member *p=Index(i);//p->next=frist;}Joseph::~Joseph(void){Member *p,*q;p=frist;while(size!=0){q=p;p=p->next;delete q;size--;}size=0;frist=NULL;}int Joseph::Delete(int i){Member *s,*p=Index(i-1);s=p->next;p->next=p->next->next;int x=s->number;cout<<x<<" ";int y=s->password;delete s;size--;return y;}void main(void){Joseph jos;int i;cout<<"Please input number of people :"<<endl;cin>>i;jos.Create(i);int frist;//设初始值cout<<"Please input the frist number :"<<endl;cin>>frist;for(int k=1;k<=i;k++)//用循环输入每个人的密码{cout<<"please input No."<<k<<"`s password:"<<endl;Member *b=jos.Index(k);cin>>b->password;}cout<<"The final is :"<<endl;int l=frist%i;if (l==0) l=i;for(int b=i-1;b>0;b--){frist=jos.Delete(l);l=(frist+l-1)%b;int e=jos.Size();if(l==0)l=e;}jos.Delete(l);cout<<endl;}。

程序源代码：#include <stdio.h>#include <malloc.h>#include<conio.h>#include <stdlib.h>#include<ctime>#define NULL 0typedef struct Node{int m;//密码int n;//序号struct Node *next;}Node,*Linklist;Linklist create(int z) //生成循环单链表并返回,z为总人数{int i,mm;Linklist H,r,s;H=NULL;printf("请按顺序依次为每个人添加密码：");for(i=1;i<=z;i++){printf("\ninput cipher=");scanf("%d",&mm);s=(Linklist)malloc(sizeof(Node));s->n=i;s->m=mm;printf("%d号的密码%d",i,s->m);if(H==NULL)//从链表的第一个节点插入{H=s;r=H;}else//链表的其余节点插入{r->next=s;r=s;//r后移}//for结束r->next=H;/*生成循环单链表*/return H;}void search(Linklist H,int m0,int z)//用循环链表实现报数问题{int count=1;//count为累计报数人数计数器int num=0;//num为标记出列人数计数器Linklist pre,p;p=H;printf("出列的顺序为:");while(num<z){do{count++;pre=p;p=p->next;}while(count<m0);｛pre->next=p->next;printf("%d ",p->n);m0=p->m;free(p);p=pre->next;count=1;num++;}//while结束}void clean(){int system(const char *string);int inquiry;printf("请问需要清除上一次操作记录吗（1.清屏/2.不清屏）...?\n"); scanf("%d",&inquiry);if(inquiry ==1)system("cls");}void text(){int m0,z,i, choose,k=1; //k用来阻止第一次进入程序清屏操作Linklist H;bool chooseFlag=false;while(1){if(k!=1)clean();k++;while(!chooseFlag){printf(" ……………………欢迎进入约瑟夫环问题系统…………………… \n"); printf( "* 1.输入约瑟夫环数据 * \n"); printf(" * 2.什么是约瑟夫环 * \n"); printf(" * 3.退出系统 * \n"); printf("........................................................ \n"); printf("请输入相应的数字进行选择: ");scanf("%d",&choose);for(i=1;i<=4;i++){if(choose==i) { chooseFlag=true; break;}else chooseFlag=false;}if(!chooseFlag) printf("Error Input!\n");} //end while(!chooseFlag)if(choose==1) //if 开始{printf("Input how many people in it:");//z为总人数scanf("%d",&z);if(z<=30){H=create(z);//函数调用printf("\nInput the start code m0=");scanf("%d",&m0);search(H,m0,z);printf("\n\n\n");}else{printf("超过最大输入人数\n");break;}}else if(choose==2){printf("\n约瑟夫环问题：设有n个人，其编号分别为1，2，3，…，n，安装编号顺序顺时针围坐一圈。

约瑟夫环问题如下：已知n个人(n>=1)围桌一园桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列。

他的下一个人又从1开始报数，数到m的那个人又出列。

依此规则重复下去，直到所有人全部出列。

求解最后一个出列的人的编号。

本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下：输入人数、所报数、第一个报数人编号存储并建立一个约瑟夫环通过循环结构依次查找每次出列的人的编号并输出输出最后一个出列的人的编号程序代码如下：#include<iostream>#include<process.h>#include<stdlib.h>using namespace std;struct Node //循环节点的定义{int number; //编号Node *next;};Node *CreateList(Node *L,int &n,int &m); //建立约瑟夫环函数void Joseph(Node *L,int n,int m); //输出每次出列号数函数Node *DeleteList(Node **L,int i,Node *q); //寻找每次出列人的号数int LengthList(Node *L); //计算环上所有人数函数void main() //主函数{system("color 75"); //设置颜色以美观Node *L;L=NULL; //初始化尾指针int n, m;cout<<"请输入人数N：";cin>>n; //环的长度if(n<1){cout<<"请输入正整数!";} //人数异常处理else{cout<<"请输入所报数M：";cin>>m;if(m<1){cout<<"请输入正整数!";} //号数异常处理else{L=CreateList(L,n,m); //重新给尾指针赋值Joseph(L,n,m);}}system("pause");}Node *CreateList(Node *L,int &n,int &m) //建立一个约瑟夫环（尾插法）{Node *q;for(int i=1;i<=n;i++){Node *p;p=new Node;p->number=i;p->next=NULL;if(i==1) L=q=p; //工作指针的初始化 else{q->next=p;q=q->next;}}q->next=L;if(L!=NULL){return(L);} //返回尾指针else cout<<"尾指针异常!"<<endl; //尾指针异常处理}void Joseph(Node *L,int n,int m) //输出每次出列的人{int k;cout<<"请输入第一个报数人：";cin>>k;if(k<1||k>n){cout<<"请输入1-"<<n<<"之间的数"<<endl;}else{cout<<"\n出列顺序:\n";for(int i=1;i<n;i++){Node *q = new Node;if(i==1) q=DeleteList(&L,k+m-1,q); //第一个出列人的号数else q=DeleteList(&L,m,q);cout<<"号数："<<q->number<<endl;delete q; //释放出列人的存储空间}cout<<"最后一个出列号数是："<<L->number<<endl; //输出最后出列人的号数}}Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人{if(i==1) i+=LengthList(*L); //顺序依次出列情况的处理方式Node *p;p=*L;int j=0;while(j<i-2) {p=p->next;j++;}q = p->next;p->next=p->next->next;*L = p->next;return(q);}int LengthList(Node *L) //计算环上的人数{if(L){cout<<"尾指针错误!"<<endl;} //异常处理else{int i=1;Node *p=L->next;while(p!=L){i++;p=p->next;}return(i);}}实验体会：通过对本问题的分析，我进一步熟悉了对各种逻辑表达式的判断和指针的使用。

#include"stdio.h"#include"stdlib.h"#include"malloc.h"#include"conio.h"#define ERROR 1#define OK 0typedef int ElemType;typedef int Status;typedef struct LNode{ElemType code;ElemType number;struct LNode *next;}LNode,*LinkList;Status CreateLink_L(LinkList &L,int n){struct LNode *p,*q;int i;if(n<=0)return ERROR;printf("请输入个人的密码：");L = (LinkList)malloc(sizeof(LNode));L -> next = NULL;L -> number=1;scanf("%d",&L->code);p=L;q=L;for(i = 2;i <= n;++i){L = (LinkList)malloc(sizeof (LNode));L -> next = NULL;L -> number = i;scanf("%d",&L->code);q-> next=L;q = L;}L->next=p;//首尾链接,L指向最后一个人return OK;Status ListDelete_L(LinkList &L,int n,int k,ElemType &code,ElemType &number) {int i;LinkList p=NULL;if(L->next==L) //{p=L;L=NULL;}else{k=(k-1+n)%n;//该移动的次数for(i=1;i<=k;i++) L=L->next;//点到出列的前一个人p=L->next;//该出列的人L->next=p->next;}code=p->code;number=p->number;free(p);return OK;}Status Josephus_L(LinkList &L,int n){ElemType code=0;ElemType number=0;int m;if(L==NULL)return ERROR;printf("请输入m的初值：");scanf("%d",&m);printf("先后出列的人是：");while(L!=NULL){ListDelete_L(L,n--,m,code,number);m=code;printf("%d ",number);}printf("\n");return OK;}int main()LinkList L=NULL;int n;int m;printf("请输入人数：");while(!scanf("%d",&n)||n<=0){printf("请输入一个正整数：");fflush(stdin);}if(!CreateLink_L(L,n)) // 判断链表是否创建成功Josephus_L(L,n);elseprintf("创建链表失败");printf("按任意键结束程序");getch();return 0;}。

#include<iostream>using namespace std;struct Node//定义节点的结构类型{int data;Node* next;};class CircularLinkedList//循环链表类{public:CircularLinkedList(){first=new Node;first->next=NULL;}CircularLinkedList(int n);//构建一个附有值的循环链表~CircularLinkedList();int Josephus(int num);//约瑟夫函数private:Node* first;};CircularLinkedList::CircularLinkedList(int n){first=new Node;Node * r=first;for(int i=1;i<=n;i++){Node* s=new Node;s->data=i;s->next=NULL;r->next=s;r=s;} //头插法初始化链表r->next=first; //最后一个元素的next志指向头结点}CircularLinkedList::~CircularLinkedList(){Node* p=first,*q;while(p->next!=first)//p指向最后一个结点时结束循环{q=p;p=p->next;delete q;}delete p;//删除头结点}int CircularLinkedList::Josephus(int num){Node* p=first,*q;if(num<=0)throw "输入错误！";while(first->next->next!=first){for(int i=1;i<num;i++) //p向后移动num位，指向要删除的元素的前一个结点{p=p->next;if(p==first) //若循环过程中出现p指向头结点，则跳过头结点{p=p->next;}}if(p->next==first) //若循环结束后p指向最后一个元素，则要跳过头结点，并让头结点的next指向要删除元素的下一个{p=first;q=p->next;p->next=q->next;//first->next=q->next;cout<<q->data<<" ";delete q;}else{q=p->next;p->next=q->next;cout<<q->data<<" ";delete q;}}cout<<endl;cout<<"最后一个数为：";return first->next->data;}void main(){int n,m;cout<<"请输入约瑟夫问题的人数和间隔人数：";cin>>n>>m;cout<<"依次删除："<<endl;CircularLinkedList Josephus1(n);//创建的对象调用第二个构造函数cout<<Josephus1.Josephus(m)<<endl;}。

数据结构与算法（Python版）：⽤队列（Queue）处理约瑟夫问题在古罗马时期，犹太⼈背叛了罗马⼈，落到困境，约瑟夫和同⾏的⼀共39个犹太⼈只能够⾃杀殉国，但是犹太教义规定不能⾃杀，因此只能够让别⼈将⾃⼰杀害。

他们所有39个⼈坐成⼀圈，报数1—7，报到7则由⾝旁的⼈将⾃⼰杀死。

结果约瑟夫灵机⼀动，给⾃⼰安排了⼀个位置，最后活了下来，那么约瑟夫给⾃⼰安排的是哪⼀个位置呢？在这个题⽬当中，我们如果使⽤队列，不仅可以处理任意⼈数坐成⼀圈，还可以将报数的值任意修改，最后都可以找到那⼀个不被杀死的⼈的位置。

我们可以将所有⼈都放进⼀个⼤的队列⾥，每报⼀次数字，那么就把队列头部的⼈放到队列的尾部，直到报数报到⼀组数字的最后⼀个，⽐如1——7当中的7。

这个时候就将队列头的这个⼈删除（也就是杀死），不断执⾏这个过程，直到整个队列当中的⼈数只有⼀个，则跳出循环返回最后活着的那个⼈的名字。

⾸先定义队列（Queue）类的结构：class Queue():def__init__(self):# 初始化⼀个空的列表self.__list=[]# 往队列⾥插⼊元素def enqueue(self,item):self.__list.append(item)# 弹出队列⾥的元素def dequeue(self):return self.__list.pop(0)# 弹出队列⾥最先进⼊的元素# 判断队列是否为空def is_empty(self):return self.__list == []# 计算队列的⼤⼩def size(self):return len(self.__list)使⽤队列类来初始化⼀个对象，sim_queue,然后编写刚才我们分析之后的程序：def hot_potato(namelist,num):sim_queue = Queue()for name in namelist:sim_queue.enqueue(name) # 把拿到的名字全部都放到队列⾥while sim_queue.size() > 1:for i in range(num):sim_queue.enqueue(sim_queue.dequeue())# 每执⾏完⼀次，就将队列的头拿出来弹出，相当于⼟⾖传递给这个⼈，然后这个⼈就死了last_person=sim_queue.dequeue()return last_personprint("开始执⾏约瑟夫问题")print(hot_potato(["bob","NAni","Ao li Gei!","HeHe","Mike","Suvennia"],4))输出：开始执⾏约瑟夫问题Ao li Gei!得解，因此Ao li Gei!这个⼈不会被杀死。

数据结构实验报告题目：约瑟夫环问题一．设计内容[问题描述]约瑟夫环问题的一种描述是：编号为1, 2, 3,…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。

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

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

试设计程序实现之。

[基本要求] 利用循环链表存储结构模拟此过程,按照出列的顺序打印各人的编号。

[ 实验提示] 程序运行后首先要求用户指定初始报数上限值。

然后读取各人的密码。

设n<=30 。

程序执行后,要求用户在计算机终端上显示“提示信息”后,用键盘输入“提示信息”中规定的命令,以“回车符”为结束标志。

相应的输入数据和运算结果显示在其后。

二、设计目的1. 达到熟练掌握C++ 语言的基本知识和技能；2. 能够利用所学的基本知识和技能,解决简单的面向对象程序设计问题。

3. 把课本上的知识应用到实际生活中,达到学以致用的目的。

三、系统分析与设计（确定程序功能模块）1、为实现上述程序的功能,应以有序链表表示集合。

基本操作：InitList(&L)操作结果：构造一个空的有序表L。

DestroyList(&L)初始条件：有序表L 已存在。

操作结果：销毁有序表L。

ListEmpty(L)初始条件：有序表L 已存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSE。

ListLength(L)初始条件：有序表L 已存在。

操作结果：返回L 中数据元素个数。

GetElem(L,i)初始条件：有序表L已存在，并且K i< ListLength(L)。

操作结果：返回L 中第i 个数据元素。

LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类型的值。

操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。

约瑟夫问题详解（CC++）Josephus 约瑟夫问题假设n个竞赛者排成一个环形，依次顺序编号1，2，…，n。

从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。

这个过程一直进行到所有的人都出列为止。

最后出列者为优胜者。

无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较麻烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

注意到原问题仅仅是要求出最后的胜利者的序号，而不是要模拟整个过程。

因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。

求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。

现在我们把他们的编号做一下转换：k --> 0k+1 --> 1k+2 --> 2......k-2 --> n-2变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x 是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？变回去的公式很简单：x'=(x+k)%n如何知道(n-1)个人报数的问题的解？显然，只要知道(n-2)个人的解就行了。

(n-2)个人的解呢？当然是先求(n-3)的情况---- 这显然就是一个倒推问题！递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式f[1]=0;f[i]=(f[i-1]+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。