约瑟夫环问题——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;}}elsepos = (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; }