约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

方法1：使用stl：：list模拟环形链表，参考剑指offer

代码：

#include <iostream>
#include <list>
using namespace std;

int lastNumber(unsigned int n,unsigned int m ){
	if(n < 1 || m < 1)
		return -1;
	list<int> lNum;
	int i=0;
	for( i=0;i < n;i ++ ){
		lNum.push_back(i);
	}
	list<int>::iterator cur=lNum.begin();
	while(lNum.size() > 1){
		//每次都为i 开始值 ，m值考虑好长时间，这次记住了
		for(i=1;i<m;i++){
			cur++;
			if(lNum.end() == cur){
				cur = lNum.begin();
			}
		}
		list<int>::iterator next = ++cur;
		if(next == lNum.end())
			next = lNum.begin();
		cout<< * (--cur);
		lNum.erase(cur);
		cur = next;
	}
	return *cur;

}


int main()
{    
	cout<<endl<<lastNumber(5,3);
    return 0;
}

2 使用环形链表

#include <iostream>
#include <list>
using namespace std;


typedef struct list{
	int data;
	struct list * pNext;
}List,*pList;

void createList(pList &pHead ,unsigned int m, unsigned int n){
	if(m < 1 || n <1 )
		return ;
	pList p=pHead,q;
	bool isFirst = true;
	for(int i=0;i < m ;i++){
		q=(pList)malloc(sizeof(List));
		q->data= http://www.mamicode.com/i ;>
运行结果为：


3 利用递归 ，查找其中规律


#include <iostream>
#include <list>
using namespace std;

//使用for循环解决
int lastRemainNum(unsigned int m , unsigned int n){
	if(m < 1 || n < 1)
		return -1;
	int last = 0;
	for(int i=2; i <= m ;i++){
		last =(last  + n) % i;
	//	cout << last << " ";
	}
	
	return last;
}

//使用递归
int lastNum(unsigned int m,unsigned int n){
	if(m < 1 || n < 1)
		return -1;
	if(m == 1)
		return 0;
	return (lastNum(m-1,n) + n) % m;

}

int main()
{   cout<< lastNum(5,3);
    cout<<  lastRemainNum(5,3);
    return 0;
}

运行结果：