猴子选王——约瑟夫环问题

题目

一堆猴子都有编号，编号是1，2，3 …m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

一、解题思路 1.向量解法（数组解法）：

第一步 首先将所有猴子进行初步编号（从1到n）4 第二步 因为所有猴子只有两种状态：淘汰与未被淘汰。所以将所有猴子进行状态编 号（0表示未淘汰，1表示被淘汰），先将所有猴子标记为0，表示未淘汰。 第三步:在主函数里开始循环报数淘汰猴子，用另一个计数变量K来统计报数猴子，当k和要淘汰的猴子报的数字相等时，淘汰该猴子，k值清零再次循环，知道猴子剩余数量j等于1时结束循环 第四步：遍历数组，找到状态参数为0的猴子就是猴子王

2.链表解法:

第一步：构建循环环状链表，存放猴子编号 第二步：报数找到淘汰数字前一个猴子，对应就能找到要被淘汰的猴子 第三步：删除淘汰猴子的结点，释放空间 第四步：让被淘汰猴子的下一个结点开始报数，循环此过程 第五步：知道猴子剩余数量为1时候，结束循环，函数返回剩下那个猴子的编号信息。即猴王编号

二、方法优缺点 1.向量法

1）优点： 1.数组能够支持下标访问，访问效率很高； 2.查找速度很快；

2）缺点： 1.数组的大小要提前声明，容易造成大额空间浪费，也容易出现空间不足需要重新定义数组的情况； 2.元素的插入删除也不方便操作，只能使用状态变量来标记猴子；

2.链表法：

1）优点： 1.插入，删除操作很便捷，在结点上操作十分灵活。 2.大小不固定，容易扩展； 3.内存的利用效率也很高，不会浪费内存；

2）缺点： 1.每次遍历数据时只能从头开始，查找效率很低。 2.随机访问效率低

三、流程图

1.向量法（数组法） 2.链表法

四、实验代码

#include 
#include 

#define N 100 //宏定义向量长度
int main()
{
    int a[N],n,m;
    printf("请输入猴子的个数：\n");
    scanf("%d",&m);
    printf("请输入要淘汰的数字：\n");
    scanf("%d",&n);
    int i,j,k;
    k=0;
    j=m;// 计数变量，用来统计剩余猴子数量
    for(i=0; inext = p;//构建循环链表
    for(int i=2 ; idata=i;
        t->next=p->next;
        p->next=t;
        p=p->next;//这个循环不断申请空间，将存放信息的结点插入链表
    }
    p=head;//形成闭环，循环链表
    q=head;//在后面用来寻找淘汰猴子的前驱
    int j=n;//j用来统计剩余猴子数目
    while(j!=1)//当j等于1，即剩余一个猴子时候结束循环
    {
        for(int i=1; inext;
        }
        while (q->next != p)//让q指向要淘汰猴子的前驱
        {
            q = q->next;
        }
        q->next=p->next;//删除这个淘汰猴子的结点
        p = p->next;//让p从被淘汰猴子的后一位再开始新的报数
        j--;//淘汰一个猴子，总猴子数目减一
    }
    int king = p->data;//返回剩余那个猴子的编号
	free(p); 
    return king;
}

int main()
{
    int t,m,n;
    printf("请输入猴子的个数：\n");
    scanf("%d",&m);
    printf("请输入要淘汰的数字：\n");
    scanf("%d",&n);
    t=create(m,n);
    printf("最后的猴王是最初的第%d个猴子",t);
    return 0;
}

五、运行截图