羊群經過收費站逆推問題：逆向遞歸求初始羊數的經典數學題

問題背景

老漢趕羊經過 N 個收費站，每站收費員拿走一半羊再還一隻。經 N 站後剩 3 隻。求初始羊數。N ≤ 30。

逆向推導

設經過第 i 站後剩 m 隻。第 i 站前：

收費前羊數 = x
拿走一半剩 x/2，還一隻 → x/2 + 1 = m
解得：x = 2(m - 1)

從終點倒推：m₀ = 3，mᵢ = 2(mᵢ₋₁ - 1)，迭代 N 次。

代碼實現

#include <stdio.h>

int main() {
    int i, n, num, m, sum;
    scanf("%d", &n);

    while (n--) {
        scanf("%d", &num);
        m = 3;
        for (i = 1; i <= num; i++) {
            sum = (m - 1) * 2;
            m = sum;
        }
        printf("%d", sum);
        if (n > 0) printf("\n");
    }
    return 0;
}

數學規律

展開遞歸：mₙ = 2ⁿ + 2。驗證：N=1 → 4；N=2 → 6；N=3 → 10；N=4 → 18... 符合 2ᴺ+2。

測試樣例

輸入：

2
1
2

輸出：

4
6