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

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

今日はべき乗のお話。

普通にべき乗を求める手続き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, 翻訳:英一, 和田
¥5,060 (2023/12/16 10:08時点 | Amazon調べ)

コメント

コメントする

目次