josphs.cpp

采用带头结点的约瑟夫算法

// JOSPHS.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "JOSPHS.H"

int main(int argc, char* argv[])
{	int n,s,m;
	
	cout<<"==========================JOSOPHU PROBLEM================================="<<endl;
		cout<<"\t(n stand for the total number,s for the start pos,m for dk)"<<endl;
	cout<<" Please input \"n,s,m\" as below"<<endl;
	cout<<" For example:\t3 1 2"<<endl;
	cout<<" ";
	cin>>n>>s>>m;
	if(s>n){s=s%n;}
//
	LinkList L,p,pre;
	L=(LinkList) malloc(sizeof(LNode));
	L->next=NULL;
	for(int i=n;i>0;--i)
	{p=(LinkList) malloc(sizeof(LNode));
	 p->data=i;
	 p->next=L->next;
	 L->next=p;
	}
	
    //Init LinkList L
	for(i=1,p=L->next;i<s;i++)
	{pre=p;
	 p=p->next;
	}//To find the start place p

  cout<<"the array:"<<"\t";
  pre=L;
while(n>1){
  for(i=1;i<m;i++)
  {pre=p;
   if(p->next==NULL){
	  pre=L; p=L->next;}
	else p=p->next;
  } 
   cout<<p->data<<"\t";
   pre->next=p->next;
   free(p);
  if(pre->next==NULL) 
	  p=pre;
  else	
	  p=pre->next;
   n--;
  }
  cout<<p->data<<endl;
	return 0;
}