7-28 猴子选大王

猴子选大王(约瑟夫环问题)

题目

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：

输入在一行中给一个正整数N（≤1000）。

输出格式：

在一行中输出当选猴王的编号。

输入样例：

11

输出样例：

7

代码长度限制
16 KB
时间限制
400 ms
内存限制

解法一：
   #include<stdio.h>
    int main()
    {
        int n,i,sum=0;
        scanf("%d",&n);
        for(i=2;i<=n;i++)//i=2开始因为如果n就是一个人那么就直接是他，不必进行循环，直接得出。n个人的编码进行到n
            sum=(sum+3)%i;//3这里是报到M（规定淘汰的数）
        printf("%d",sum+1);//累计和加1就是最后那个人
       return 0;
    }

本解法是一个算法公式，此方法可用来找出n个数筛选出报出的规定数M，通过累加和加上1就是淘太n-1未剩余最后一个人的编码

解法二：
#include<stdio.h>
  
int main()
{
    int N;//这里是总人数
    
    int i=0,c=0,k=0;//i=0，是下标从1开始，如果从0开始i=-1.c代表被淘汰的人数。k用来计数要淘汰的数进行处理
    int a[1001]={0};//定义一个数组，初始化为0；
    scanf("%d",&N);

  while(c!=N-1)//注意这里要注意的是，我们要留下左后一个人不进入循环，因为最后一个人再进行一次，必然被淘汰，淘汰n-1个人即可，while循环这里n-1已经被处理，再到判断时进入循环就会变成n
    {
        i++;//i变成1，从一开始
        if(i > N) //如果i>N需要手动到初始位置达到一个环形的目的
            i=1;
        if(a[i]==0)//只有等于0，在可以进行报数，因为1已经被淘汰
        {
            k++;//计数目前报的数
            if(k==3)//如果报到3，进行淘汰
            {
                a[i]=1;
                c++;
                k=0;//k回复为0，进行下一个1~3
                
            }
        }
    }

    for(int j = 1;j <=N;j++)//找出最后一个为0的就是没被淘汰的人
    {
        if(a[j]==0)
            printf("%d",j);
    }
        
}

本解法更富容易懂，数组的方式，标记1为淘汰，注意在while语句出容易写成c!=N.用手动复位的方法，来进行首位相连。

解法三：
#include<stdio.h>

typedef struct node//typedefy 用来重名，struct node 为Node；
{
    int data;
    struct node*next;
}Node;

void ysflb(int N)//有N个人报到M的人出局
{
    Node*head = NULL,*p=NULL,*r=NULL;//head为头指针，指向链表的第一个节点，p指针用来循环淘汰，r用来删除淘汰节点
    head= (Node*)malloc(sizeof(Node));//为head申请一个空间
    if(head == NULL)//申请失败
    {
        printf("error");
    }
    head->data = 1;//从1开始编号
    head->next=NULL;//一开始链表只有一个节点Node，这个Node有两个域，data和next。
    //data从1开始，共需要N个节点，还需n-1个
    p=head;//p 指向head用来循环

    //尾插法增加节点
    for(int i = 2; i <=N;i++)
    {
        r = (Node*)malloc(sizeof(Node));//为r申请空间
        r->data = i;
        r->next=NULL;
        p->next=r;
        p=p->next;
    }
    //创建循环链表
    p->next = head;
    p=head;

    //约瑟夫环模拟
    while(p->next!=p)//循环到只剩他一个
    {
        for(int i = 1; i < 3;i++)
        {
            r = p;
            p=p->next;
        }

        r->next = p->next;
        p=p->next;
    }

    printf("%d",p->next->data);
}

int main()
{
   
    ysflb(11);
}
    

方法三：

# include<stdio.h>
using namespace std;
//用递归实现约瑟夫环问题
 
int ysfdg(int N,int M,int i)
{
    if(i==1)
    {
    	return (M-1+N)%N;
	}
    return (ysfdg(N-1,M,i-1)+M)%N;
}
 
 
int main()
{
	int N;
	cin>>N;  
	for(int i=1;i<=N;i++)
		cout<<ysfdg(N,3,i)<<" ";
	return 0;
}