猴子选大王问题

不念不忘少年蓝@ 2022-05-23 10:54 248阅读 0赞

猴子选大王（亚瑟夫换）的问题是数据结构和算法中常见的一类问题。可以使用循环队列实现，也可以使用链表实现。还可以使用数组的回溯法实现。

M只猴子要选大王，选举办法如下：所有猴子按1，2……n编号围成一圈，从第一号开始顺序1,2……m,凡是报m号的退出圈外，如此循环报数直到圈内只剩一只猴子时这只猴子就是大王。

方法一：链表法：

#include <stdio.h>
    #include <stdlib.h>
    #define n 8
    #define m 3
    typedef struct monkey
    {
      int num;
      struct monkey *next;
    } Monkey;
    int main()
    {
       Monkey *p,*head,*q;
       int i;
       head=p=q=(Monkey*)malloc(sizeof(Monkey));//建立头指针
       for(i=1;i<n;i++)     //给n个结点分配空间
       {
         p=(Monkey*)malloc(sizeof(Monkey));
         q->next=p;
         q=p;
       }
       q->next=head;   //建立循环链表
       p=head;
       printf("对猴子进行编号！\n");
       for(i=1;i<=n;i++) //给n只猴子分别建立顺序编号
       {
         p->num=i;
         printf("%d号猴子：%d\n",p->num,p->num);
         p=p->next;
       }
       i=0;    //初始化
       p=head; 
       while(1)
       {
    	   i++;
    	   printf("%d号猴子报：%d\n",p->num,i);
    	   if(p->next==p) break;   //判断还剩下最后一个结点时停止运行
    	   if(i==m)  //报道m的猴子淘汰
    	   {
    		   i=0;
    		   printf("%d号猴被淘汰\n",p->num);
    		   q->next=p->next;
    		   p=q->next;
    		   continue;
    	   }
    	   else
    	   {
    		   if(i==m-1) q=p;
    		   p=p->next;
    	   }
       }
       printf("胜出:%d号猴子",p->num);
    }

方法二：使用数组回溯法。

回溯法是：将猴子总个数循环，第一次循环都是将当前需要出圈的猴子排列到数组的末尾。这样全部猴子循环一遍后，数组头的猴子极为猴王。注意，循环一起找出第一个之后将之循环它之前的剩余数组。即程序中的for(i=MAX-1;i>=0;i--)

#include<stdio.h>
    #include<dos.h>
    #define MAX 30/*定义猴子总数*/ 
    int i,j,k,temp;
    int Monkey[MAX],S;
    
    void init()
    {
    	for(i=0;i<MAX;i++)
    		Monkey[i]=i+1;
    	for(i=0;i<MAX;i++)
    		printf("%d ",Monkey[i]);/*让猴子站成一圈*/
    	printf("\n");
    }
    void output()
    {
    	printf("猴子淘汰出圈的顺序是:\n\r");
    	for(i=MAX-1;i>=0;i--)
    		printf("第  %3d  只猴子出圈!\n\r",Monkey[i]);
    	printf("猴王是:第  %d   只猴子\n\r",Monkey[0]);
    }
    void main() 
    {
    
    	init();
    
    	printf("请输入出队的序数：");
    	scanf("%d",&S);/*读取猴子出队序数*/
    	
    	for(i=MAX-1;i>=0;i--)
    	{
    		for(k=1;k<=S;k++)
    		{
    			temp=Monkey[0];
    			for(j=0;j<i;j++)
    			{
    				Monkey[j]=Monkey[j+1];
    			}
    			Monkey[i]=temp;
    		}/*将每一次要出队的猴子排到队尾*/
    	}
    	output();
    }