jose.cpp

jose.cpp本演示程序中

//***********************************************************************//
//************************求解约瑟夫环问题*******************************//
//*******************实习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;
}