Werden wir Helden für einen Tag

Home | About | Archive

麥樂雞問題 #2 Python ver.

Posted on Feb 24, 2011 by Chung-hong Chan

我想先答第二部份的問題,就是證明:

如果可以買到 n, n+1, n+2, n+3, n+4 及 n+5 件,那麼 n 以後的所有件數都一定買得到。

如果 n 件買到,那就一定買到 n+6 件,只是買多一盒六件的。
如果 n, n+1, n+2, .... n+5 都買到,那麼 n+6, n+1+6, n+2+6, ...., n+5+6 都買到。也即是 n 之後的數目全都是買到。

我想這樣說已經算是一個 proof 了吧。
好了,回到 Programming 的問題。
要解答這個問題,我覺得先要設立一個 function ,去決定 n 件麥樂雞是否可買。
由於那個 MIT course 是用 Python 的,故此也寫 Python 了。 ((當然,寫 R 也可以。最近學了一個字眼,好 Pro 的,叫 Turing Complete 。))

def buyable(numN):
    '''Brute force approach to findout the solution, return a tuple of boxes of 6, 9 and 20 pcs required'''
    if numN < 1:
        return (None, None, None)
    else: rangefound = int((numN/6)+1)
    for num6 in range(0,rangefound):
        for num9 in range(0,rangefound):
            for num20 in range(0,rangefound):
                totalN = 6*num6 + 9*num9 + 20*num20
                if totalN == numN:
                    return (num6,num9,num20)
    return (None, None, None)

這個 function 做的,很簡單的,就是 search 不同組合的 6 件、 9 件及 20 件盒數麥樂雞之總件數,是否等於我們輸入的 numN 。如果有的 match 的話,就 return 一個記錄了三款麥樂雞盒數的 tuple ((tuple 和 list 的分別,是 tuple 內的 item 不可變,而 list 可變。)) 。如果沒有 match ,就回報 (None, None, None) ,代表該個 numN 的件數買不到。

function 內有個叫 rangefound 的數目,那是限制三款麥樂雞的最高盒數。由於魯鈍,想這個數都想了很久。為何是等於 (numN/6) + 1 ,那是因為 numN/6 * 6 一定大於或等於 numN 。至於為何要加一,那是因為 Python 的 range() 的 Stop 值是不包括 Stop 值本身。即是 range(0,10) ,是回報 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 。

function 測試:

>>> buyable(10)
(None, None, None)
>>> buyable(6)
(1, 0, 0)
>>> buyable(20)
(0, 0, 1)
>>> buyable(29)
(0, 1, 1)

好似 Work 。有了這個 function ,之後的就很易,只是輸入由 0 開始至 200 的數值到這個 buyable() 的 function ,要是發現不能買,就 capture 它便可。

unbuyable = []
for trialnumN in range(0,200):
    num6,num9,num20 = buyable(trialnumN)
    if num6 == None or num9 == None or num20 == None:
        unbuyable.append(trialnumN)
    else: pass

那個 unbuyable 的 list 記載了以下數字:

[0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43]


Powered by Jekyll and profdr theme