找零高手 —— 便利商店

文/檸檬  |2024.10.18
567觀看次
字級
圖/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導航系統中尋找最短路徑。

貪婪著色演算法:用於解決圖形著色問題,比如排課表。

活動選擇問題:用於安排時間表,讓盡可能多的活動不衝突。

下次當我們在便利商店結帳時,不妨多觀察一下店員是怎麼運作的。你可能會發現,結帳系統正在實踐我們今天學到的貪婪演算法呢!記住,像貪婪演算法這樣的數學概念,不只是課本裡的理論,它在我們的日常生活中無處不在。從便利商店找零到高深的電腦科學,看似無關卻又緊密相連的概念,正在幫助我們解決各種實際問題呢!

熱門新聞
訂閱電子報
台北市 天氣預報   台灣一週天氣預報

《人間福報》是一份多元化的報紙,不單只有報導佛教新聞,乃以推動祥和社會、淨化人心為職志,以關懷人類福祉、追求世界和平為宗旨,堅持新聞的準度與速度、廣度與深度,關懷弱勢族群與公益;強調內容溫馨、健康、益智、環保,不八卦、不加料、不阿諛,希冀藉由優質的內涵,體貼大眾身心靈的需要、關懷地球永續經營、延續宇宙無窮慧命,是一份承擔社會責任的報紙。自許成為「社會的一道光明」的《人間福報》任重而道遠,在秉持創辦人星雲大師「傳播人間善因善緣」的理念之際,更將堅持為社會注入清流,讓福報的發行為人間帶來祥和歡喜,具體實現「人間有福報,福報滿人間」的目標。
人間福報社股份有限公司 統編:70470026

 
聯絡我們 隱私權條款

Copyright © 2000-2024 人間福報 www.merit-times.com.tw
All Rights Reserved.