C++数据结构--循环链表的应用--解决约瑟夫问题

偏执的太偏执、 2021-12-01 15:46 216阅读 0赞

**解决问题过程图解**

**![20130731102002984][]**

**实现代码：**

**//n个竞争者，每隔m个竞争者就淘汰一个   
//返回值为胜出的竞争者   
int josephus(int n,int m)  
\{  
list<int> lst;  
for(int i=1;i<=n;i++) //给\[1,n\]个竞争者编号   
\{   
lst.push\_back(i);  
\}   
  
cout<<"befor erase: "<<endl;  
for(int x:lst)  
\{   
cout<<x<<ends;  
\}  
cout<<endl;  
  
auto p=lst.begin(); //指向第一个竞争者   
while(lst.size()!=1) //循环淘汰竞争者，直到只剩下一个   
\{   
for(int i=0;i<m-1;i++)  
\{   
p++;   
  
 if(p==lst.end()) //当p到达链表的表尾时，p加1，因为(lst.end())不指向任何元素   
 \{   
  
p++;  
 \}  
  
\}   
  
  
  
 cout<<"erase num: "<<\*p<<endl;  
  
 lst.erase(p++);  
 if(p==lst.end()) //假如上一句删除的是最后一个元素，则p++到达了lst.end();   
\{   
  
p++;  
\}  
\}   
  
  
return \*p;  
\}  
  
  
int main()  
\{   
 int res;  
 res=josephus(6,3);  
 cout<<endl;  
 cout<<"the winner is: "<<res;  
  
return 0;**

**\}**

**运行结果：**

**![Center][]**

[20130731102002984]: /images/20211201/c7d4116f65c140ee9e7e9594395c934f.png
[Center]: /images/20211201/fe5394ac23dd47d7953892af6701c423.png

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法：约瑟夫问题（循环链表解决）

Josephu 问题 Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从

傷城~/ 2023年01月03日 14:29/ 0 赞/ 134 阅读

相关 [数据结构]利用循环链表实现约瑟夫问题

约瑟夫问题由41个人围成一圈，开始报数，报到3的人自杀，之后重新报数，直到最后剩下一个人存活。如何表示出这41个人的死亡过程，可以利用循环链表进行表示。 1

超、凢脫俗/ 2022年10月22日 04:08/ 0 赞/ 168 阅读

相关约瑟夫问题——循环链表

think: 1顺序建立循环链表+循环链表中的符合题意的元素结点的删除 2注意只有一个人玩死亡游戏的情况 [sdut原题链接][sdut] 约瑟夫问题 Time

秒速五厘米/ 2022年09月28日 11:46/ 0 赞/ 181 阅读

相关数据结构循环链表的应用：约瑟夫环问题

include <stdio.h> include <stdlib.h> include <iostream.h> defin

墨蓝/ 2022年09月19日 01:29/ 0 赞/ 152 阅读

相关约瑟夫问题(单向循环链表应用实例)

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于

ゞ浴缸里的玫瑰/ 2022年08月08日 06:14/ 0 赞/ 194 阅读

相关数据结构-循环单链表之约瑟夫问题

约瑟夫问题的由来：据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决

柔情只为你懂/ 2022年05月25日 06:46/ 0 赞/ 183 阅读

相关循环链表解决约瑟夫环问题

　　约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。　　什么是约瑟夫环？　　“约瑟

Love The Way You Lie/ 2022年04月10日 08:22/ 0 赞/ 219 阅读

相关【数据结构】单向循环链表应用-约瑟夫环

编号1,2,...n的n个人按顺时针方向围坐在一圈,每人持有一个密码.一开始任选一个正整数作为报数上限值m,从第一个开始按顺时针方向自1开始顺序报数,报到m时停止报数.报m的人

落日映苍穹つ/ 2022年03月07日 05:40/ 0 赞/ 214 阅读

相关 C++数据结构--循环链表的应用--解决约瑟夫问题

解决问题过程图解 ![20130731102002984][] 实现代码： //n个竞争者，每隔m个竞争者就淘汰一个 //返回值为胜

偏执的太偏执、/ 2021年12月01日 15:46/ 0 赞/ 217 阅读

相关 C循环链表解决约瑟夫斯问题

循环链表解决约瑟夫斯问题问题描述：设有n个人围坐成一个圆圈，按一定指向方向，从第s个人开始报数，数到m的人出列，然后从下一个人重新报数，数到m的人又出列，…，直到n

蔚落/ 2021年07月16日 13:38/ 0 赞/ 361 阅读