循環連結清單解決約瑟夫問題（簡化版）

約瑟夫環是一個經典的數學的應用問題：已知N個人（以編号1，2，3...N分别表示）圍坐在一張圓桌周圍。從編号為1的人開始報數，數到M的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。

這個代碼非常簡短，但還是利用循環連結清單完成了求解約瑟夫問題的功能

代碼如下：

#include<iostream>
#include<cassert>
using namespace std;
typedef struct Node
{
	int item;
	struct Node *next;
}ListNode,*List;
int main()
{
	int M;//規則（隔M個數）
	int N;//人數（N個人）
	int a;//編号
	int i;
	cout<<"input the N and M"<<endl;
	cin>>N>>M;
	List head=(List)malloc(sizeof(ListNode));
	assert(head!=NULL);
	cin>>a;
	head->item=a;
	head->next=head;
	ListNode *p=head;
	for(i=2;i<=N;i++)//構造循環連結清單，值為1的結點為連結清單頭
	{
		cin>>a;
		p->next=(List)malloc(sizeof(ListNode));
		p=p->next;
		p->item=a;
		p->next=head;
	}
	while(p!=p->next)//while循環開始時，p指向連結清單的尾結點
	{
		for(i=1;i<M;i++)
			p=p->next;
		ListNode *targetnode=p->next;
		cout<<targetnode->item<<"出局"<<endl;
		p->next=p->next->next;
		free(targetnode);
	}
	cout<<p->item<<endl;
	return 0;
}