首页 > 代码库 > 约瑟夫问题--list模拟循环链表

约瑟夫问题--list模拟循环链表

约瑟夫问题

Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^

题目描写叙述

n个人想玩残酷的死亡游戏,游戏规则例如以下:

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模拟循环链表