読者です 読者をやめる 読者になる 読者になる

牌語備忘録 -pygo

あくまでもメモです。なるべくオフィシャルの情報を参照してください。

牌語備忘録 -pygo

SICPの練習問題 1.11をPythonでやってみた

SICP Python

SICPの練習問題 1.11Pythonでやってみた
schemeの解答はこちら:http://oss.timedia.co.jp/index.cgi/kahua-web/show/SICP/Answer%20Book


Exercise 1.11. A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n>= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
(練習問題 1.11 関数f 次の式により定義する。もし n<3 なら f(n) = n、もし n>= 3 であれば f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)。再帰を用いて f の計算する手順を書け。反復も書け。)

# recursive
def f_rec(n):
    if n < 3:
        return n
    return f_rec(n - 1) + 2 * f_rec(n - 2) + 3 * (n - 3)
print f_rec(4) #11

# iterative
def f_iter(n):
    def iter(a,b,c,count):
        if count == 0:
            return c
        if count == 1:
            return b
        return iter((a + 2 * b + 3 * c), a, b, (count - 1))
    return iter(2,1,0,n)
print f_iter(4) #11