圖/yapei
文/檸檬
大家是否注意過,每次到便利商店買東西,店員總是能超快速找零給你?就算拿一張1000元買個85元的飯糰,他們眨眼間就能算出該找915元。這是什麼神奇魔法嗎?今天,讓我們一起來揭開便利商店結帳系統背後的數學祕密!
貪婪演算 結帳有效
便利商店的結帳系統使用一種叫「貪婪演算法」的方法來計算找零。聽起來很厲害?其實原理很簡單,就是每次都先選最大面額的硬幣或紙鈔。
舉個例子,假設要找零915元。結帳系統會這樣計算:
先拿最大的:1張500元(還剩415元)。
再拿第二大的:4張100元(還剩15元)。
接著:1個10元硬幣(還剩5元)。
最後:1個5元硬幣。
這樣,915元就被分解成1張500元、4張100元、1個10元與1個5元,總共5張鈔票與2枚硬幣,這個方法可以確保使用最少數量的鈔票與硬幣。
不過。什麼是貪婪演算法?這個方法明聽起不大好聽,卻是一種在每一步都做出當前看起來最好選擇的問題解決方法。在找零的例子中,「最好的選擇」就是「最大面額的鈔票或硬幣」。
貪婪演算法的特點是:
簡單快速:每一步只考慮當前最佳解,不回頭。
局部最優:每一步的選擇在當時看來都是最好的。
不一定全域最優:雖然每一步都選最好的,但最後的結果不一定是整體最佳解。
貪婪演算法真正成為電腦科學中的重要概念,是在1970年代。當時,隨著電腦科技的發展,人們開始尋找解決複雜問題的有效方法。貪婪演算法因其簡單快速的特性,很快就成為了解決某些問題的首選方法。
而貪婪演算法之所以在找零問題中特別有效,是因為台灣的貨幣系統設計得很巧妙。我們的貨幣面額是:1000元、500元、100元、50元、10元、5元、1元。注意到了嗎?每個面額都是前一個的因數或倍數。這意味著,用更大面額的組合,一定可以取代小面額,而且不會用到更多的鈔票或硬幣。這種特性使得貪婪演算法在找零問題中,不只是局部最佳,而且可能是唯一最佳解,也就是使用最少數量的鈔票與硬幣。
多種領域 廣泛延伸
除了找零問題,貪婪演算法在很多其他領域也有廣泛應用:
霍夫曼編碼:用於資料壓縮,像是在製作ZIP檔案時。
Dijkstra最短路徑演算法:用於GPS導航系統中尋找最短路徑。
貪婪著色演算法:用於解決圖形著色問題,比如排課表。
活動選擇問題:用於安排時間表,讓盡可能多的活動不衝突。
下次當我們在便利商店結帳時,不妨多觀察一下店員是怎麼運作的。你可能會發現,結帳系統正在實踐我們今天學到的貪婪演算法呢!記住,像貪婪演算法這樣的數學概念,不只是課本裡的理論,它在我們的日常生活中無處不在。從便利商店找零到高深的電腦科學,看似無關卻又緊密相連的概念,正在幫助我們解決各種實際問題呢!