c语言实现约瑟夫环问题
（一）基本问题
1.问题描述
设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。
2.数据结构设计
首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
struct Node
{
int data;
Node *next;
};
其次，建立一个不带头结点的循环链表并由头指针first指示
3.算法设计
1、工作指针first，r，s，p，q初始化
2、输入人数（n）和报数（m）
3、循环n次，用尾插法创建链表
Node *q;
for(int i=1;i<=n;i++)
{
Node *p;
p=new Node;
p-> data =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);}
4、输入报数的起始人号数k;
5、Node *q = new Node;计数器初始化i=1;
6、循环n次删除结点并报出位置（其中第一个人后移k个）
当i 移动指针m-2次p=p->next; 删除p结点的后一结点q q=p->next; p->next=q->next; *L = p->next; 报出位置后Delete q; 计数器i++; 运行流程图 代码和相关解释 #include using namespace std; struct Node//循环节点的定义 { int data;//编号 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);//计算环上所有人数函数 开始 输入m 和n 创建链表 k>n-1 移动指针p 删除p 后一结点q 指针p 后移，k++ 输出n 结束 Y N void main()//主函数 //在主函数中，完成人数（n）和报数（m）的输入和工作指针的初始化{ 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->data=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<<"尾指针异常!"< } void Joseph(Node *L,int n,int m)//输出每次出列的人 { int k; cout<<"请输入第一个报数人："; cin>>k; if(k<1||k>n){cout<<"请输入1-"< { cout<<"\n出列顺序:\n"; for(int i=1;i { Node *q = new Node; if(i==1) q=DeleteList(&L,k+m-1,q);//第一个出列人的号数else q=DeleteList(&L,m,q); cout<<"号数："< delete q;//释放出列人的存储空间 } cout<<"最后一个出列号数是："< } Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人 { if(i==1) i+=LengthList(*L);//顺序依次出列情况的处理方式 Node *p; p=*L; int j=0; while(j q = p->next; p->next=p->next->next; *L = p->next; return(q); } int LengthList(Node *L)//计算环上的人数 { if(L){cout<<"尾指针错误!"< else { int i=1; Node *p=L->next; while(p!=L) { i++; p=p->next; } return(i); } } 复杂度分析： 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; } 时间复杂度：O（n） if(i==1) i+=LengthList(*L); Node *p; p=*L; int j=0; while(j q = p->next; p->next=p->next->next; *L = p->next; return(q); 时间复杂度：O（n2） 算法的空间复杂度：O（n2） 4.界面设计 请输入报数人数n 请输入所报数M 请输入第一个报数人 —— 以下列出依次报数的结 果 5. 运行、测试与分析 (二)采用顺序存储结构如何实现约瑟夫环问题 代码和解释 #include #include #include #define MaxSize 50 typedef char ElemType; typedef struct Seqlist {//线性表顺序存储结构定义 ElemType *elem[MaxSize];//存放顺序表数据元素 int length;//当前长度 }*JSeqlist;//线性表存储结构类型名 JSeqlist Int_SeqList(void) {//顺序表初始化 JSeqlist L; L=(JSeqlist)malloc(sizeof(struct Seqlist)); if(L!=NULL) L->length=0; else printf("超出范围！！"); return L; } ElemType *Locate_SeqList(JSeqlist L,int p) {//查找线性表中下标为P的元素 if(p>=0&&L->length) return(L->elem[p]); else {printf("顺序表中不存在相关元素"); return NULL; } } int Insert_SeqList(JSeqlist L,int i,ElemType *x) {//在顺序表中指定元素前插入X int j; if(L->length==MaxSize)//L.length是最后一个元素的位置{printf("线性表已满，无法进行插入操作！！！！\n"); return 0; } if(i<0||i>L->length) {printf("插入位置不对，超出顺序表长度\n"); return 0; } if(i==0) {L->elem[i]=x; L->length=L->length+1; return 1; } for(j=L->length;j>=i;j--) {L->elem[j]=x;} L->length++; return 1; } int Delete_JSeqlist(JSeqlist L,int i) {//在顺序表中删除第i个元素 int j; if(i<0||i>L->length-1) { printf("删除位置不对，超出顺序表的长度啦\n"); return 0; } for(j=i;j L->elem[j]=L->elem[j+1]; L->length--; return 1; } void josephus(JSeqlist L,int start,int m) {//josephus问题求解的非常牛逼的函数 int s,i; ElemType *w; s=start-1; for(i=L->length;i>0;i--) { s=(s+m-1)%i; w=Locate_SeqList(L,s); printf("出列人员为：%s\n",w); Delete_JSeqlist(L,s); } } int main (void) { JSeqlist Josephus; int n,m,i,k,s; Josephus=Int_SeqList();//顺序表初始化 printf(" 约瑟夫环问题顺序表求解_愚人节特别版\n\n"); printf("请输入本问题中总人数m="); scanf("%d",&n); printf("请输入本问题开始人员的位置S="); scanf("%d",&s); printf("请输入本问题的计数值m="); scanf("%d",&m); printf("请输入本问题中这些人的名字\n"); for(i=0;i { printf("第%d位置的人员的名字为:",(i+1)); Josephus->elem[i]=(ElemType *)calloc(10,sizeof(char)); scanf("%s",Josephus->elem[i]); k=Insert_SeqList(Josephus,i,Josephus->elem[i]); if(k==0) exit(1); } josephus(Josephus,s,m); free(Josephus); getchar(); return 0; } 运行结果 (三)密码不同 #include struct CList { int password; int number; struct CList *next; }; typedef struct CList CNode; typedef CNode *CLink; CLink CreateList(int length) { CLink head; CLink before; CLink new_node; int i; head=new CNode; if(head==NULL) return NULL; cout << "Please Input Password 1 :" << endl; cin >> head->password; head->number=1; head->next=NULL; before=head; for(i=1;i { new_node=new CNode; if(new_node == NULL) return NULL; new_node->number = i+1; cout << "Please Input Password " << new_node->number << ":" < cin >> new_node->password; new_node->next = NULL; before->next=new_node; before=new_node; } new_node->next =head; return head; } int main() { CLink head; CLink ptr,back,last; int i,j,m,n; cout << "Please Input the Number of Persons: " << endl; cin >> n; cout << "Please Input the First Password M: " << endl; cin >> m; head=CreateList(n); ptr=head; for(i=0;i { for(j=0;j { back=ptr;//定位最后一个数的接点赋值给back ptr=back->next; } cout <<"第"< m=ptr->password; if(ptr==head) { last=head; while(last->next!=head) last=last->next; last->next=head->next; delete ptr; ptr=last->next; head=ptr; } else { back->next=ptr->next; delete ptr; ptr=back->next; } } return 0; } 运行结果 （三）心得体会： 1.编程是个很细致的工作，尤其是在写顺序表的时候，涉及的函数很多，函数名中最初为了看在清晰，涉及成单词首字母是大写的，但是后来在函数调用的时候，就忘记了最初命名的时候是大写的了，导致编译的时候不能识别。 2.通过这个实验，理解了数据结构是数学在编程中的应用，是程序涉及和算法设计的基础，在计算机相关学科总占有举足轻重的地位 (一)基本问题 1?问题描述 设有编号为1,2,…小的n (n> 0)个人围成一个圈，每个人持有一个密码m。从第一个 人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m, 实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点 定义为如下结构类型： struct Node { int data; Node *n ext; }； 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first, r, s, p, q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for（i nt i=1;i<=n ;i++） { Node *p; p=new Node; p-> data =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);} 4、输入报数的起始人号数k; 5、Node *q = new Node; 计数器初始化i=1; 6、循环n 次删除结点并报出位置(其中第一个人后移当 k 个) i 2009年02月24日星期二下午 05:03 问题描述:约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M 的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。#include if(j!=i-1&&i!=1) {cout<<"erro!!!!!!!!!"; return 0;} if((q=(Scnode *)malloc(sizeof(Scnode)))==NULL) exit(1); q->data=x; q->next=p->next; p->next=q; return 1; } //删除 int MyDelete(Scnode *head,int i,DataType *x) { Scnode *p,*q; int j; p=head;j=1; while(p->next!=head&&j 一问题描述 1 题目内容：约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n的n 个人按顺时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值。试设计一个程序求出出列顺序。 2 基本要求：利用单项循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3 测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4（正确的出列顺序应为6，1，4，7，2，3，5）。 二需求分析 程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列 三概要设计 利用单项循环链表存储结构模拟此过程 1 循环链表的抽象数据类型 循环链表是单链表的一种变化形式，把单链表的最后一个节点的next指针指向第一个节点，整个链表就形成了一个环。 2 循环链表的基本操作（仅列出用在本程序的） creat(n) 操作结果：构造一个长度为n的无头节点的循环链表,并返回指向最后一个节点的指针 find(m,s) 初始条件：循环链表存在 操作结果：找到当前元素（即s）后面第m个元素 print(&m,&n,&s) 初始条件：循环链表存在 操作结果：从s中删除约舍夫问题中下一个被删除的元素，并将此元素显示在屏幕上 3 本程序包括4个模块： 主程序模块； 创建循环链表模块； 找节点模块； 删节点模块； 各模块调用关系如下图所示： 约瑟夫问题(数学解法及数组模拟) 约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 ? 以上来自百度百科约瑟夫【导师实操追-女视频】问题是个很有名的问题：N个人围成一个圈，从第一个人开始报数，第M个人会被杀掉，最后一个人则为幸存者【Ｑ】，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5【１】，4，6，2，3，1。 约瑟夫【０】问题其实并不难，但求解的方法多种多样；题目的 变化形式【⒈】也很多。接下来我们来对约瑟夫问题进行讨论。 1.模拟【б】解法优点 : 思维简单。?缺点：时间复杂度高达O(m*【9】n) 当n和m的值较大时，无法短时间内得到答案。 为了叙述【５】的方便我们将n个人编号为：1- n ，用一个数组vis【２】来标记是否存活：1表示死亡 0表示存活 s代表当前死亡的人【６】数? cnt 代表当前报了数的人数用t来枚举每一个位置(当tn时 t=1将人首尾相连)? 那么我们不难得出核心代码如下：bool vis[1000]; --标记当前位置的人的存活状态 int t = 0; --模拟位置 int s = 0; --死亡人数 int cnt = 0; --计数器 if(t n) t = 1; if(!vis[t]) cnt++; --如果这里有人,计数器+1 if(cnt == m) --如果此时已经等于m,这这个人死去 cnt = 0; --计数器清零 s++; --死亡人数+1 vis[t] = 1 --标记这个位置的人已经死去 coutt" "; --输出这个位置的编号 }while(s != n); 接下来我们来看另一种更为高效快速的解法数学解法 我们将这n个人按顺时针编号为0~n-1，则每次报数到m-1的人死去，剩下的人又继续从0开始报数，不断重复，求最后幸存的人最 计算机科学与工程学院 《算法与数据结构》试验报告[一] 专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼 学生姓名肖宇博试验时间2012-2-29 试验项目算法与数据结构 试验类别基础性（）设计性（）综合性（√）其它（） 试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。 成绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成设计任务 30分 程序与报告程序代码规范、功能正确 报告详实完整、体现收获 70分 备注： 评阅教师： 日期：年月日 试验内容 一、实验目的和要求 1、实验目的： （1）掌握用VC++上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。 2、实验内容 约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的 下一个人开始重新从1报数，报到m时停止并且报m的人出列。如 此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程， 对任意给定的m和n，求出出列编号序列。 3、实验要求：用顺序表实现。 二、设计分析 根据实验要求，采用顺序表来完成本次实验。 实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。 程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示！否则继续出队！ 三、源程序代码 #include 约瑟夫环问题python解法 约瑟夫环问题：已知n个人（以编号1，2，3.n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。 思路是：当k是1的时候，存活的是最后一个人，当k=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下： class Node(): def __init__(self,value,next=None): self.value=value self.next=next def createLink(n): return False if n==1: return Node(1) root=Node(1) tmp=root for i in range(2,n+1): tmp.next=Node(i) tmp=tmp.next tmp.next=root return root def showLink(root): tmp=root while True: print(tmp.value) tmp=tmp.next if tmp==None or tmp==root: def josephus(n,k): if k==1: print('survive:',n) root=createLink(n) tmp=root while True: for i in range(k-2): tmp=tmp.next print('kill:',tmp.next.value) tmp.next=tmp.next.next tmp=tmp.next if tmp.next==tmp: print('survive:',tmp.value) if __name__=='__main__': 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 约瑟夫环问题 问题描述： 有n个人围成一个环，然后给从某个人开始顺时针从1开始报数，每报到m时，将此人出环杀死(当然不杀死也可以啊)，然后从下一个人继续从1报数，直到最后只剩下一个人，求这个唯一剩下的存活的人是谁？ 分析： 首先，我们要标示这n个人，别小看这一步，其实蛮重要的。第一种标示方法是从0开始，将n个人标示为0~n-1，第二种方法是从1开始标示，将这n个人标示为1~n。当然会有人说了，那我从x(x>=2)开始，将此n个数标示为x~x+n-1，其实我们可以把这种情况都归到第二种从1开始标示的情况，为什么可以，我们稍后分析。 第一种情况从0开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m)%n (假设当前有n个人还活在环中)。 第二种情况从1开始编号： 编号为k的人拖出去杀死之后，下一个要拖出去受死的人的编号为：(k+m-1)%n+1，于是我们就可以回答上面的问题了，如果从x开始编号的话，下一个拖出去受死的人的编号就应该是：(k+m-x)%n+x了。 其实，上面的这两种情况是完全可以在合并的，编号只是一个识别，就像名字一样，叫什么都没关系，从某个人开始出环，不管他们怎么编号，n个人出环的先后顺序都是一样的，最后该哪个人活下来是确定的，不会因为编号而改变，所以不管从几开始编号，都可以归纳为从0开始编号，其他的编号就是一个从0编号情况的一个偏移而已，从x编号的情况就相当于从0开始编号的情况下每个人的编号都+x，大小先后顺序不变~ 于是，下面的讨论都是从0开始编号的~ 怎么解决这个问题呢？ 最简单的方法是模拟，模拟这个出环过程，可以使用链表也可以使用数组，时间复杂度都是O(n*m).当然，这种解法时间复杂度太高，不可取~ 我们有O(n)的算法~ 假设从编号为0的人开始报数，当然从编号为k的人开始报数的情况也是也可以解决的，只要稍微转化就可以，至于怎么解决？我们讲完从编号为0的人开始报数的情况就明白啦~ 我们从0编号开始报数，第一个出环的人m%n-1，剩下的n-1个人组成一个新的约瑟夫环，接下来从m%n开始报数，令k=m%n，新环表示为： k, k+1, k+2, ……n-1, 0, 1, 2, …..., k-2 我们对此环重新编号，根据上面的分析，编号并不会影响实际结果。 k → 0 k+1 → 1 k+2 → 2 ... k-2 → n-2 对应关系为：x’ = (x+k)%n (其中，x’是左侧的，x是右侧重新编号的) C语言课程设计报告约瑟夫环胡存夫 沈阳航空航天大学 课程设计报告 课程设计名称：C语言课程设计课程设计题目：约瑟夫环 院（系）：计算机学院 专业：计算机科学与技术班级：3410301 学号： 姓名：胡存夫 指导教师：丁一军 目录 1 课程设计介绍 ......................................................... 错误!未定义书签。 1.1课程设计内容及要求 ........................................... 错误!未定义书签。 1.2系统需求............................................................... 错误!未定义书签。 2 课程设计原理 ......................................................... 错误!未定义书签。 2.1课设题目粗略分析 ............................................... 错误!未定义书签。 2.2.1 功能模块图..................................................... 错误!未定义书签。 2.2.2 流程图分析..................................................... 错误!未定义书签。 3 调试与分析............................................................. 错误!未定义书签。 3.1调试过程............................................................... 错误!未定义书签。参考文献 .................................................................... 错误!未定义书签。附录（关键部分程序清单） ................................... 错误!未定义书签。 一、实验题目： 约瑟夫环问题。 二、实验内容： 设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m 的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 实现：用一个不带头结点的单向循环链表表示上述约瑟夫环，结点结构可定义为： typedef struct node{ Array int pos;//位置 int code;//密码 struct node *next; }JosephNode,* JosephList;; 三、程序源代码： # include 数据结构课程设计题目 1.目的 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 2.内容 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 约瑟夫环问题的描述是：设编号为1，2，…，n的n个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。 3.设计： 1）对设计内容进行分析 2）逻辑设计 1、循环链表抽象数据类型定义 typedef struct LNode//定义单循环链表中节点的结构 { int num;//编号 int pwd;//password struct LNode *next;//指向下一结点的指针 }LNode; 2、本程序包含一下几个模块 （1）构造结点模块 LNode *createNode(int m_num,int m_pwd) { 图2 约瑟夫环原理演示图 约瑟夫环问题如下：已知n 个人(n>=1)围桌一园桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m 的那个人出列。他的下一个人又从1开始报数，数到m 的那个人又出列。依此规则重复下去，直到所有人全部出列。求解最后一个出列的人的编号。 本次实验是以顺序表求解约瑟夫环问题，程序流程图及程序运行结果如下： 程序代码如下： #include 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<<"尾指针异常!"< 《约瑟夫环》实验报告 专业：网络工程班级 学号姓名 一、问题描述： 约瑟夫问题的一种描述是：编号为1，2，……，n点的n个人按顺时针方向围坐一个圈，每人持有一个密码。一开始选一个正整数作为报数上限值m，从第一个人开始从顺时针方向自1开始报数，报到m时停止。报到m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始从新从1报数，如此下去，直达所有人出列。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。 测试数据：m的初始值为20；n=7，7个人的密码依次是3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序为6，1，4，7，2，3，5） 二、程序设计的基本思想，原理和算法描述： 采用结构体定义单链表，格式为：struct Lnode {int number; int password; struct Lnode*next; }Lnode,*p,*q,*head; 其中number是人的排列序号，password是各人所持有的密码值，next是节点指针。Lnode是节点变量，p、q是节点，head是头指针。 程序的代码：定义变量n，i,m,j 输入人的数量n If n<=0或n>30 重新输入n值 当0 约瑟夫环问题的简单解法（数学公式法） 关于约瑟夫环问题，无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达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-2 – n-2 k-1 – n-1 解x’ —- 解为x 注意x’就是最终的解 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单， 相信大家都可以推出来：x’=(x+k)%n 如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况—- 这显然就是一个倒推问题！下面举例说明： 假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 m=2。那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换： 现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。x怎么求出呢？继续推导吧。0,1,2,3,4,，同样是第二个1出列，变为（2,3,4,0），转换下为 很简单，同样的道理，公式又出来了，x=(x”+m)%5，这里变成5了。即求n-1个人的问题就是找出n-2的人的解，n-2就是要找出n-3，等等 因此，就可以回去看上面的推导过程了。 好了，思路出来了，下面写递推公式： 令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n] 递推公式 f[i]=(f[i-1]+m)%i; (i1) 算法：n个人围成一圈，每个人都有一个互不相同的密码，该密码是一个整数值，选择一个人作为起点，然后顺时针从1到k（k为起始点手中的密码值）数数。数到k的人退出圈子，然后从下一个人开始继续从1到j（j为刚退出圈子人的密码数）数数，数到j的人退出圈子。重复上述操作，直到最后一人 代码如下： # include 实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级000 学号000 姓名神刀公 子 1.问题描述 约瑟夫环问题 （1）问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 （2）基本要求 建立模型，确定存储结构。 对任意n个人，密码为m，实现约瑟夫环问题。 出圈的顺序可以依次输出，也可以用一个数组存储。 （3）思考： 采用顺序存储结构如何实现约瑟夫环问题？ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct Node { int data; //数据域 Node *next; //next指针指向下一个结点 }; 3.算法设计 问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。 设计流程图如图1.1所示。 开始 输出提示语 输入所需参数 创建链表，计算，得出结果 输出结果 结束 图1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插入链接，构造为循环链表。 NODE *link(int number) { NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); head->value=i; p=head; for(i=2; i<=number; i++) 实验报告 1.问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 2.设计思想 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针first指示。 最后，设计约瑟夫环问题的算法。 3. 基本要求 ●建立模型，确定存储结构。 ●对任意n个人，密码为m，实现约瑟夫环问题。 ●出圈的顺序可以依次输出，也可以用一个数组存储。 4.算法设计 1.系统里面自己定义了一个fun1函数，用来执行创建循环列表的功能。 YUE * fun1(int n) { YUE *head,*p1,*p2; int i; for(i=1;i<=n;i++) { p1=(YUE *)malloc(S()); if(i==1) head=p1; else p2->next=p1; p1->n=i; p2=p1; } p1->next=head; return head; } 2.系统里面另外有定义了一个fun2的函数，用来执行满足条件出队列的功能。 int fun2(YUE *p) { YUE *p2; int n; p2=p->next; n=p2->n; p->next=p2->next; free(p2); return n; } 3.在程序的开端，首先定义了一个链表结构。 typedef struct yuesefu { int n; struct yuesefu *next; } YUE; 4.在程序的中间部分，是程序的主函数，用来判断条件的满足与否。 YUE * fun1(int n); int fun2(YUE *p); int main() { int m,i,n,j,s; YUE *p,*p2; printf("n="); scanf("%d",&n); printf("m="); scanf("%d",&m); printf("i="); 顺序表实现约瑟夫环的问题C语言 计算机科学与工程学院 《算法与数据结构》试验报告[一] 10级计算机工程02计算机大楼计工教研专业班级试验地点室学生学号1005080222 指导教师蔡琼学生姓名肖宇博试验时间 2012-2-29 试验项目算法与数据结构 试验类别基础性() 设计性() 综合性(?) 其它( ) (1)掌握用VC++上机调试线性表的基本方法; 试(2)掌握顺序表的存储结构以及基本运算的实现。验 目的求及 要 成绩评定表 类别评分标准分值得分合计 积极出勤、遵守纪律 上机表现 30分 主动完成设计任务 程序代码规范、功能正确 程序与报告 70分 报告详实完整、体现收获 计算机科学与工程学院 备注: 评阅教师: 日期: 年月日 试验内容 一、实验目的和要求 1、实验目的: (1)掌握用VC++上机调试线性表的基本方法; (2)掌握顺序表的存储结构以及基本运算的实现。 2、实验内容 约瑟夫环问题:设编号为1，2，3，……，n的n(n>0)个人按顺 时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下 一个人开始重新从1报数，报到m时停止并且报m的人出列。如此下 去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对 任意给定的m和n，求出出列编号序列。 3、实验要求:用顺序表实现。 二、设计分析 根据实验要求，采用顺序表来完成本次实验。 实验中定义了两个顺序表，一个用来存储n个人的序号，另一个用来存储n个人的出队顺序及序号。 程序中充分考虑了如果出队的元素大于队列的元素个数时应该有的情况，如果出现这样的错误就提示～否则继续出队～ 三、源程序代码 #include 数据结构上机实验报告 02090401 12 雒文杰题目：约瑟夫环问题 一．问题描述 设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。 二．基本要求 运用循环单链表解决约瑟夫环问题。 三．算法说明 本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。 四．源程序清单 #include {new_node=(clink)malloc(sizeof(cnode)); if(!new_node) return NULL; new_node->data=array[i]; new_node->order=i+1; new_node->next=NULL; before->next=new_node; before=new_node; } new_node->next=head; return head; } void main() {clink head,ptr; int find,j,i,a,list[n]; printf("Please input 'm'\n"); for(i=0;i （一）基本问题 1.问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m 时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。建立模型，确定存储结构。对任意n个人，密码为m，实现约瑟夫环问题。 2.数据结构设计 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针first指示 3.算法设计 1、工作指针first，r，s，p，q初始化 2、输入人数（n）和报数（m） 3、循环n次，用尾插法创建链表 Node *q; for(int i=1;i<=n;i++) { Node *p; p=new Node; p-> data =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);} 4、输入报数的起始人号数k; 5、Node *q = new Node;计数器初始化i=1; 6、循环n次删除结点并报出位置（其中第一个人后移k个） 当ic语言实现约瑟夫环问题
约瑟夫环问题讲解
约瑟夫问题
约 瑟 夫 环 问 题 的 三 种 解 法 ( 2 0 2 0 )
顺序表实现约瑟夫环的问题c语言
约 瑟 夫 环 问 题 的 三 种 解 法
数据结构经典题目及c语言代码
约瑟夫环问题
C语言课程设计报告约瑟夫环胡存夫
约瑟夫环问题
数据结构实验约瑟夫环..
约瑟夫环问题源代码(C语言)
C语言实现约瑟夫环
约 瑟 夫 环 问 题 的 三 种 解 法
约瑟夫问题的C语言算法(循环链表)
约瑟夫环问题 实验报告完整版
约瑟夫环问题
顺序表实现约瑟夫环的问题C语言
题目：约瑟夫环问题
c语言实现约瑟夫环问题解析