C語言經典遞歸題：猴子吃桃問題數學建模與代碼實現

C語言經典遞歸題：猴子吃桃問題數學建模與代碼實現

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

數學建模分析

設第 n 天早上剩 P_n 個桃子，則第 n-1 天早上剩：

P_{n-1} = 2 × (P_n + 1)

已知 P_10 = 1，逆推 9 步得 P_1。

遞歸實現

#include <stdio.h>

// 遞歸函數：從第 n 天倒推到第 1 天
int peach_count(int day, int current) {
    if (day == 1) return current;
    return peach_count(day - 1, 2 * (current + 1));
}

// 迭代版本（更高效）
int peach_count_iter(int days) {
    int peaches = 1;  // 第 10 天剩 1 個
    for (int i = days; i > 1; i--) {
        peaches = 2 * (peaches + 1);
    }
    return peaches;
}

int main() {
    int days = 10;
    printf("遞歸結果：%d\n", peach_count(days, 1));
    printf("迭代結果：%d\n", peach_count_iter(days));
    return 0;
}

通用化擴展

// 通用版：支持任意天數、任意剩餘數
int monkey_peach(int total_days, int final_remaining) {
    int peaches = final_remaining;
    for (int day = total_days; day > 1; day--) {
        peaches = 2 * (peaches + 1);
    }
    return peaches;
}

int main() {
    int n, remaining;
    printf("輸入天數：");
    scanf("%d", &n);
    printf("輸入第 %d 天剩餘桃數：", n);
    scanf("%d", &remaining);
    printf("第一天共摘 %d 個桃子\n", monkey_peach(n, remaining));
    return 0;
}

運行結果

輸入天數：10
輸入第 10 天剩餘桃數：1
第一天共摘 1534 個桃子

數學驗證

第 10 天：1
第 9 天：2×(1+1)=4
第 8 天：2×(4+1)=10
第 7 天：2×(10+1)=22
第 6 天：2×(22+1)=46
第 5 天：2×(46+1)=94
第 4 天：2×(94+1)=190
第 3 天：2×(190+1)=382
第 2 天：2×(382+1)=766
第 1 天：2×(766+1)=1534 ✓