解碼換水瓶問題：從直覺模擬到終極數學公式

***此篇文章由 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; } }; ``` ### 總結 從一個簡單的模擬迴圈，到一個帶有瑕疵的數學公式，再到一個能處理所有邊界情況的完美表達式，這個解題過程本身就是一趟精彩的旅程。它告訴我們，一個「能動」的程式和一個「完美」的程式之間，往往是對細節和邊界情況的極致追求。 希望這次的分享能對你有所啟發！祝大家寫程式愉快！