约瑟夫环问题——4个解法总结（C语言）

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

样例输入

6 2

样例输出

5

样例输入

12 4

样例输出

1

1.循环链表实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct link
{
int data;
link* next;
}link;

int main()
{
int n, m;
int i;
printf("请输入(n/m)：");
scanf("%d%d", &n, &m);

link* head = (link*)malloc(sizeof(link));//头节点
head->data = -1;
head->next = NULL;

link* tail, * p, * q;

tail = head;//构造循环节点
for (i = 0; i < n; i++)
{
p = (link*)malloc(sizeof(link));
p->data = i + 1;
tail->next = p;
p->next = head->next;
tail = p;
}

p = head->next;//p为要删除的那一个指针，q为p的前一个位置的指针
q = tail;
i = 1;//用i来报数
while (p != q)//直到两个指针相同时，循环链表内除开头节点外只有一个节点了
{
if (i == m)//当报数为m时，删除p，同时让i=1
{
i = 1;
q->next = p->next;
free(p);
p = q->next;
}
else
{
q = p;
p = p->next;
i++;
}
}
printf("最后留下的猴子序号为: %d", p->data);
free(p);
free(head);
return 0;
}

2.数组标志位实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main()
{
int n, m;
int i;
int monkey[300] = { 0 };

printf("请输入（n/m): ");
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
{
monkey[i] = i + 1;
}

int number = n;//记录此时数组中有效元素的个数
int count = 1;//用来报数
int pos = 0;//记录数组下标位置
while (number > 1)
{
if (monkey[pos] > 0)
{
if (count == m)
{
monkey[pos] = 0;
count = 1;
number--;
pos = (pos + 1) % n;
}
else
{
count++;
pos = (pos + 1) % n;
}
}
else
pos = (pos + 1) % n;
}

for (i = 0; i < n; i++)
if (monkey[i] > 0)
printf("最后留下的猴子序号为：%d\n", monkey[i]);

return 0;
}

3.数组模拟(循环)链表实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main()
{
int n, m;
int monkey[300] = { 0 };
int i;

printf("请输入（n/m）: ");
scanf("%d%d", &n, &m);
for (i = 0; i < n - 1; i++)//数组模拟循环链表，数组的值相当于链表的next，指向下一个数组结点的下标
{
monkey[i] = i + 1;
}
monkey[i] = 0;

int number = n;//记录当前数组有效元素个数
int count = 1;//用来报数
int pos = 0;
int prior = n - 1;

while (number > 1)//或者while(prior!=pos)
{
if (count != m)
{
count++;
prior = pos;
pos = monkey[pos];
}
else
{
monkey[prior] = monkey[pos];
monkey[pos] = -1;
pos = monkey[prior];
count = 1;
number--;
}
}
printf("最后留下的猴子序号为：%d\n", pos + 1);
return 0;
}

4.数学方法（原理自己百度查）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main()
{
int n, m;
printf("请输入（n/m）：");
scanf("%d%d", &n, &m);
int pos = 0;
for (int i = 2; i < n + 1; i++)
{
pos = (pos + m) % i;
}
printf("最后留下的猴子序号为：%d\n", pos + 1);
return 0;
}

原文地址：https://blog.csdn.net/2301_80163571/article/details/143452200

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！