约瑟夫问题--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;

}