求用数据结构（c语言版）编写选猴王的程序，

Question

如题所述

Answer 1

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

这个是最基础的约瑟夫环

用数组 或者链表实现均可。 

数组实现如下：

#include<stdio.h>
#define MAX 1005
int main(void){
    int monkey[MAX]={0};
    int n,temp=0;
    int monkeyOut=0;
    int count = 0;
    scanf("%d",&n);
    do{
        temp++;//逐个枚举圈中的所有位置
        if(temp>n)
            temp=1;//数组模拟环状，最后一个与第一个相连
        if(!monkey[temp])
            count++;//第t个位置上有人则报数
        else
            continue;
        if(count==3){//当前报的数是count
            count=0;//计数器清零
            monkey[temp]=1;//此猴已经退出，状态设为1，表示已经退出
            monkeyOut++;//退出猴的数目加一
        }
    }while((monkeyOut+1)!=n);
    int i;
    for(i=1;i<=n;++i){
        if(!monkey[i]){
            printf("%d\n",i);
            break;}
    }
    return 0;
}