經典算法題：猴子吃桃問題的數學建模與 C 語言實現

問題描述

猴子第一天摘若干桃子，吃掉一半再多吃一個；第二天吃剩下的一半又多吃一個；……第 10 天早上只剩 1 個。求第一天摘了多少個？

逆向推導數學模型

設第 i 天早上剩 x_i 個，則 x_{i-1} = 2*(x_i + 1)。從第 10 天 x_10 = 1 反推 9 步。

x_10 = 1
x_9  = 2*(1+1) = 4
x_8  = 2*(4+1) = 10
...
x_1  = 1534

C 語言實現

#include <stdio.h>

int main(void) {
    int peaches = 1;  // 第 10 天早上
    for (int day = 9; day >= 1; --day) {
        peaches = 2 * (peaches + 1);
    }
    printf("第一天共摘了 %d 個桃子\n", peaches);
    return 0;
}

通用化擴展

int monkey_peach(int days, int final_left) {
    int n = final_left;
    for (int i = days - 1; i >= 1; --i)
        n = 2 * (n + 1);
    return n;
}

// 測試
printf("%d\n", monkey_peach(10, 1));   // 1534
printf("%d\n", monkey_peach(5, 2));    // 62

遞歸版本

int monkey_peach_rec(int day, int total_days, int left) {
    if (day == total_days) return left;
    return 2 * (monkey_peach_rec(day + 1, total_days, left) + 1);
}