牌語備忘録 -pygo

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

牌語備忘録 -pygo

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

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


Exercise 1.16. Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (b ^ {n/2}) ^ 2 = (b ^ 2) ^ {n/2}, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a b^n is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

《練習問題 1.16 発展させた反復の累乗計算プロセスの手順を作る二乗を継続的に使い、fast-expような対数のステップ数を使う。(ヒント: (b ^ {n/2}) ^ 2 = (b ^ 2) ^ {n/2}、動作を続ける、指数nと基底b、さらに状態が可変するa、そして提示する状態から変化しないa b^n の状態変換を定義する。a の初期値は 1 とすると処理の終了時にaが渡される。概して、提示する状態から変化しない不変量(invariant quantity)を定義する技術は、反復アルゴリズムを考える効果的な方法)》

#Exercise 1.16.
def even(n):
    if n % 2 == 0:
        return True
def fast_expt_iter(b, n):
    return e_iter(b, n, 1)
def e_iter(b, counter, product):
    if counter == 0:
        return product
    elif even(counter):
        return e_iter(b * b, counter / 2, product)
    else:
        return e_iter(b, counter - 1, b * product)
print fast_expt_iter(2,4)
print fast_expt_iter(2,5)

#Exercise 1.16.(counter == n, product == a)
def e_iter(b, n, a):
    if n == 0:
        return a
    elif even(n):
        return e_iter(b * b, n / 2, a)
    else:
        return e_iter(b, n - 1, b * a)