2021-06-21：販賣機只支援硬幣支付，且收退都只支援10 ，50，100三種面額。一次購買只能出一瓶可樂，且投錢和找零都遵循優先使用大錢的原則，需要購買的可樂數量是m， 其中手頭擁有的10、50、100的數量分別為a、b、c，可樂的價格是x（x是10的倍數） 。請計算出需要投入硬幣次數？
福大大 答案2021-06-21：
時間緊，思路見程式碼。
程式碼用golang編寫。程式碼如下：
package mainimport “fmt”func main（） { m ：= 10 a ：= 20 b ：= 30 c ：= 40 x ：= 50 ret ：= putTimes（m， a， b， c， x） fmt。Println（ret）}// 正式的方法// 要買的可樂數量，m// 100元有a張// 50元有b張// 10元有c張// 可樂單價xfunc putTimes（m int， a int， b int， c int， x int） int { // 0 1 2 qian ：= ［］int{100， 50， 10} zhang ：= ［］int{c， b， a} // 總共需要多少次投幣 puts ：= 0 // 之前面值的錢還剩下多少總錢數 preQianRest ：= 0 // 之前面值的錢還剩下多少總張數 preQianZhang ：= 0 for i ：= 0； i < 3 && m ！= 0； i++ { // 要用之前剩下的錢、當前面值的錢，共同買第一瓶可樂 // 之前的面值剩下多少錢，是preQianRest // 之前的面值剩下多少張，是preQianZhang // 之所以之前的面值會剩下來，一定是剩下的錢，一直攢不出一瓶可樂的單價 // 當前的面值付出一些錢+之前剩下的錢，此時有可能湊出一瓶可樂來 // 那麼當前面值參與搞定第一瓶可樂，需要掏出多少張呢？就是curQianFirstBuyZhang curQianFirstBuyZhang ：= （x - preQianRest + qian［i］ - 1） / qian［i］ if zhang［i］ >= curQianFirstBuyZhang { // 如果之前的錢和當前面值的錢，能湊出第一瓶可樂 // 湊出來了一瓶可樂也可能存在找錢的情況， giveRest（qian， zhang， i+1， （preQianRest+qian［i］*curQianFirstBuyZhang）-x， 1） puts += curQianFirstBuyZhang + preQianZhang zhang［i］ -= curQianFirstBuyZhang m—— } else { // 如果之前的錢和當前面值的錢，不能湊出第一瓶可樂 preQianRest += qian［i］ * zhang［i］ preQianZhang += zhang［i］ continue } // 湊出第一瓶可樂之後，當前的面值有可能能繼續買更多的可樂 // 以下過程就是後續的可樂怎麼用當前面值的錢來買 // 用當前面值的錢，買一瓶可樂需要幾張 curQianBuyOneColaZhang ：= （x + qian［i］ - 1） / qian［i］ // 用當前面值的錢，一共可以搞定幾瓶可樂 curQianBuyColas ：= getMin（zhang［i］/curQianBuyOneColaZhang， m） // 用當前面值的錢，每搞定一瓶可樂，收貨機會吐出多少零錢 oneTimeRest ：= qian［i］*curQianBuyOneColaZhang - x // 每次買一瓶可樂，吐出的找零總錢數是oneTimeRest // 一共買的可樂數是curQianBuyColas，所以把零錢去提升後面幾種面值的硬幣數， // 就是giveRest的含義 giveRest（qian， zhang， i+1， oneTimeRest， curQianBuyColas） // 當前面值去搞定可樂這件事，一共投了幾次幣 puts += curQianBuyOneColaZhang * curQianBuyColas // 還剩下多少瓶可樂需要去搞定，繼續用後面的面值搞定去吧 m -= curQianBuyColas // 當前面值可能剩下若干張，要參與到後續買可樂的過程中去， // 所以要更新preQianRest和preQianZhang zhang［i］ -= curQianBuyOneColaZhang * curQianBuyColas preQianRest = qian［i］ * zhang［i］ preQianZhang = zhang［i］ } if m == 0 { return puts } else { return -1 }}func giveRest（qian ［］int， zhang ［］int， i int， oneTimeRest int， times int） { for ； i < 3； i++ { zhang［i］ += （oneTimeRest / qian［i］） * times oneTimeRest %= qian［i］ }}func getMin（a int， b int） int { if a < b { return a } else { return b }}
執行結果如下：
***
［左神java程式碼］（https：//github。com/algorithmzuo/coding-for-great-offer/blob/main/src/class02/Code02_Cola。java）
