C語言練習實例80：猴子分桃子問題（逆向思維求解）

經典「猴子分桃子」問題：5 只猴子依次將桃子分成 5 份，每次多 1 個扔掉並拿走 1 份，求最少初始桃子數。

逆向推導

• 設第 5 只猴子操作前有 x5 個桃子，操作後剩 x6 = 1（題目說第 10 天早上只剩 1 個，此處為第 5 只猴子後剩 1 個）。
• 逆推公式：x_k = (x_{k+1} + 1) * 5 / 4，要求每步結果為整數。
• 程序從 j=1 開始嘗試最終剩餘桃子數，逆推 5 步，若中間出現非整數則 j++ 重試。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>

int main() {
    int x, i = 0, j = 1;
    while (i < 5) {
        x = 4 * j;
        for (i = 0; i < 5; i++) {
            if (x % 4 != 0) break;
            x = (x / 4) * 5 + 1;
        }
        j++;
    }
    printf("%d\n", x);
    return 0;
}

運行結果

3121

驗證

3121 → 猴子1：(3121-1)/5=624 拿走 剩2496 → 猴子2：(2496-1)/5=499 拿走 剩1996 → 猴子3：(1996-1)/5=399 拿走 剩1596 → 猴子4：(1596-1)/5=319 拿走 剩1276 → 猴子5：(1276-1)/5=255 拿走 剩1020。每步均整除，符合條件。