约瑟夫环的两种常见解法：链表解法和递归解法（C++版）

约瑟夫环问题： 

       直观解法 ：链表解法。创建链表，判断删除节点是在N/2之前还是之后，进行模除运算，若在之前则从前往后遍历，保留间隔内数字，直到扫描到本次遍历结尾，输出本次遍历被删除的节点；若在之后，则从后往前遍历间隔内数字，直到扫面到本次遍历开头，输出本次遍历被删除的节点，逐次模除运算，最后的节点即为最终保留结果。

#include<iostream>
#include<list>

using namespace std;

int main()
{
	int mPrime, numLeft;
	int N, M;
	list<int> mList;
	list<int>::iterator iter;
	cout << "Enter the N(of people) & M(of passes before elimination ) : ";
	cin >> N >> M;
	numLeft = N;
	mPrime = M % N;
	for(int i = 1; i <= N; i++){
		mList.push_back(i);
	}
	iter = mList.begin();
	for(int i = 0; i < N; i++)
	{
		mPrime %= numLeft;
		//pass forward
		if(mPrime <= numLeft/2)
		{
			for(int j = 0; j < mPrime; j++)
			{
				iter++;
				if(iter == mList.end())
				{
					iter = mList.begin();
				}
			}	
		}
		//pass backworfd
		else
		{
			for(int j = 0; j < mPrime; j++)
			{
				if(iter == mList.begin())
				{
					iter = --mList.end();
				}
				else
				{
					iter--;
				}
			}
		}
		//output the selected one
		cout << *iter << " ";
		iter = mList.erase(iter);
		if(iter == mList.end())
		{
			iter = mList.begin();
		}
	}
	cout << " done ." << endl;
	return 0;
}

//run with N = 7, M = 3
           

      数学解法：第一个人出列后，剩余（N- 1）人组成新的约瑟夫环，递归调用，当最后只剩一人是即为所求结果。地推表达式：

#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::cin;
using std::list;

int josephus(int N, int M);

int main()
{
	int N, M;
	cout << "Enter the N(of people) & M(of passes before elimination ) : ";
	cin >> N >> M;
	cout << "the last one is : " << ( 1 + josephus(N, M)) << endl;
    return 0;
}

int josephus(int N, int M)
{
	if(N == 1)
	{
		return 0;
	}
	else
	{
		return (josephus(N - 1, M) + M) % N;
	}
}

//run with N = 7, M = 2 (passes before elimination)
           

practice makes perfects!