いつもの千代田区立図書館で。
最近は、来る日も来る日も再帰的プロセスと反復的プロセスについてです。何度も出てくるのでよほど重要なんでしょう。
今日はべき乗のお話。
普通にべき乗を求める手続き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減らしていったけど、ここでは「不定量」という技(よく使われるらしい)を使って解いていた。
なるほど。おもしろい!
著:エイブルソン,ハロルド, 著:サスマン,ジュリー, 著:サスマン,ジェラルド・ジェイ, 原著:Abelson,Harold, 原著:Sussman,Julie, 原著:Sussman,Gerald Jay, 翻訳:英一, 和田
¥10,602 (2025/02/05 08:23時点 | Amazon調べ)

コメント