いつもの千代田区立図書館で。
最近は、来る日も来る日も再帰的プロセスと反復的プロセスについてです。何度も出てくるのでよほど重要なんでしょう。
今日はべき乗のお話。
普通にべき乗を求める手続き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でも書く。
コメント