PTA例題精析-約瑟夫問題 Josephus Problem

0 問題描述

【人數(shù)為n，步長為m】有n個(gè)人匿沛，編號為1~n逃呼，從第一個(gè)人開始報(bào)數(shù)者娱，從1開始報(bào)苏揣，報(bào)到m的人會(huì)死掉，然后從第m+1個(gè)人開始框沟，重復(fù)以上過程增炭。問最后一個(gè)人的編號是隙姿？

猴子選大王

【人數(shù)為n，步長為3】一群猴子要選新猴王哎甲。新猴王的選擇方法是：讓N只候選猴子圍成一圈饲嗽，從某位置起順序編號為1~N號。從第1號開始報(bào)數(shù)吞加，每輪從1報(bào)到3尽狠，凡報(bào)到3的猴子即退出圈子，接著又從緊鄰的下一只猴子開始同樣的報(bào)數(shù)践图。如此不斷循環(huán)，最后剩下的一只猴子就選為猴王沉馆。請問是原來第幾號猴子當(dāng)選猴王码党？正整數(shù)N（≤1000）

1 數(shù)組模擬，m=3

這里使用數(shù)組暴力模擬的問題在于斥黑，已經(jīng)被淘汰的猴子仍然會(huì)被循環(huán)到

#include <stdio.h>
int a[1001];// 1表示淘汰 
int main(){
    int n = 0,s=0,count=0;
    int i = 0; // 數(shù)組下標(biāo) 
    scanf("%d", &n);
    while(s != n-1){ // 淘汰猴子的數(shù)量達(dá)到n-1時(shí)退出
        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

鏈表方法很好理解兽狭，首尾相連成環(huán)，n個(gè)人中會(huì)淘汰n-1個(gè)人，所以外層循環(huán)是n-1箕慧，鏈表使用curr = curr->Next 2次服球，那么颠焦，就找到了數(shù)3的人有咨，把它從鏈表中刪除，這次外層循環(huán)就走完了蒸健，剩下n-2個(gè)人。

這里使用了單向鏈表婉商，用一個(gè)last指向了出圈者的上一個(gè)人似忧，以便于對出圈者進(jìn)行鏈表刪除操作。也可以考慮使用雙向鏈表丈秩。時(shí)間復(fù)雜度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

使用遞歸求解問題需要找到三個(gè)關(guān)鍵點(diǎn)，從而找到對應(yīng)的遞推公式蘑秽。

該問題的解可以分解為幾個(gè)子問題饺著？
確保問題本身和子問題，除了數(shù)據(jù)規(guī)模不同肠牲，求解思路完全一樣
確定遞歸終止條件

待著上述3個(gè)關(guān)鍵點(diǎn)幼衰，我們來看約瑟芬問題如何用遞歸求解。

我們從0開始做下標(biāo)缀雳。
設(shè)f(n,m)表示n個(gè)人數(shù)m時(shí)問題的解渡嚣，那么f(n-1,m)是n-1個(gè)人數(shù)m時(shí)問題的解。
顯然我們知道不管m等于多少f(1) = 0肥印。
假設(shè)f(n-1)的答案（勝利者的下標(biāo)）已經(jīng)求出识椰，那么思考一下f(n-1)的勝利者的下標(biāo)位置和f(n)勝利者的下標(biāo)位置之間有什么關(guān)系呢？

image.png

圖中最上方的兩行黃色深碱，列出了n從1~11時(shí)腹鹉，對應(yīng)的f(n,3)結(jié)果。

下方的圖拿n=11個(gè)人編號0~10敷硅，第一次數(shù)的時(shí)候從0數(shù)到2數(shù)了3個(gè)數(shù),那么2就被踢出去了功咒，標(biāo)記為紅色，之后永遠(yuǎn)不可能數(shù)到2了绞蹦，下方設(shè)置為灰色航瞭。剩下10個(gè)人。
剩下10個(gè)數(shù)編號0~9坦辟，編號為3的人是這10個(gè)人隊(duì)伍的頭刊侯，從0開始重新報(bào)數(shù)。仍然是報(bào)到的人被踢出去锉走，剩下9個(gè)人0~8滨彻。

所以我們可以看到f(n)和f(n-1)下標(biāo)之間有相差為m的關(guān)系藕届。
f(k) = ( f(k-1)+3 )%k ,效率O(n)
理解這個(gè)遞推式的核心在于

關(guān)注勝利者的下標(biāo)位置是怎么變的。
每次去掉一個(gè)人以后亭饵，下一個(gè)報(bào)數(shù)的人從0開始編號休偶。

如果下一個(gè)報(bào)數(shù)的人，不從0開始編號會(huì)怎么樣呢辜羊？如下圖看到踏兜，n=11的時(shí)候，f(11,3)是從0開始報(bào)數(shù)的八秃，到編號2的時(shí)候被踢出去碱妆，剩下10人。
10人中昔驱，編號為3的人是這10個(gè)人隊(duì)伍的頭疹尾，但是我們給他編號9。他仍然是第一個(gè)報(bào)數(shù)骤肛，報(bào)了第三個(gè)數(shù)的人（編號1）將被踢出去纳本。對于這10個(gè)人來說，是從最后一個(gè)編號開始報(bào)數(shù)的腋颠，這與題意不符合繁成，所以它的值根本不能表示f(10,3)。

image.png

分析了這么多淑玫，我們發(fā)現(xiàn)：

f(n,m) 可以分解成1個(gè)子問題f(n-1,m)
f(n,m)的求解思路和f(n-1,m)一樣朴艰，只是數(shù)據(jù)規(guī)模不同
遞歸終止條件為f(1)=0
遞推公式為 f(n,m) = (f(n-1,m) + m)%n , f(1)=0

最后，題目要求下標(biāo)從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);
}