//***********************************************************************//
//************************求解約瑟夫環問題*******************************//
//*******************實習1　1.2***難度系數3******************************//
//***********************************************************************//
#include <iostream.h>
//定義一個JOSE結構及一個結構指針變量.
 typedef struct Jose
{
    int code,pwd;          //編號，密碼
    struct Jose *next;
}*LinkList;


//主函數
int main()
{    
    int i,j,m,n;                     //m為報數上限值，n為總人.
    
	//輸入總人數n，以及輸入從第m個人開始.
	cout<<"Please input n=";
	cin>>n;
    if(n<2) 
	{
		cout<<"ERROR:n is wrong!";
		return -1;
	}
    cout<<"Please input m=";
	cin>>m;
    if(m<1||m>n)
	{
		cout<<"ERROR:m is a wrong!";
		return -1;
	}
    
	
	
	LinkList first,last,p,q;          //first為頭結點指針，last為尾結點指針，p為當前指針的前一指針，q為當前指針.

	//建立n個結點的單向循環鏈表.
    first=new Jose;
    p=first;
    for(i=1;i<n;i++)
    {
        q=new Jose;
        p->next=q;
        p=q;
    }
    last=q;
    last->next=first;


	//獲取每個人的密碼.
    p=first;
    for(i=1;i<=n;i++)
    {
        p->code=i;
        cout<<"Please input No."<<i<<"'s password:";
        cin>>p->pwd;
        p=p->next;
    } 
	//輸出序列.
    cout<<"output sequence result is:";
    p=last;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<m;j++) p=p->next;
        q=p->next;
        m=q->pwd;
        cout<<" "<<q->code;
		p->next=q->next;
        
    } 
	cout<<endl;
	//最后獲勝者.
	cout<<"The last winner is:"<<q->code<<endl;
	delete q;
	delete first;
	return 0;
}