從模擬到數學魔法：解開「換酒問題」的奧秘

***此篇文章由 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\!