3356705.txt

约瑟夫问题的一种描述是：编号为1

/*约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，没人持有一个密码。一开始人选一个正整数作为报数上限值m，从第一个人开始按顺时针自1开始报数，报到m是停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。*/

#include <stdio.h>
#include <stdlib.h>
#define NULL 0

struct node                 // create structure
{
	int num;
	int cipher;
	struct node * next;
};

typedef struct node line;
typedef struct node * link;

link createlist(int n);    //function creation.
void golist(link head, int m);   // go away function.

link createlist(int n)      // Create to set up the circulation connect the list.

{
	int i;
	link head,ptr,ptr1;

    head=(link)malloc(sizeof(line));
	if(!head)
	{   printf("memory falt.\n");
		return NULL;
	}
	ptr=head;
	for(i=0;i<n;i++)   //create node.         
	{
		ptr1=(link)malloc(sizeof(line));
		if(!ptr1)
			return NULL;
		ptr1->next=NULL;
		ptr1->num=i+1;
		printf("please input %dTh people cipher:\n",i+1);
		scanf("%d",&ptr1->cipher);
		ptr->next=ptr1;
		ptr=ptr->next;
	} 
	head=head->next;    //  Throw away head node.
	ptr1->next=head;    //  Direction a head node.
	return head;
}

void golist(link head ,int m)         // create going away function.
{
	int i;
	link p1,p2,s;
	p1=head;
	while(p1!=NULL)        // Whether judgment ends or not.
       
    {
		for(i=1;i<m;i++)
		{
			p2=p1;
			p1=p1->next;
		}
		printf("** %dTh people go away!",p1->num);
		printf("-----Cipher is %d.   **\n",p1->cipher);
		m=p1->cipher;            // The password of a row gives m.
		if(p1->next!=p1)         // Connect the list inside not only a node.
		{ 
			p2->next=p1->next;
			s=p1;
			p1=p1->next;
			free(s);
		}
		else 
		{
			free(p1);
		    head=NULL;
			break; 
		}
	}
}

void main()
{
	int n,m;
	link head;

	printf("please input whole people number:\n");
	scanf("%d",&n);  
	if(n==0)    
	   printf("This is a space Circle.\n");
	else if(n==1) 
	   printf("This Circle is only one people.\n");
    else
	{
       head=createlist(n);    
       printf("please input first cipher:\n");
	   m=20;
	   scanf("%d",&m);	
	   golist(head,m);   
	}
}