アルゴリズムと計算量 (1): 最大公約数を求めるアルゴリズム

今日の内容

最大公約数を求めるアルゴリズムとその評価

最大公約数を求めるアルゴリズムとその評価

最大公約数を求める素朴なアルゴリズムのプログラム

# gcd_s.rb
# 最大公約数を単純な方法で求めるプログラム

def gcd_s(x,y)                    # 関数 gcd_s の定義
  if x > y                        # x, y のうち大きくない方を n に設定
    n = y
  else
    n = x
  end
  k = 1
  while k <= n                    # k が n 以下なら繰り返す:
    if x % k == 0 && y % k == 0   # x と y が k で割り切れるか判定
      ans = k                     # k が x と y の公約数のときに ans に設定
    end
    k = k + 1                     # k の値を 1 増やす
  end
  ans                             # 答えとして ans の値を返す
end

[演習 5.1]

素朴なアルゴリズムで2つの数 x, y の最大公約数を求める関数 gcd_s(x,y) をファイル gcd_s.rb に作り，irb にロードして実行し，最大公約数の計算が行われる事を確認しなさい．

計算の途中結果を表示

プログラムを書いたときに，思うとおりの計算結果にならないときも多い．
そのようなときには，計算の途中結果を表示させると間違いに気が付くときがある．
計算の途中結果を表示させるには print という関数を使う．
以下はユークリッドの互除法の計算を逐次表示するプログラムである．

# gcd_s_p.rb
# 最大公約数を単純な方法で求めるプログラム

def gcd_s_p(x,y)                  # 関数 gcd_s_p の定義
  if x > y                        # x, y のうち大きくない方を n に設定
    n = y
  else
    n = x
  end
  k = 1
  while k <= n                    # k が n 以下なら繰り返す:
    if x % k == 0 && y % k == 0   # x と y が k で割り切れるか判定
      ans = k                     # k が x と y の公約数のときに ans に設定
      print "k = ", k, "\n"       # 公約数を表示
      # k = という文字列の後に k の値を表示．
      # \n という文字列は改行を行う．
    end
    k = k + 1                     # k の値を 1 増やす
  end
  ans                             # 答えとして ans の値を返す
end

gcd_s_p.rb を実行すると次のようになる．

irb(main):002:0> load("./gcd_s_p.rb")
=> true
irb(main):003:0> gcd_s_p(100, 50)
k = 1
k = 2
k = 5
k = 10
k = 25
k = 50
=> 50

[演習 5.2]

関数 gcd_s_p(x,y) をファイル gcd_s_p.rb に作り，irb にロードして実行し，最大公約数の計算の途中結果が表示される事を確認しなさい．

ユークリッドの互除法のプログラム

ユークリッドの互除法については，先週の授業で説明したし，教科書66ページにも説明がある．

[問題 5.1]

ユークリッドの互除法で2つの数 x, y の最大公約数を求める関数 gcd(x,y) を作りなさい．

素朴なアルゴリズムとユークリッドの互除法の評価

以下の関数は，最大公約数を求める際に何回比較を行うのかを評価している．

def gcd_s_bench(x,y)
  times = 0
  if x > y
    n = y
  else
    n = x
  end
  for k in 1..n
    if x % k == 0 && y % k == 0
      ans = k
    end
    times = times + 1
  end
  times
end

[演習 5.3]

関数 gcd_s_bench(x,y) をファイル gcd_s_bench.rb に作り，irb にロードして実行し，最大公約数の計算での繰り返し回数が返される事を確認しなさい．

[問題 5.2]

関数 gcd(x,y) を基に，計算の繰り返し数を返す関数 gcd_bench(x,y) を作りなさい．

[演習 5.4]

数 x, y を変えながら，関数 gcd_s_bench(x,y), gcd_bench(x,y) の値を比較し，ユークリッドの互除法の方が計算が少ないことを確認しなさい．
x = 144, y = 89 のときに gcd_bench(x,y) を求めなさい．
上記で，x, y を少しずつ変えて計算回数が急に変わることを確認しなさい．

計算量の違いを実感

[演習 5.5]

同じ整数 n に対して，n log₂n と n² の値を表示するプログラムを作り，いくつかの整数値に対して実行して，比較しなさい．
log₂n は Math.log2(n) で計算出来る．

[問題 5.3]

n の k 乗を n を単純に k 回掛けて計算する関数 power1(n, k) を作りなさい．
n の k 乗をもっと効率よく計算する関数 power2(n, k) を作りなさい．([ヒント] 2⁴ = (2²)²)

来週の予告

来週の授業は教室で行います．
教科書を使いますので忘れずに持って来て下さい．
来週の授業の主な内容 (予定)
- ユークリッドの互除法の計算量
- ソートのアルゴリズム