Rubyでアルゴリズムやらデータ構造やらのお勉強（recursive - 2）

gcd.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

# 再帰の例に「良い例」としてあったやつなんだけど、Rubyでそのままは無理やり感が強かった。
# 再帰でシンプルに書ける理由として、ここでは「配列の長さに基づくループとか出来無いよね」という前提にたってるみたいなので・・・

$VERBOSE = true

# 何も限定されなければ、たぶんRubyでこんな感じで書いてしまう。
# これだと不公平すぎる
def gcd(*numbers)
  numbers.min.downto(1).find{|try|
    numbers.all?{|n|n % try == 0}
  }
end

# しょうが無いので、Arrayの長さとか簡単に取れないしenumみたいなのないよと仮定して・・・

# まずは２つの数間で値を求めるものを作り
def ab_gcd(num_a, num_b)
  try = num_a

  while try > 1
    break if num_a % try == 0 && num_b % try == 0
    try -= 1
  end

  try
end

# 配列の長さに合わせて適宜再帰するものを用意。
# 確かに宣言的な記述だなーとは思う。
def deep_gcd(numbers, length_minus_1)
  if length_minus_1 == 1
    ab_gcd numbers[0], numbers[1]
  else
    ab_gcd numbers[length_minus_1], deep_gcd(numbers, length_minus_1 - 1)
  end
end


# Overview

p gcd(90, 150, 45) #=> 15

p ab_gcd(90, 150) #=> 30
p ab_gcd(90, 45) #=> 45
p ab_gcd(45, 150) #=> 15

p deep_gcd([90, 150, 45], 3 - 1) #=> 15