經典算法題「喝汽水」：模擬遞歸與數學優化雙解法

經典算法題「喝汽水」：模擬遞歸與數學優化雙解法

題目：1 元買 1 瓶汽水，2 個空瓶換 1 瓶，給定 n 元，最多能喝幾瓶？

方法一：模擬遞歸（直觀易懂）

#include <stdio.h>
int main() {
    int money, empty = 0, total = 0;
    scanf("%d", &money);
    total = money;
    empty = money;
    while (empty >= 2) {
        int exchange = empty / 2;
        total += exchange;
        empty = empty % 2 + exchange;
    }
    printf("%d\n", total);
    return 0;
}

邏輯：每輪用空瓶換新瓶，喝完產生新空瓶，循環直到不足 2 個。

方法二：數學公式優化（O(1) 時間）

#include <stdio.h>
int main() {
    int n; scanf("%d", &n);
    printf("%d\n", 2 * n - 1);
    return 0;
}

推導：假設老板借 1 空瓶，則 n 元可喝 2n 瓶（每瓶產生 1 空瓶，共 2n 空瓶還給老板）。實際不借瓶，最後剩 1 空瓶無法換，故 2n - 1。

測試對比

輸入 20 → 輸出 39。兩種方法結果一致，公式法極致高效。

舉一反三

• 3 空瓶換 1 瓶？公式變為 (3*n - 1) / 2（整數除法）。
• k 空瓶換 1 瓶？通用公式 (k*n - 1) / (k - 1)。