C語言練習實例21：猴子吃桃問題（逆向遞推）

經典問題：猴子 10 天每天吃剩餘一半多 1 個，第 10 天早上剩 1 個，求第一天摘了多少。

逆向公式

設第 k 天早上剩 x_k，則第 k-1 天早上剩 x_{k-1} = (x_k + 1) * 2。從第 10 天 x_10 = 1 逆推 9 步得 x_1。

源代碼

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

int main() {
    int day, x1 = 0, x2;
    day = 9;
    x2 = 1;
    while (day > 0) {
        x1 = (x2 + 1) * 2;
        x2 = x1;
        day--;
    }
    printf("總數為 %d\n", x1);
    return 0;
}

運行結果

總數為 1534

驗證

正向模擬 1534 → 766 → 382 → 190 → 94 → 46 → 22 → 10 → 4 → 1，共 10 天，符合。