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);
}