C語言經典算法：猴子選大王（约瑟夫环問題）

問題描述

10 只猴子圍成圈，從 1 開始報數，報到 n 的退出，循環直到剩最後一只，輸出其編號。

數學建模（約瑟夫環）

設 f(n, m) 為 n 人、步長 m 時的獲勝位置（0-indexed），遞推公式：
f(1, m) = 0
f(i, m) = (f(i-1, m) + m) % i

C 語言實現（數組模擬）

#include 

int main() {
    int m, n = 10, step;
    printf("輸入步長 n: "); scanf("%d", &step);
    int monkeys[10] = {1,2,3,4,5,6,7,8,9,10};
    int count = n, idx = 0, num = 0;
    while (count > 1) {
        num++;
        if (monkeys[idx] != 0) { // 未退出
            if (num == step) {
                monkeys[idx] = 0; // 退出
                count--;
                num = 0;
            }
        }
        idx = (idx + 1) % n;
    }
    for (int i = 0; i < n; i++) if (monkeys[i] != 0) printf("大王編號: %d\n", monkeys[i]);
    return 0;
}

優化版（遞推公式 O(n)）

int josephus(int n, int m) {
    int res = 0;
    for (int i = 2; i <= n; i++) res = (res + m) % i;
    return res + 1; // 轉 1-indexed
}

教學意義

體驗循環鏈表/數組模擬、遞推關系、取模運算在環形結構中的應用。