試題的 Python 解法

by thinker

關鍵字:

昨天的 linkname:[CMClass: 微軟徵才試題] http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/226 ，今天做了點小修正，補正一些漏洞。接著將程式寫出來， implement 該推論方式。這個 implementation 使用了一個 iterator ，用來做排列、組合中的組合 (combination) ，以簡化程式的複雜度。

{{{#!python
def combine(data, n):
    sels = list(range(n))
    while True:
        yield tuple([data[i] for i in sels])
        try:
            i = [i for i in range(n) if sels[i] + n - i < len(data)][-1]
        except IndexError:
            break
        c = sels[i]
        for i in range(i, n):
            c = c + 1
            sels[i] = c
            pass
        pass
    pass

sdict = {}                                                                      
pdict = {}                                                                      
for x, y in combine(range(2, 50), 2):                                           
    sdict.setdefault(x + y, []).append((x, y))                                  
    pdict.setdefault(x * y, []).append((x, y))                                  
    pass

def E(x, y):
    $C$ = x * y
    return len(pdict[$C$]) >= 2

def F(x, y):
    D = x + y
    subset = [(a, b) for a, b in sdict[D] if E(a, b)]
    return len(subset) >= 2

def G(x, y):
    $C$ = x * y
    subset = [(a, b) for a, b in pdict[$C$] if F(a, b)]
    return (len(subset) == 1)

def H(x, y):
    D = x + y
    subset = [(a, b) for a, b in sdict[D] if G(a, b) and E(a, b)]
    return (len(subset) == 1)

def I():
    subset = [(a, b) for a, b in combine(range(2, 50), 2) if H(a, b) and G(a, b) and F(a, b) and E(a, b)]
    return subset

print I()
}}}

執行結果
{{{
bash-2.05b$$ python mspro.py
[(35, 42)]
bash-2.05b$$ 
}}}

最後更新時間: 2007-03-07 22:55:57 CST | 引用

查詢:

COMMENTS:

on 2007-03-08 23:24:57 CST

hoamon said ..

請問你所談的 dynamic programming 是作業研究/離散數學/演算法(不曉得你會是在那一種學科中看到，我是唸作業研究時看到的)的「動態規劃」，還是說的是 Python 的動態語言特性。因為 keywords 連結是動態規劃的wiki頁面，但我在程式中無法體會到「動態規劃」的原理。

on 2007-03-09 02:44:47 CST

Thinker said ..

to 阿蒙: 這是演算法會提到的內容..

on 2007-03-09 02:49:11 CST

Thinker said ..

to 阿蒙: 你應該看 http://heaven.branda.to/~thinker/GinGin_CGI.py/show_id_doc/228 這篇才有加 Dynamic Programming 的技巧。

on 2007-03-09 07:48:32 CST

hoamon said ..

Sorry! 我看錯了。