首页 > 代码库 > 约瑟夫问题--list模拟循环链表
约瑟夫问题--list模拟循环链表
约瑟夫问题
Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^
题目描写叙述
n个人想玩残酷的死亡游戏,游戏规则例如以下:
n个人进行编号,分别从1到n,排成一个圈,顺时针从1開始数到m,数到m的人被杀,剩下的人继续游戏,活到最后的一个人是胜利者。
请输出最后一个人的编号。
n个人进行编号,分别从1到n,排成一个圈,顺时针从1開始数到m,数到m的人被杀,剩下的人继续游戏,活到最后的一个人是胜利者。
请输出最后一个人的编号。
输入
输入n和m值。
输出
输出胜利者的编号。
演示样例输入
5 3
演示样例输出
4
首先说一下写这个之前我是准备徒手艹链表的,可惜意志力实在不咋滴,再加上手头上没课本,之前我有看过C语言版的链表实现,但没动手敲过,都是偷懒用list水过,list是双向链表,但约瑟夫这个问题吧,明显是用循环链表来完毕的,问题来了,本渣不会艹链表啊,木办法仅仅能用list来胡搞了
#include <stdio.h> #include <iostream> #include <algorithm> #include <list> using namespace std; int main() { int m,n,i; cin>>n>>m; list <int> node; list <int>::iterator j; for(i=1;i<=n;i++) node.push_back(i); //编号 j=node.begin(); while(node.size()>1) //当链表中仅仅剩一个元素时结束 { for(i=1;i<m;i++) //第k遍遍历 { if(j!=node.end()) j++; else //重点来了 { j=node.begin(); j++; //一開始忘记写这个了 事实上当j=node.end()时就意味着j已经指向node.begin()了,仅仅是由于这不是循环链表,我们须要手动把它改过来 } } if(j!=node.end()) node.erase(j++); else //同上 { j=node.begin(); node.erase(j++); } } cout<<node.front()<<endl; return 0; }
约瑟夫问题--list模拟循环链表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。