约瑟夫问题 刺骨的言语ヽ痛彻心扉 2022-09-19 13:29 201阅读 0赞 **约瑟夫问题** **作者:Ackarlix** 这是一个非常经典的问题:n个骑士编号1,2,...,n,围坐在圆桌旁,编号为k的骑士从1开始报数,报到m的骑士出列,然后下一个位置再从1开始报数,找出最后留在圆桌旁的骑士编号。 这个问题可以用没有头结点的循环链表解决,数据域存放骑士的编号,出列的骑士,删除其对应的结点,最后剩下的那个结点就是问题所求的骑士编号。程序如下: \#define OK 1 \#define ERROR 0 \#include <iostream.h> \#include <malloc.h> int N; //骑士总数 typedef int Status; // 定义循环链表 typedef struct LNode\{ int data; LNode \*next; \}LNode,\*LinkList; // 构造空循环链表 Status InitList(LinkList &L)\{ L=(LinkList)malloc(sizeof(LNode)); L->next=L; return OK; \} // 第i个位置之前插入元素e Status ListInsert(LinkList &L,int i,int e)\{ if(i<1) return ERROR; //插入位置不合理 int j=0; LinkList p=L,s; while(j<i-1)\{ //寻找第i-1个结点 p=p->next; j++; \} s=(LinkList)malloc(sizeof(LNode)); //生成新结点,插入L中 s->data=e; s->next=p->next; p->next=s; return OK; \} // 删除结点s Status ListDelete(LinkList &L,LinkList &s)\{ LinkList p=L; while((p->next)!=s)\{ //寻找结点s p=p->next; \} p->next=s->next; //删除结点s if(s==L) L=s->next; free(s); return OK; \} // 初始化循环链表 Status PutList(LinkList &L)\{ int i; L->data=1; for (i=2;i<=N ; i++)\{ ListInsert(L,i-1,i); \} return OK; \} // 取第i个结点的地址,赋给结点s Status GetElem(LinkList L,int i,LinkList &s)\{ if(i<1) return ERROR; //位置不合理 int j=1; LinkList p; p=L; while(j<i)\{ //寻找第i个结点 p=p->next; j++; \} s=p; return OK; \} // 数i个结点,删除最后数的结点,返回后面结点的地址 Status ElemCount(LinkList &L,int i,LinkList &s)\{ LinkList p=s; while(i!=1)\{ //数i个结点 p=p->next; i--; \} s=p->next; //结点s返回后面结点的地址 cout<<p->data<<' '; ListDelete(L,p); //删除最后数的结点 return OK; \} //Josephus 问题 void Josephus(int k,int m)\{ int total=N; LinkList L,s; InitList(L); PutList(L); GetElem(L,k,s); while(total!=1)\{ //直到只剩一人,循环结束 ElemCount(L,m,s); total--; \} cout<<endl<<"留下的骑士是"<<L->data<<endl; \} // 主函数 void main()\{ int k,m; char flag='y'; while(flag=='y')\{ cout<<"输入骑士个数,开始数的位置,每次数的人数:"; cin>>N>>k>>m; cout<<"骑士离开的顺序为:"; Josephus(k,m); cout<<"你想再试一次吗(按y继续): "; cin>>flag; cout<<endl; \} cout<<"程序结束."<<endl; \} 输出结果为(红色为键盘输入的数据): 输入骑士个数,开始数的位置,每次数的人数:13 1 3 骑士离开的顺序为:3 6 9 12 2 7 11 4 10 5 1 8 留下的骑士是13 你想再试一次吗(按y继续): y 输入骑士个数,开始数的位置,每次数的人数:10 2 2 骑士离开的顺序为:3 5 7 9 1 4 8 2 10 留下的骑士是6 你想再试一次吗(按y继续): n 程序结束.
相关 约瑟夫问题 约瑟夫问题 作者:Ackarlix 这是一个非常经典的问题:n个骑士编号1,2,...,n,围坐在圆桌旁,编号为k的骑士从1开始报数,报到m的骑士出列,然后下一个位置再从1 刺骨的言语ヽ痛彻心扉/ 2022年09月19日 13:29/ 0 赞/ 202 阅读
相关 约瑟夫问题 约瑟夫问题如下: n个人围成一圈,从1号开始报数,报到m就退出,剩下的人从下一个人开始继续报数。。。问最后剩下的是谁?也可问每个人的死亡顺序. 这一题在数据量比较小的 太过爱你忘了你带给我的痛/ 2022年08月10日 17:55/ 0 赞/ 147 阅读
相关 约瑟夫问题 约瑟夫环问题:一圈共有N个人,开始报数,报到M的人自杀,然 后重新开始报数,问最后自杀的人是谁? ![Center][] 第一种方法:循环思想 待我称王封你为后i/ 2022年08月08日 00:39/ 0 赞/ 181 阅读
相关 约瑟夫问题 适合队列初学者 \include<queue> //队列 头文件 queue<int>q; //定义队列q,I ゝ一世哀愁。/ 2022年08月04日 04:10/ 0 赞/ 176 阅读
相关 约瑟夫问题 Problem Description n个人想玩残酷的死亡游戏,游戏规则如下: n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被 £神魔★判官ぃ/ 2022年07月14日 12:44/ 0 赞/ 175 阅读
相关 约瑟夫问题 约瑟夫问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statis 分手后的思念是犯贱/ 2022年06月18日 05:24/ 0 赞/ 178 阅读
相关 约瑟夫问题 <table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2017 ╰半夏微凉°/ 2022年06月02日 08:57/ 0 赞/ 273 阅读
相关 约瑟夫问题 1.知识点:循环链表 2.题意:n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被杀,剩下的人继续游戏,请输出最后一个人的编号 3.注意事项: 心已赠人/ 2022年05月30日 04:46/ 0 赞/ 171 阅读
相关 约瑟夫问题 Problem Description n个人想玩残酷的死亡游戏,游戏规则如下: n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被杀,剩下的人 我就是我/ 2022年05月16日 06:06/ 0 赞/ 184 阅读
相关 约瑟夫问题 约瑟夫问题 ![在这里插入图片描述][20181114211743434.jpg] 题目描述: 开始有5个人围成圆形,从0号开始,数2个人,谁被数到就 灰太狼/ 2022年04月16日 00:46/ 0 赞/ 199 阅读
还没有评论,来说两句吧...