0 问题描述
【人数为n，步长为m】有n个人，编号为1~n，从第一个人开始报数，从1开始报，报到m的人会死掉，然后从第m+1个人开始，重复以上过程。问最后一个人的编号是？
【人数为n，步长为3】一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？正整数N（≤1000）
1 数组模拟，m=3
这里使用数组暴力模拟的问题在于，已经被淘汰的猴子仍然会被循环到
#include <stdio.h>
int a[1001];// 1表示淘汰
int main(){
int n = 0,s=0,count=0;
int i = 0; // 数组下标
scanf("%d", &n);
while(s != n-1){ // 淘汰猴子的数量达到n-1时退出
i++;
if (i>n){
i = 1;
}
if(a[i] == 0){ // 只判断剩下的猴子
count++;
if (count %3==0){
a[i] = 1;
s++; // 每次淘汰一只猴子，直到s==n-1，剩下最后一只
}
}
}
for (int j=1;j<=n;j++){
if (a[j]==0){
printf("%d",j);
}
}
return(0);
}
2 链表模拟，m=3
image.png
链表方法很好理解，首尾相连成环，n个人中会淘汰n-1个人，所以外层循环是n-1，链表使用curr = curr->Next 2次，那么，就找到了数3的人，把它从链表中删除，这次外层循环就走完了，剩下n-2个人。
这里使用了单向链表，用一个last指向了出圈者的上一个人，以便于对出圈者进行链表删除操作。也可以考虑使用双向链表。时间复杂度O(nm)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node* Link;
struct Node{
int Num;
Link Next;
};
int main(){
int n=0;
scanf("%d", &n);
Link head = (Link) malloc(sizeof(struct Node));
head->Num = 1;
head->Next = NULL;
Link curr = head;
for (int i=2;i<=n;i++){
Link node = (Link) malloc(sizeof(struct Node));
node->Num = i;
node->Next = NULL;
curr->Next = node;
curr = curr->Next;
}
curr->Next = head;
Link last = curr;
curr = head;
// operate
for (int i=1;i<n;i++){
for (int j=1;j<3;j++){
last = curr;
curr = curr->Next;
}
printf("出圈：%d\n",curr->Num);
Link Temp = curr;
last->Next = curr->Next;
free(Temp);
curr = last->Next;
}
printf("胜利者：%d\n",curr->Num);
return(0);
}
3 递归法，m=3
使用递归求解问题需要找到三个关键点，从而找到对应的递推公式。
- 该问题的解可以分解为几个子问题？
- 确保问题本身和子问题，除了数据规模不同，求解思路完全一样
- 确定递归终止条件
待着上述3个关键点，我们来看约瑟芬问题如何用递归求解。
我们从0开始做下标。
设f(n,m)表示n个人数m时问题的解，那么f(n-1,m)是n-1个人数m时问题的解。
显然我们知道不管m等于多少f(1) = 0。
假设f(n-1)的答案（胜利者的下标）已经求出，那么思考一下f(n-1)的胜利者的下标位置和f(n)胜利者的下标位置之间有什么关系呢？
image.png
图中最上方的两行黄色，列出了n从1~11时，对应的f(n,3)结果。
- 下方的图拿n=11个人编号
0~10，第一次数的时候从0数到2数了3个数,那么2就被踢出去了，标记为红色，之后永远不可能数到2了，下方设置为灰色。剩下10个人。 - 剩下10个数编号
0~9，编号为3的人是这10个人队伍的头，从0开始重新报数。仍然是报到的人被踢出去，剩下9个人0~8。
所以我们可以看到f(n)和f(n-1)下标之间有相差为m的关系。
f(k) = ( f(k-1)+3 )%k ,效率O(n)
理解这个递推式的核心在于
- 关注胜利者的下标位置是怎么变的。
- 每次去掉一个人以后，下一个报数的人从0开始编号。
如果下一个报数的人，不从0开始编号会怎么样呢？如下图看到，n=11的时候，f(11,3)是从0开始报数的，到编号2的时候被踢出去，剩下10人。
10人中，编号为3的人是这10个人队伍的头，但是我们给他编号9。他仍然是第一个报数，报了第三个数的人（编号1）将被踢出去。对于这10个人来说，是从最后一个编号开始报数的，这与题意不符合，所以它的值根本不能表示f(10,3)。
image.png
分析了这么多，我们发现：
- f(n,m) 可以分解成1个子问题f(n-1,m)
- f(n,m)的求解思路和f(n-1,m)一样，只是数据规模不同
- 递归终止条件为f(1)=0
- 递推公式为
f(n,m) = (f(n-1,m) + m)%n , f(1)=0
最后，题目要求下标从1开始，所以返回ans+1
#include <stdio.h>
int main(){
int n = 0,m=3;
scanf("%d", &n);
int ans = 0;
for (int i=1;i<=n;i++){
ans = (ans + m)%i;
}
printf("%d", ans+1);
return(0);
}
网友评论