iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 9
2
Software Development

活用python- 路遙知碼力,日久練成精系列 第 9

Day9- 中秋特輯: 月餅店攬客花招,「名偵探柯馬」出馬,亂丟骰子馬欸通?

月到中秋分外明,來寫文章精神好

雖說今日中秋佳節,花好月圓,
小馬不停蹄的繼續創作,
因應撰文這天正巧是中秋節來寫個應景的程式算法問題,
什麼「切片」、「列表生成式」屠龍的事先擺一邊吧。
(文末有彩蛋,歡迎閱到最後)

先快速公佈一下昨日課後練習解答:

def judge(scores):
    return sorted(scores)[1:-1]

恭喜邦友ccutmis答對哦。

大家好,我是心原一馬,內心原來一心喜歡打程式碼。
請看問題:

買月餅問題

「小馬月餅店」開張囉,
為了吸引客人,
老闆想出了以下小遊戲與客人互動,
以決定月餅的價錢。
假設客人想買裝有n個月餅的禮盒一盒(n至少為2),
客人必須將n個月餅分成兩堆,
每堆至少一個月餅,
並將兩堆月餅的個數相乘,
得到第一個乘數。
之後再將第一堆和第二堆分別分成兩堆,
又會得到兩個乘數。
依此繼續下去,每堆僅剩一個月餅為止。
最後n個月餅的售價就是這些乘數的和。

舉例來說,假設n=5,
底下是小明的一種分堆方法:
https://ithelp.ithome.com.tw/upload/images/20190911/20117114FCdhfpsn3y.png

(圖示意思為先把5個月餅分成2、3兩堆,再各自把月餅繼續分堆)
因此,小明買五個月餅的錢數就是6 + 1 + 2 + 1 = 10塊錢。
請你實作一支程式,
計算小明需要買n個月餅最省錢的分堆分法的金額為何?

你看完題目後的反應是這樣嗎:
https://ithelp.ithome.com.tw/upload/images/20190911/20117114hBeTOIsfg1.png

初看這問題的時候可能真的會有點嚇到,
把n個月餅分到每堆1個的狀況實在太多了,
於是你嘗試腦內google 各式各樣的關鍵字來嘗試解這一題:
窮舉?樹結構?排列組合?遞迴函數?DP?

別急,本系列文的門檻並不用先會資料結構及太深的數學,
你若腦中閃過這些關鍵字可能是你把問題想複雜了。

在此小馬提供一種思路:
既然不知道怎麼分月餅最好,
那先隨便亂分試試看好了
先行介紹新工具教大家使用囉。

產生隨機數 - random模組

要產生隨機數,首先要在你的python程式裡加入這行:

import random

底下介紹常用的random函數

函數 說明
random.randrange(start, stop[, step]) 隨機回傳一個 range(start, stop, step) 之中的數值
random.randint(a, b) 隨機回傳一個整數 N (a <= N <= b)
random.random() 隨機回傳一個浮點數 f (0 <= f <= 1)
random.uniform(a, b) 隨機回傳一個浮點數 f (a <= f <= b)
random.choice(seq) 隨機回傳seq裡的元素
random.shuffle(seq) 隨機洗亂seq裡的順序

這類random模組類的函數很特別,
一般來說,我們使用函數都是只要參數相同,那麼回傳的結果就是固定的,
例如Day4- Python內建函數是你的好夥伴這篇所提到的max(), min(), len(),sorted(),sum(),abs(), pow() 函數全屬於這類。
試想你今天想計算pow(2,3)的值好了,也就是2的3次方,
那麼這個值你不管計算多少次,答案永遠是8

但是這類隨機函數你每次調用的答案並不會每次都相同,
例如產生5個介於1到2之間的浮點數:

for i in range(5):
    print(random.uniform(1,2))

在小馬的電腦上,印出了這樣的結果,
1.7157798843466416
1.0091935990562648
1.2721025440645635
1.7863341497311933
1.7895073195027238
(相信我,在你的電腦上執行的結果一定跟小馬不同)

你可能說這類隨機函數可以用在哪裡?
它的用途可廣了,
許多遊戲元素都帶有隨機性,
例如: 骰子、撲克牌、猜拳啦

你可以運用random模組幫你模擬丟骰子的狀況,
也可以拿來模擬洗牌,
這邊暫不贅述。

回到原問題,我們也可以用random模組模擬隨意將月餅分堆的狀況,
雖然這方法看起來很蠢,
但說不定能幫助我們找到規律,
進而發現更漂亮的解法。

模擬隨機分月餅的過程

首先我們先定義 divMoonCakes這樣一個函式,
參數n表示有n個月餅,如下:

import random

def divMoonCakes(n):
    mooncakes = [n]

其中,我們在函數內定義變數mooncakes = [n]
收集所有大於一個的月餅堆,
設定初始值只有一堆n個月餅。

想要把月餅分堆的邏輯我們可以這樣寫:

while mooncakes裡還有月餅:
    隨意取出一堆月餅
    將它分成更小的兩堆
    把大於1個月餅的月餅堆放進列表mooncakes

把它寫成程式碼變成這樣:

import random

def divMoonCakes(n):
    mooncakes = [n]
    while mooncakes:
        m = random.choice(mooncakes)
        mooncakes.remove(m)
        div = random.randint(1,m-1)
        if div!=1:
            mooncakes.append(div)
        if m-div!=1:
            mooncakes.append(m-div)

為了清楚看到分月餅的過程,我們加幾個print()函數印出資訊:

def divMoonCakes(n):
    mooncakes = [n]
    while mooncakes:
        m = random.choice(mooncakes)
        mooncakes.remove(m)
        print("取出"+str(m)+"個月餅")
        div = random.randint(1,m-1)
        print(f"把{m}個月餅分成{div}和{m-div}兩堆")
        if div!=1:
            mooncakes.append(div)
        if m-div!=1:
            mooncakes.append(m-div)
        print("目前待分月餅堆: ", mooncakes)

(哦,對了,你可能沒看過在字串前加f的語法,
f"把{m}個月餅分成{div}和{m-div}兩堆"這句,
這是在python3.6版的新特性,
可以很方便的在字串內放入變數)

我們實際執行程式試試吧:

>>> divMoonCakes(5)
取出5個月餅
把5個月餅分成2和3兩堆
目前待分月餅堆:  [2, 3]
取出2個月餅
把2個月餅分成1和1兩堆
目前待分月餅堆:  [3]
取出3個月餅
把3個月餅分成1和2兩堆
目前待分月餅堆:  [2]
取出2個月餅
把2個月餅分成1和1兩堆
目前待分月餅堆:  []

可以看到目前已經可以印出月餅分堆的過程了
(由於用了隨機函數,每次分堆的過程會不一樣)

添加計算月餅金額的功能

計得原題目是要計算買n個月餅「最省錢」的方法。
我們增加一個變數money
用來統計月餅的總價,
並在每次分月餅的時候增加money的值。
程式更改如下:

def divMoonCakes(n):
    mooncakes = [n]
    money = 0
    print(f"月餅小計 {money} 元")
    while mooncakes:
        m = random.choice(mooncakes)
        mooncakes.remove(m)
        print("取出"+str(m)+"個月餅")
        div = random.randint(1,m-1)
        print(f"把{m}個月餅分成{div}和{m-div}兩堆,總共增加{div*(m-div)}元")
        money += div*(m-div)
        print(f"目前月餅小計 {money} 元")
        if div!=1:
            mooncakes.append(div)
        if m-div!=1:
            mooncakes.append(m-div)
        print("目前待分月餅堆: ", mooncakes)
    return money

這可能是目前路遙知碼力,日久練成精第一支超過十行的python程式,
但邏輯應該不算太難,
讓大家突破看看「螢幕十行」學讀長一點的程式囉,
如果你第一個程式是學其它語言,
這點行碼數其實應該還算小case。

再試著執行一次程式試試吧:

>>> divMoonCakes(5)
月餅小計 0 元
取出5個月餅
把5個月餅分成3和2兩堆,總共增加6元
目前月餅小計 6 元
目前待分月餅堆:  [3, 2]
取出2個月餅
把2個月餅分成1和1兩堆,總共增加1元
目前月餅小計 7 元
目前待分月餅堆:  [3]
取出3個月餅
把3個月餅分成1和2兩堆,總共增加2元
目前月餅小計 9 元
目前待分月餅堆:  [2]
取出2個月餅
把2個月餅分成1和1兩堆,總共增加1元
目前月餅小計 10 元
目前待分月餅堆:  []

好的,目前已經可以算出月餅總價了。
目前得到五個月餅是10元
我們再執行一次程式看看:

>>> divMoonCakes(5)
月餅小計 0 元
取出5個月餅
把5個月餅分成4和1兩堆,總共增加4元
目前月餅小計 4 元
目前待分月餅堆:  [4]
取出4個月餅
把4個月餅分成2和2兩堆,總共增加4元
目前月餅小計 8 元
目前待分月餅堆:  [2, 2]
取出2個月餅
把2個月餅分成1和1兩堆,總共增加1元
目前月餅小計 9 元
目前待分月餅堆:  [2]
取出2個月餅
把2個月餅分成1和1兩堆,總共增加1元
目前月餅小計 10 元
目前待分月餅堆:  []

這次分堆方式確實不一樣了,
結果五個月餅還是10元。
事實上不論你執行幾次,算出來的結果一定都是10元。
是巧合嗎?

會不會是5這個數字太小,
分堆方式不夠多,所以才會這樣呢?

我們換成10個月餅試試,
為了避免把過程印出來太占版面,
小馬先把函數內印出的資訊註解掉,
並用for迴圈執行10次看看。

for i in range(10):
    print(f"10個月餅總計{divMoonCakes(10)}元")

結果十次都是
10個月餅總計45元

雖說十個月餅的分堆分法有這種多種,
但是不論怎麼分竟都得到相同結果,
似乎很難想像這是巧合。
其實我們可以合理猜測:
當n固定時,買n個月餅的價格也是固定的,
只是目前不知原因。

好吧,現在改變參數n
再執行一次觀察看看規律吧,

for n in range(11):
    print(f"{n}個月餅總計{divMoonCakes(n)}元")

得到這樣的結果:

2個月餅總計1元
3個月餅總計3元
4個月餅總計6元
5個月餅總計10元
6個月餅總計15元
7個月餅總計21元
8個月餅總計28元
9個月餅總計36元
10個月餅總計45元

疑疑?規律呼之欲出了呢。
數列[1,3,6,10,15,...],
數列兩數之間的差距為[2, 3, 4, 5,...]
讓我想到起之前Day5畫過的階梯圖形:

*
**
***
****
*****

哦,等等,原來是這麼回事啊,
我已經揭開所有的謎底了。(「名偵探柯馬」上身。)

月餅問題超直覺圖解

底下開始上演小馬劇場:
https://ithelp.ithome.com.tw/upload/images/20190912/20117114epK2n0K7sa.png
柯馬: 月餅店老闆,聽說你今年月餅銷量特別好,有什麼秘訣嗎?
老闆: 是啊,大概今年有小遊戲與客人互動的關係吧
柯馬: 其實我已經看出你的手法了,首先,你故弄玄虛的訂一個遊戲,讓客人期待說可以透過什麼策略買到更便宜的月餅,但打從一開始,你就打算一盒月餅的價錢都是固定的吧?
老闆(緊張~): 你…你有什麼證據嗎?
柯馬: 我已經調查過貴店面的帳目了,那些全都如出一轍的數字,又是怎麼回事呢?
老闆(鬆一口氣): (好險,秘密應該沒被發現)當然是這些客人默契好。
柯馬: 哦?看來只好拿出鐵證了,你自己看下圖吧,這邊以n=7為例

https://ithelp.ithome.com.tw/upload/images/20190912/20117114sQi0EAA56J.png

柯馬: 排在月餅左下角的硬幣總和,就是月餅的價錢總和
老闆(狡辯中…): 啍,你想說你隨手畫的三角形,就能解掉我的遊戲嗎?你如何證明分月餅的順序都是不影響的?
柯馬: 要說為什麼的話…

https://ithelp.ithome.com.tw/upload/images/20190912/201171141aLguLFDpX.png
柯馬: 當你任意將月餅分堆時,其實就是拿藍十字線將月餅劃分成左上、右下更小的三角形堆,而左下角矩形的硬幣,根據規則,通通計在月餅總價中。而,遊戲又會持續進行分堆到一堆一個月餅,也就是左下角的硬幣最後都會算在月餅價格中。還有甚麼想說的嗎?
老闆: 哈,沒想到竟被看穿的如此徹底了嗎?
柯馬: 另外這隻程式可以計算出n個月餅的總價。

def priceOfMooncakes(n):
    return sum(range(1,n))

老闆: 哈哈哈,服了服了。確實有幾個客人不服氣,連續玩了好幾次,想找出最佳策略買月餅,沒想到怎麼玩結果都一樣,但又參不透其中道理,只好摸摸鼻子離開。
柯馬: 遊戲的樂趣…在於無窮無盡的可能性,你的遊戲從一開始走向固定結局,不剝奪了遊戲的樂趣嗎?
老闆: 哈哈,下次還請「名偵探柯馬」幫忙設計更好玩的遊戲囉。

全劇終

結語

今天沒有給讀者的課後練習,
主要想說因應中秋節,
鐵人賽也寫點特別的東西,
希望讀者還喜歡。
最後寫首小詩送給大家:

參與鐵人賽「中」,
「秋」季挑戰自我,
若能「快」馬加鞭,
必能「樂」在其中。

祝各位邦友中秋快樂


上一篇
Day8- 第一屠龍刀- range函數與列表切片的融會貫通
下一篇
Day10- 幾個程式經典問題,一亮出第一屠龍刀,彷彿開著坦克車攻打原始人,太逆天啦 (談切片語法的應用)
系列文
活用python- 路遙知碼力,日久練成精30

尚未有邦友留言

立即登入留言