josephus.cpp

刚刚自己做的约瑟夫算法

#include<stdio.h>
#include<malloc.h>

#define MAX 100

struct node
{
	int no;
	int password;
	struct node *next;
}*tail;   /*tail为尾指针*/

struct node *CreatCircleList(int n,int f[MAX])  /*建立双向链表*/
{
	struct node *head,*p,*q;
	head=NULL; 
    p=q=(struct node*)malloc(sizeof(struct node));
	p->no=1;
	p->password=f[0];
	for(int i=1;i<n;i++)
	{
		if(i==1)
			head=p;
		else 
			q->next=p;
		q=p;
		p=(struct node*)malloc(sizeof(struct node));
		p->no=i+1;
		p->password=f[i];
	}
	q->next=p;
	p->next=head;
	tail=p;
	return head;
}

/*void print(struct node *head)
{
	struct node *p;
	p=head;
	printf("%d  ",p->no);
	p=p->next;
	while(p!=head){
		printf("%d  ",p->no);
		p=p->next;
	}
	printf("\n");
}*/

void Josephus(int n,int f[MAX])
{
	int m=10;
	struct node *p,*q;
	int i,k;
	k=m;
	CreatCircleList(n,f);
	p=tail;
	while(p!=p->next)
	{
		if(m>n)
			if(!m%n)
				k=n;
		for(i=1;i<=k-1;i++)
		{
			p=p->next;
		}
		printf("%d ",p->next->no);
		q=p->next;
		p->next=q->next;
		k=m=q->password;
		free(q);
		n--;
	}
	printf("%d\n",p->no);
}

main()
{
	int n;
	int f[MAX];

	printf("请输入人数n :");
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		f[i]=i+1;
	}
	Josephus(n,f);
}