2025年10月2日 星期四
解碼換水瓶問題:從直覺模擬到終極數學公式
***此篇文章由 Gemini AI 產生***
大家好!我是 Coding Partner。今天想跟大家分享一個很有趣的程式問題,它看似簡單,但深入挖掘後會發現許多值得玩味的細節。
**問題情境:** 你手上有 `numBottles` 瓶水。喝完後,空瓶可以拿去回收兌換新的水。第一次兌換需要 `numExchange` 個空瓶,但之後每一次兌換所需的空瓶數都會加一。請問,你最多總共能喝到幾瓶水?
這是一個典型的演算法問題,考驗我們如何將一個生活化的情境轉化為高效的程式碼。接下來,我會帶大家走過三種層次的思考:從最直觀的模擬,到有瑕疵的數學解,最終抵達一個堪稱完美的終極公式。
### 第一層:直觀模擬法 — 穩紮穩打的起點
面對這個問題,第一個閃過腦中的念頭,就是「照著規則跑一次看看」。這就是模擬法。它的邏輯非常直接:
1. 先把手上的水全部喝掉,得到第一批空瓶。
2. 用一個迴圈不斷檢查:手上的空瓶夠不夠換下一次?
3. 如果夠,就進行兌換,更新手上空瓶數、總共喝掉的瓶數,以及下一次兌換的成本。
4. 如果不夠,就結束。
這個思路清晰、不易出錯,寫成程式碼也相當直觀。
#### 模擬法程式碼
```cpp
#include
class Solution {
public:
/**
* @brief Calculates the maximum bottles drunk via simulation.
* @param numBottles The initial number of full water bottles.
* @param numExchange The number of empty bottles required for the first exchange.
* @return The total number of bottles drunk.
*/
int maxBottlesDrunk_Simulation(int numBottles, int numExchange) {
// Start by drinking all the initial bottles.
int drunkBottles = numBottles;
// These now become your initial empty bottles.
int emptyBottles = numBottles;
// Loop as long as we can afford the next exchange.
while (emptyBottles >= numExchange) {
// Perform one exchange.
emptyBottles -= numExchange;
// The cost for the next exchange increases.
numExchange++;
// We got a new bottle, so we drink it immediately.
drunkBottles++;
// That newly drunk bottle becomes an empty one.
emptyBottles++;
}
return drunkBottles;
}
};
```
這個解法很棒,是個可靠的起點。但身為工程師,我們總會忍不住問:「有沒有可能更快?有沒有辦法不用迴圈,一次就算出來?」
### 第二層:數學公式解 — 抓住核心關係
要擺脫迴圈,我們得換個思路。與其模擬「過程」,不如直接計算「結果」。我們可以問:**最多能進行幾次兌換?**
假設總共能兌換 `k` 次,那麼答案就是 `初始瓶數 + k`。為了算出 `k`,我們必須滿足一個核心條件:
$$\text{Total Bottle Supply} \ge \text{Total Exchange Cost}$$
* **空瓶總供給量 (Total Bottle Supply)**:來自於 `numBottles` 個初始空瓶,以及 `k` 次兌換後新產生的 `k` 個空瓶,總共是 `numBottles + k`。
* **總兌換成本 (Total Exchange Cost)**:這是一個等差級數 `numExchange + (numExchange + 1) + ...` 的總和,其結果為 `(k/2) * (2 * numExchange + k - 1)`。
將這兩者放入不等式中:
$$\text{numBottles} + k \ge \frac{k \times (2 \cdot \text{numExchange} + k - 1)}{2}$$
經過整理與化簡,我們可以將這個不等式改寫成一個標準的二次不等式形式:
$$k^2 + (2 \cdot \text{numExchange} - 3)k - 2 \cdot \text{numBottles} \le 0$$
瞧!我們成功地把問題轉化成了一個國中數學的二次不等式問題。只要解出滿足這個不等式的最大整數 `k`,問題就解決了。
#### 有瑕疵的數學解程式碼
根據這個推導,我們可以寫出第一版的數學解程式碼。它使用 `floor()` 函數來取得 `k` 的最大整數解,並加上 `if` 判斷來處理無法首次兌換的邊界情況。
```cpp
#include
#include
class Solution {
public:
/**
* @brief A flawed mathematical attempt to solve the problem.
* It uses floor() and requires an explicit edge case check.
*/
int maxBottlesDrunk_FlawedMath(int numBottles, int numExchange) {
// This guard clause is necessary because the formula below doesn't handle this case.
if (numBottles < numExchange) {
return numBottles;
}
double n = static_cast(numBottles);
double x = static_cast(numExchange);
double b = 2 * x - 3;
double c = -2 * n;
double t_root = (-b + std::sqrt(b * b - 4 * 1 * c)) / 2.0;
// The intuitive approach: the number of exchanges is the floor of the root.
int exchanges = static_cast(std::floor(t_root));
return numBottles + exchanges;
}
};
```
這個版本看起來不錯,但魔鬼,就藏在我們沒看到的細節裡。
### 第三層:完美的細節 — `floor` vs `ceil - 1`
上面這個 `floor(t)` 的版本,在兩個關鍵的邊界情況會出錯:
1. **需要 `if` 補丁**:它無法自行處理 `numBottles < numExchange` 的情況,必須依賴一個額外的 `if` 判斷,顯得不夠優雅。
2. **資源正好用盡**:當 `t` 算出來剛好是整數時(例如 `t=2.0`),代表所有資源正好「完美用盡」。但在現實的逐步兌換中,這意味著你在支付最後一次費用時,會正好差一個空瓶(因為那個空瓶要等換完喝掉才有),導致兌換失敗。`floor(t)` 會多算出一次兌換。
這時,高手們發現了一個極其精妙的數學技巧來取代 `floor(t)`,那就是 `ceil(t) - 1`(對 `t` 無條件進位後再減一)。
我們來看看這個技巧有多神奇:
* **當 `t` 不是整數 (如 2.7)**:`ceil(2.7) - 1 = 3 - 1 = 2`。這和 `floor(2.7) = 2` 結果一樣。
* **當 `t` 是整數 (如 2.0)**:`ceil(2.0) - 1 = 2 - 1 = 1`。它自動修正了「差一」的錯誤!
* **當初始無法兌換 (t \< 1,如 0.8)**:`ceil(0.8) - 1 = 1 - 1 = 0`。它竟然連 `if` 判斷都省了,直接得到正確的兌換次數 0!
這個 `ceil(t) - 1` 的表達式,用純數學的優雅,完美地處理了所有邊界情況。
### 終極程式碼 — 結合效率與優雅
現在,我們可以寫出最終版的程式碼了。它不僅是 O(1) 的時間複雜度,而且極其簡潔、強固。
```cpp
#include
#include // Required for std::sqrt and std::ceil
class Solution {
public:
/**
* @brief Calculates the maximum number of bottles that can be drunk using a direct mathematical formula.
* @param numBottles The initial number of full water bottles.
* @param numExchange The number of empty bottles required for the first exchange.
* @return int The total number of bottles drunk.
*/
int maxBottlesDrunk(int numBottles, int numExchange) {
// Use long long for coefficients to prevent overflow if inputs are large.
long long b = 2LL * numExchange - 3;
long long c = -2LL * numBottles;
// Discriminant from the quadratic formula: b^2 - 4ac
double delta = (double)b * b - 4.0 * c;
// The positive root of the quadratic equation
double t_root = (-b + sqrt(delta)) / 2.0;
// The number of exchanges 'k' is calculated using ceil(t) - 1.
// This trick correctly handles both non-integer cases, perfect integer cases,
// and the edge case where no exchanges are possible, all in one formula.
int exchanges = (int)ceil(t_root) - 1;
return numBottles + exchanges;
}
};
```
### 總結
從一個簡單的模擬迴圈,到一個帶有瑕疵的數學公式,再到一個能處理所有邊界情況的完美表達式,這個解題過程本身就是一趟精彩的旅程。它告訴我們,一個「能動」的程式和一個「完美」的程式之間,往往是對細節和邊界情況的極致追求。
希望這次的分享能對你有所啟發!祝大家寫程式愉快!
GitHub 上面清不掉的未讀訊息
看到 GitHub notification 消不掉的問題 才知道發生什麼事情。
本來是 GitHub 官方應該要處理的問題,我又不想安裝 GitHub CLI 來用,不如來順便練習一下 Vibe coding 好了,於是弄了一個 https://ghno.sylee.org/,程式碼放在 https://github.com/fourdollars/go-playground/tree/main/github-notifications-oauth 上面。
伺服器只是處理 OAuth 重導,跟透過使用者傳來的 Token 呼叫 GitHub API 而已,利用 https://github.com/settings/applications/new 註冊一個 OAuth app 來用,清空的感覺真好。
2025年10月1日 星期三
從模擬到數學魔法:解開「換酒問題」的奧秘
***此篇文章由 Gemini AI 產生***
在程式設計的世界裡,我們時常遇到一些看似簡單,卻蘊含巧妙解法的問題。「換酒喝」或稱「空瓶換水」(Water Bottles) 就是一個典型的例子。這個問題不僅考驗我們的邏輯,更展示了如何從直觀的模擬思維,昇華到高效的數學公式解法。
今天,就讓我們一起踏上這段有趣的解題之旅,從頭到尾徹底理解這兩種方法的思路與奧妙。
### 問題描述
> 給你 `numBottles` 瓶酒。你可以用 `numExchange` 個空酒瓶來換一瓶新酒。
>
> 請問你總共可以喝到多少瓶酒?
**舉個例子:**
假設你有 9 瓶酒 (`numBottles = 9`),並且 3 個空瓶可以換一瓶新酒 (`numExchange = 3`)。
- 你先喝掉 9 瓶,得到 9 個空瓶。
- 用 9 個空瓶換 3 瓶新酒。
- 喝掉 3 瓶新酒,得到 3 個空瓶。
- 再用 3 個空瓶換 1 瓶新酒。
- 喝掉 1 瓶新酒,剩下 1 個空瓶。
- 剩下 1 個空瓶,不夠再換了。
- 總共喝了 9 + 3 + 1 = 13 瓶。
### 解法一:直觀模擬法 (The Simulation Approach)
身為工程師,我們的第一直覺通常是「模擬」。電腦最擅長的就是重複執行指令,所以我們可以寫一個迴圈,完整模擬整個換酒的過程。
#### 思考邏輯
1. **起始**:我們先把手上所有的酒 (`numBottles`) 喝完,這就是我們能喝到的基礎數量。
2. **迴圈**:只要手上的空瓶數量還足夠兌換 (`>= numExchange`),我們就持續進行交換。
3. **交換**:在每一輪迴圈中,我們計算能換到多少瓶新酒 (`gain`),並將其加入總數。
4. **更新**:手上的空瓶數會更新為「上一輪換完剩下的」加上「剛換來喝完的」。
5. **結束**:當空瓶數不再足以兌換時,迴圈結束,我們得到最終答案。
#### 程式碼實現 (C++)
這個邏輯直接、清晰,就像我們腦中沙盤推演一樣。
```cpp
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
// Start with the initial number of bottles.
int sum = numBottles;
int emptyBottles = numBottles;
// Keep exchanging as long as we have enough empty bottles.
while (emptyBottles >= numExchange) {
// Calculate how many new bottles we can get.
int gain = emptyBottles / numExchange;
// Add the newly obtained bottles to the total sum.
sum += gain;
// Update the count of empty bottles:
// The remainder from the exchange + the new bottles we just drank.
emptyBottles = (emptyBottles % numExchange) + gain;
}
return sum;
}
};
```
這個解法完全正確,而且很容易理解。但身為追求極致的開發者,我們不禁會想:有沒有更快、更優雅的方法?
### 解法二:數學公式法 (The Mathematical Approach)
讓我們換個角度,尋找問題背後的數學規律。這個問題的核心可以轉化為:**每多喝一瓶「換來的」酒,我們淨消耗了多少空瓶?**
#### 思考邏輯
- 你用 `numExchange` 個空瓶,換來 **1** 瓶新酒。
- 喝完這瓶新酒後,它又變成了 **1** 個空瓶回到你手上。
所以,你實際付出的代價是 `numExchange - 1` 個空瓶,就成功多喝了一瓶酒。
現在,問題變成了:
**你最初喝完 `numBottles` 瓶後得到的 `numBottles` 個空瓶,總共能讓你完成多少次「淨消耗 `numExchange - 1` 個空瓶」的交換?**
這裡有個小細節:你手上的空瓶不可能全部都「淨消耗」掉,因為最後總會剩下不夠交換的瓶子。一個巧妙的理解方式是:
> 想像你手上有 `numBottles` 個空瓶。你先拿出 1 個放在旁邊備用,剩下 `numBottles - 1` 個空瓶作為你的「週轉資本」。
>
> 每當你想換酒時,就從「週轉資本」裡拿出 `numExchange - 1` 個,再把你旁邊備用的那 1 個湊上去,正好是 `numExchange` 個。
>
> 換來新酒喝完,又得到 1 個空瓶,你再把它放到旁邊當作下一次的備用瓶。
這個過程可以一直持續下去,直到你的「週轉資本」耗盡為止。所以,你**額外**能喝到的酒瓶數,就等於:
`額外瓶數 = (週轉資本) / (每次交換的淨成本)`
`額外瓶數 = (numBottles - 1) / (numExchange - 1)`
*(這裡使用整數除法,會自動捨去餘數,正好對應了資本不足、無法再換的情況)*
最後,把初始喝的瓶數和額外喝的瓶數相加,就是總數。
#### 程式碼實現 (C++)
這個驚人的發現,讓我們可以將原本的迴圈濃縮成一行程式碼。
```cpp
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
// Edge case: If we can't even make one exchange initially.
// This check is optional as the formula works even without it.
if (numBottles < numExchange) {
return numBottles;
}
// Total = Initial bottles + additional bottles gained from exchanges.
return numBottles + (numBottles - 1) / (numExchange - 1);
}
};
```
### 結論
我們從一個直觀的模擬解法,透過轉換思考角度,最終得到了一個極其簡潔的數學公式。
| **特性** | **模擬解法** | **數學解法** |
| :--- | :--- | :--- |
| **直觀性** | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ |
| **效率** | O(log N) | O(1) |
| **程式碼簡潔度** | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| **核心思想** | 逐步模擬實際過程 | 分析資源的淨消耗 |
這趟解題之旅告訴我們,許多程式問題的背後都隱藏著數學規律。當我們能夠洞察其本質,就能寫出更高效、更優雅的程式碼。下次遇到類似問題時,不妨也試著跳出模擬的框架,尋找那把化繁為簡的數學鑰匙。
Happy Coding\!
訂閱:
文章 (Atom)