main.cpp

用环形链表解决的约瑟夫问题

#include"MyNode.h"
#include<iostream.h>
#include<limits.h>
void main(){
	int n,m;
	Node *p=NULL, *p_head=NULL ,*p_tmp=NULL;
	cout<<"This is a YSF(n,m) problem."<<endl;
//n people, m count, both n and m should >= 1
	//get and check integer n
	cout<<"Please input the integer n(n>=1).";
	cin>>n;
	while(cin.fail()||n<1){
		cin.clear(); //	equals to cin.clear(ios::goodbit);
		cin.ignore(INT_MAX, '\n');
		cout<<"Please input the integer n(n>=1).";
		cin>>n;
	}
	//get and check integer m
	cout<<"Please input the integer m(m>=1).";
	cin>>m;
	while(cin.fail()||m<1){
		cin.clear(); //	equals to cin.clear(ios::goodbit);
		cin.ignore(INT_MAX, '\n');
		cout<<"Please input the integer m(m>=1).";
		cin>>m;
	}

//construct the circular link structure
	for(int i=n;i>=1;i--){
		p_head = new Node(i,p);
        p=p_head;
    }

	//get to the tail, which is n.
	while(p->next)p=p->next;
    //connect to a circular
	p->next=p_head;

//go with the circular
	for(i=1;i<n;i++){ //do n-1 times to get rid of n-1 elements.
		for(int k=1;k<m;k++)p=p->next;
        p_tmp=p->next;
		p->next=p_tmp->next;
        cout<<endl<<"Get rid of:"<<p_tmp->entry;
		delete p_tmp;	
	}
//Print the left element
	cout<<endl<<"The left element is:"<<p->entry<<endl;
	delete p;

//just for exe under folder debug to run and wait to see the result
	cout<<"Press any key to quit.";
	cin.ignore(INT_MAX, '\n');
	cin.get();
}