king.c

猴子选大王

//猴子选大王
#include<stdio.h>
#include<math.h>
#define L sizeof(struct mon)
struct mon//定义猴子节点
{
	int num;
	struct mon *next;
};
void print1()//打印定义*号函数
{
	int i;
	for(i=0;i<16;i++)
		printf("*****");
	printf("\n");
}
void print()//定义打印提示信息函数
{
	print1();
	printf("     m只猴子要选大王,选举办法是:所有的猴子按1...m编号围坐一圈,从第1号开始按顺序1,2,...,n报数,凡报n号的退出圈外,如此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王。m和n是由键盘输入,打印出猴王的序号。\n");
	print1();
}

void main()
{
	struct mon *head,*p1,*p2,*p3,*p4;//声明头指针和四个工作指针
	int n,m,i,k;
	k=0;
	i=1;
	print();//打印提示信息
	printf("请输入猴子数m和退出圈外的报数n:");
	scanf("%d%d",&m,&n);//输入猴子数m和退出圈外的报数n
	printf("\n");
	for(i=1;i<=m;i++)//建立m个节点的循环链表
	{
		p1=(struct mon *)malloc(L);
		p1->num=i;
		if(i==1)
			head=p1;
		else p2->next=p1;
		p2=p1;
	}
	p2->next=head;//尾节点指向头节点
	p3=head;//p3指向当前节点
	p4=p2;//指向前一个节点
	while(p3->next!=p3)//当p3->next!=p3时说明循环链表有不止一个节点
	{
		k++;//当前节点报数
		if(fmod(k,n)==0)//如果报数是n的整数倍，删除当前节点
			p4->next=p3->next;
		else p4=p3;//若不是向前移动一个节点，到下一个猴子报数
		p3=p3->next;
	}
	printf("猴王是%d号猴子。\n",p3->num);//当循环链表中只剩下一个节点时，此节点就是“猴王”节点，打印此节点的序号
}