SICP読書会 #7

いつもの千代田区立図書館で。

最近は、来る日も来る日も再帰的プロセスと反復的プロセスについてです。何度も出てくるのでよほど重要なんでしょう。

今日はべき乗のお話。

普通にべき乗を求める手続きpowを再帰で書くと以下のような感じになって、O(n)ステップになるけど、

#! /usr/bin/env ruby
def pow(a, n)
if n == 0
return 1
else
a * pow(a, n - 1)
end
end
__END__

逐次平方を使って書くと以下のような感じになって、O(logn)ステップになりますという話。

#! /usr/local/env ruby
def square(n)
return n * n
end
def even?(n)
return (n % 2 == 0)
end
def pow(a, b, n)
if n == 0
a
elsif even?(n)
pow(a, square(b), n / 2)
else
pow(a * b, b, n - 1)
end
end
__END__

反復的プロセスで書くとき、階乗とかフィボナッチ数列のときはcounter減らしていったけど、ここでは「不定量」という技(よく使われるらしい)を使って解いていた。

なるほど。おもしろい!

# あとでちゃんと書く。Schemaでも書く。

気に入ったらシェアお願いします!

この記事を書いた人

こんにちは!カノといいます👓
インターネットやテクノロジー、ビジネスモデルや歴史(世界史・日本史)、美術などが好きです。メガネのせいか真面目っぽく見えるらしいですが、基本的には昔からいい加減な性格です。
このブログは昔からずっと個人的な日記みたいな感じで書いてきていて、基本的には個人的なログになりますが、興味のあるところだけ読んでいただけるとうれしいです。コメントやTwitterのフォローなどは大歓迎です。

コメント

コメントする

目次