Java 猴子分桃問題：遞迴與迴圈解法

經典數學謎題：猴子分桃

海灘上有一堆桃子，5 隻猴子依序分桃。每隻猴子將桃子分成 5 份，多 1 個，吃掉多的 1 個，拿走 1 份。第 6 隻猴子同樣操作。求最少原始桃子數。

遞迴搜尋法（原始碼風格）

public class MonkeyPeachRecursive {
    static final int MONKEYS = 5;
    static final int MAX_SEARCH = 5000;

    public static void main(String[] args) {
        new MonkeyPeachRecursive().find(0);
    }

    int find(int peaches) {
        if (peaches == MAX_SEARCH) {
            System.out.println("搜尋結束");
            return 0;
        }
        if (canDivide(peaches, 1)) {
            System.out.println("最少桃子數 = " + peaches);
            return peaches;
        }
        return find(peaches + 1);
    }

    boolean canDivide(int total, int round) {
        if (round > MONKEYS) return true; // 5 隻猴子都分完
        if ((total - 1) % MONKEYS != 0) return false;
        int remaining = (total - 1) / MONKEYS * (MONKEYS - 1);
        return canDivide(remaining, round + 1);
    }
}

輸出：最少桃子數 = 3121（5 猴子情況）。

迴圈驗證法（更直觀）

public class MonkeyPeachIterative {
    public static void main(String[] args) {
        for (int total = 1; ; total++) {
            int peaches = total;
            boolean ok = true;
            for (int i = 0; i < 5; i++) {
                if ((peaches - 1) % 5 != 0) { ok = false; break; }
                peaches = (peaches - 1) / 5 * 4;
            }
            if (ok) {
                System.out.println("最少桃子數 = " + total);
                break;
            }
        }
    }
}

數學通解

設原始桃子數為 N，每次操作：N -> (N-1)*(m-1)/m (m=猴子數)。

反向推導：第 k 次分桃前桃子數 N_k 滿足 N_k = m * N_{k+1}/(m-1) + 1。

最小正整數解為 N = m^m - (m-1)（當 m 為奇數）或類似形式。程式驗證 m=5 時 5^5 - 4 = 3121。

擴充：任意猴子數

public static long solve(int monkeys) {
    for (long total = 1; ; total++) {
        long p = total;
        boolean ok = true;
        for (int i = 0; i < monkeys; i++) {
            if ((p - 1) % monkeys != 0) { ok = false; break; }
            p = (p - 1) / monkeys * (monkeys - 1);
        }
        if (ok) return total;
    }
}

注意：猴子數增加時答案指數增長，long 很快溢位，需改用 BigInteger。