アルゴリズムと計算量 (2): ユークリッドの互除法，フィボナッチ数の計算

今日の内容

最大公約数を求めるアルゴリズムとその評価
フィボナッチ数を求めるプログラム
ベキ乗計算のアルゴリズム

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

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

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

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

[演習 7.1]

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

[問題 7.1]

ユークリッドの互除法で最大公約数を求める関数 gcd(x,y) を基に，計算の繰り返し数を返す関数 gcd_bench(x,y) を作りなさい．

授業時間中にプログラムをメイル提出する事．
- メイルの件名: CS入門問題7.1
- メイルの本文に氏名と学籍番号を必ず書くこと．
- プログラムは添付ファイルにすること．
- 東工大のアカウント以外から出されたメイルは受取らない．

[演習 7.2]

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

[問題 7.2]

どのような場合に，ユークリッドの互除法でも計算回数が増えるのか考察しなさい．

授業時間中に考察の結果をメイルで提出する事．
- メイルの件名: CS入門問題7.2
- メイルの本文に氏名と学籍番号を必ず書くこと．
- 本文に考察の結果を書くこと．
- 東工大のアカウント以外から出されたメイルは受取らない．

フィボナッチ数の計算

[問題 7.3]

フィボナッチ数の計算を行う計算量 O(n) の関数 fib(n) を作りなさい．

関数 fib(n) のプログラムをメイルで授業時間内に提出すること．
もし授業時間中に提出出来なかった時には，11月16日(金)の20時までに提出する事．
- メイルの件名: CS入門問題7.3
- メイルの本文に氏名と学籍番号を必ず書くこと．
- プログラムは添付ファイルにすること．
- 東工大のアカウント以外から出されたメイルは受取らない．

ベキ乗計算のアルゴリズム

[問題 7.4]

n の k 乗を n を単純に k 回掛けて計算する関数 power1(n, k) を作りなさい．
n の k 乗をもっと効率よく計算する関数 power2(n, k) を作りなさい．
関数 power1(n, k) を基に，計算の繰り返し回数を返す関数 power1_bench(n, k) を作りなさい．
関数 power2(n, k) を基に，計算の繰り返し回数を返す関数 power2_bench(n ,k) を作りなさい．

次の授業までに問題を解いておいて下さい．

[問題 7.5]

関数 power1_bench(n, k)，関数 power2_bench(n ,k) で実験を行い，
関数 power1(n, k) のアルゴリズムの計算量，関数 power2(n, k) のアルゴリズムの計算量を予想しなさい．

次の授業までに問題を解いておいて下さい．

来週の予告

来週の授業は教室で行います．
教科書を使いますので忘れずに持って来て下さい．
来週の授業の主な内容 (予定)
- 最大公約数を求めるアルゴリズム (まとめ)
- フィボナッチ数の計算のアルゴリズム
- ベキ乗計算のアルゴリズムと計算量
- ソートのアルゴリズム

2012年11月3日作成
2012年11月9日改訂
伊知地宏
Copyright (C) Hiroshi Ichiji, 2012. All rights reserved.