情報科学

基本情報

授業科目名: 情報科学
時間割コード: 20739
曜限: 木3
教室: E21教室
教員: 山口泰
HP1: http://lecture.ecc.u-tokyo.ac.jp/~yama/2012W-JOHOKAGAKU/index.html
HP2: http://lecture.ecc.u-tokyo.ac.jp/johzu/joho-kagaku/2012/

自宅の環境でRubyを使う

大学のPCだけでなく自宅のPCでもRubyを使えるようにしておくと、課題をこなすときなどに便利でしょう。
以下ではWindowsの場合を仮定して、Rubyの使用法を書いていきます。MacとかLinuxとか使ってる人は情強でしょうから、こんな説明要らないよね？

WindowsにRubyをインストールする簡単な方法として、以下の2つが挙げられると思います。

大学側で用意されたインストーラを使う
一般に用いられているインストーラを使う

1.のインストーラはこのページからダウンロード出来ます。インストール方法と使用法も非常に簡単ながら書いてあるので、参考にすると良いでしょう。zipの展開とか意味分からん、って場合はそれくらい自分で調べましょう。
なお、要求されているJRuby 1.6.7.2はこのページからダウンロードします。OSが32bitの場合は「jruby_windows_1_6_7_2.exe」、64bitの場合は「jruby_windows_x64_1_6_7_2.exe」を選びます。OSが32bitとか64bitとかなんじゃらほい、って場合も自分で調べてください。なお、PCにJavaがインストールされていない場合は、このページからインストールを行う必要があります。
大学側で用意されたインストーラを使う利点は、ECCS端末とほぼ同じ環境を再現出来ることです。特に、画像を表示する際に用いるisrb2を使う場合は、このインストーラを使用する必要があります。

2.の場合はいろいろなインストーラが存在しますが、Windows向けのRubyインストーラとしてはこのページのものがおすすめです。インストールする際は「Add Ruby executables to your PATH」にチェックを入れておくことを推奨します。なおバージョン選択についてですが、ECCSにインストールされているRubyのバージョンは1.8.7です。私はバージョン1.9.3を入れていますが、バージョンを合わせたい場合は参考にしてください。
一般に用いられているインストーラを使う利点は、自分の好きな実装を選択できることや、バージョンの更新に強いことです。Rubyを使う際は、普通にコマンドプロンプトを立ち上げて使用します。画像を表示するisrb2は使用出来ないので、それに関してだけは方法1.を併用したり、ECCS端末を使うなどの工夫が必要になります。

大学の授業で使うからというだけでなく、今後もRubyをそれなりに使っていきたいという場合は一般向けのインストーラを用いる方が柔軟に対応出来ると思います。逆に大学の授業以外ではRubyなんぞ使わん、という場合は大学側で用意されたインストーラを用いる方が無難でしょう。

トラブルシューティング

（1.の方法の場合）isrbではなく「ruby check.rb exXX.rb」やirbなどを使いたい

Macではターミナルを起動しますが、Windowsではコマンドプロンプトを立ち上げる必要があります。コマンドプロンプトを起動するにはスタートボタンを押して検索欄に「cmd.exe」と打つなどいくつか方法があります。
これでirbは普通に実行できるはずです。rubyを使用するにはrubyではなく「jruby」とする必要があります。

（1.の方法の場合）isrb.bat を起動するとエラーが出る

ログオフ（または再起動）しても上手く動かない場合は、isrb2のフォルダの配置に問題がある可能性があります。パスに空白やマルチバイト文字（ひらがなや漢字など）を含まない場所に移動してみてください（C:\isrb2\ など）。

自宅の環境で check.rb を走らせるとエラーが出る（または文字化けする）

日本語を含むプログラムはテキストの符号化形式に関する問題が起こりやすいです。check.rbはUTF-8（BOM無し）という符号化形式で保存されていますが、この符号化形式を上手く扱えていないのだと思われます。符号化形式を変えて保存し直したりしてみてください。

（1.の方法の場合）isrb2が load() などで読み込むディレクトリが分からない

isrb.batのあるフォルダにあるrubyというフォルダの中です。

↑ 目次に戻る

Emacsの使い方

執筆予定ということで。

↑ 目次に戻る

第1週 10/11

irbを電卓代わりに使う

irbでは加算、減算、乗算、除算・剰余、冪乗の計算が出来ます。記号はそれぞれ「+」「-」「*」「/」「%」「**」を用います。
演算子の優先順位は「冪乗＞乗算、除算・剰余＞加算、減算」となっており、通常の計算と同じになっています。優先順位が等しい場合は、これも通常の計算と同じく左から計算されます。
除算を行う際は、扱う数が整数であるか小数であるかに注意する必要があります。割る数と割られる数がともに整数である場合、x / y の計算結果は x = p * y + q（ただしp,qは整数、0≦q＜y）を満たすpとなります（qを得るには x % y です）。7 / 2 = 3、-7 / 2 = -4 のようになるので気をつけましょう。割る数と割られる数のいずれか片方でも小数ならば、結果も小数となります。小数として計算したい場合は 7.0 / 2.0 のように「.0」を忘れないようにしましょう。
また、小数の計算には誤差がつきものとなります。例えば 0.7 % 0.2 = 0.1 となるはずですが、実際に計算してみると 0.7 % 0.2 = 0.099999... のように表示されたりします。コンピュータは有限桁の数値しか扱えませんが、2進法では0.7といった数は無限小数となってしまい、正確に計算出来ないのです。こういった誤差に関しては、おいおい授業でも取り扱われると思います。なお、整数の計算では誤差は生じません。

その他、数学関数を使えるようにする「include(Math)」、変数への値の代入、関数の定義などをやりました。これらの解説をする予定はありません。

↑ 目次に戻る

第2週 10/18

時間があるときに適宜書き足します。

↑ 目次に戻る

第3週 10/25

この回はサボってしまったため授業内容が確かではないのですが、スライドを見る限り主に条件分岐を習ったということで良いのでしょうか。配列や画像の操作、繰り返しについては第4週の方で扱うことにします。

ここで、プログラムを分かりやすくするために、授業では扱われていませんが「return」と「elsif」という2つのキーワードを紹介したいと思います。

return

例えば、引数を2つ取り最大値を返すプログラムは次のように書けるのでした。

def max(x, y)
  if x > y
    x
  else
    y
  end
end

xがyよりも大きいならばxを返し、そうでなければyを返す関数です。このとき、xやyを「返す」ことを明示的に表したいとき、次のように書くことも出来ます。

def max(x, y)
  if x > y
    return x
  else
    return y
  end
end

xやyの前に「return」というキーワードが追加されています。このreturnは無くても良いのですが、関数が何を返しているかが個人的に分かりやすくなると思うので、今後のプログラム例では断りなくreturnを使うこととします。
プログラムがreturn文に到達するとその時点で関数は値を返し、それより後ろの部分は処理されないため、returnがあるのとないのとで完全に同じというわけではありません。しかし、以下でreturnを用いるのはあくまで関数が返す値を明示するためだけなので、returnがあってもなくても正常に動作するようにプログラムを書くよう注意していきたいと思います。そのため、不要だと思う場合はreturnを完全に省略してもらって構いません。

elsif

西暦 y 年が閏年かどうかを判定するプログラムを条件分岐で書いてみると、次のようになります。

def leap_year(y)
  if y % 400 == 0
    return true
  else
    if y % 100 == 0
      return false
    else
      if y % 4 == 0
        return true
      else
        return false
      end
    end
  end
end

なお「%」は剰余を計算する演算子でした。このように条件分岐を繰り返すと入れ子がどんどん深くなり、何回もendを書くハメになります。これを回避するため、「if」「else」の他に、Rubyには「elsif」というキーワードが用意されています。elsifはif節とelse節の間に何個でも挟むことが出来ます（厳密にはelse節は省略できます）。elsifを用いると、このプログラムは次のように書くことが出来ます。

def leap_year(y)
  if y % 400 == 0
    return true
  elsif y % 100 == 0
    return false
  elsif y % 4 == 0
    return true
  else
    return false
  end
end

インデントが整い、endの数も減ってプログラムが読みやすくなりました。以降、このelsifも断りなく使うこととします。

以下は余裕のある人だけ見てもらいたいのですが、「y % 400 == 0」といった条件式は場合分けをしなくてもtrueやfalseという値になっていることを利用すると、このプログラムは次のように簡単に書くことも出来ます。

def leap_year(y)
  return y % 400 == 0 || (y % 100 != 0 && y % 4 == 0)
end

どちらが分かりやすいかは人それぞれだと思いますが、参考にしてみてはどうでしょうか。

median.rbの解答例

median1(x, y, z) の解答例は次のようになります。

def median1(x, y, z)
  if x < y
    if y < z
      return y
    else
      if x < z
        return z
      else
        return x
      end
    end
  else
    if x < z
      return x
    else
      if y < z
        return z
      else
        return y
      end
    end
  end
end

「if x < y」の形しか使えないために、場合分けが煩雑になり非常に読みにくいプログラムになっています。こういったプログラムは処理の流れを分かりにくくし、バグを生む原因となりやすいです。課題なので仕方ありませんが、このようなプログラムを書くことは基本的にやめましょう。
代わりに「かつ（&&）」「または（||）」やelsifを用いて、median2(x, y, z) を書いてみます。

def median2(x, y, z)
  if (y <= x && x <= z) || (z <= x && x <= y)
    return x
  elsif (x <= y && y <= z) || (z <= y && y <= x)
    return y
  else
    return z
  end
end

特に制限が無ければ、このように簡潔で分かりやすいプログラムを書くことを心掛けましょう。
ところで、(y <= x && x <= z) の部分を y <= x <= z のように書くことは出来ません。y <= x <= z では、まず y <= x が評価されて true や false といった値になってしまい、true <= z のような評価できない式になってしまいます。面倒でも && で2つの条件をつなげるようにしてください。
さて median2() の条件分岐ですが、不等号にイコールがついていることに注意しましょう。median1() ではイコールはあってもなくても良いのですが、median2() ではイコールを取り除くことは出来ません。なぜ取り除けないかは、(x, y, z) = (0, 0, 1) の場合などを考えてみると分かるのではないでしょうか。（検査ファイルにこのようなケースは用意されていないのでイコールがなくても検査は通ってしまいますが、本来は駄目です）

↑ 目次に戻る

第4週 11/1

以下のプログラムでは、コメントとして解説を書くことがあります。「#」より後ろの部分はプログラムに影響しない部分ですので、プログラムを写す場合などは切り落としてもらっても構いません。

繰り返し

「for」というキーワードを用いることで、繰り返し処理をさせることが出来ます。以下のプログラムは、n以下の正の整数の和を求める関数です。

def sum(n)
  s = 0
  for i in 1..n  # i に 1 ～ n が入る
    s += i       # s = s + i と同じ
  end
  return s
end

まあ繰り返しの例ということで、n * (n+1) / 2 を返せば良いじゃんとかいう突っ込みは勘弁して下さい。

今回の例では閉区間 [1, n] を繰り返しましたが、しばしば半開区間 [0, n) を繰り返したいことがあります。その場合には

for i in 0..(n-1)

と書けば良いのですが、点を3つにして

for i in 0...n  # .. が ... になっていることに注意

としても同じように動作します。便利なのでこれも以下断りなく使用します。

配列

配列とは、複数の変数をひとまとめにして扱えるようにしたものだと言っておくことにします。次のように書くことで、要素数がn個の配列を作ることが出来ます。

ary = Array.new(n)  # これで変数 ary は要素数 n の配列になる

配列の個々の値にアクセスするには a[1] のように書きます。なお要素数がn個の配列の場合、有効なインデックス（ [ ] 内の数字）は 0 ～ n-1 なので注意してください（本当は -n ～ -1 も有効なのですが、恐らく使わないので覚える必要はありません）。
配列を作った直後は、各要素は「nil」という値になっています。nilは値が未定義の場合に使われるもので、このままでは計算などが出来ません。配列を作ったら、forループを回して全ての値に0を代入するなどして初期化しておきましょう。

授業でも注意がありましたが、配列を代入することは避けるのが無難です。配列を代入すると以下のようなことが起こり、予期しない不具合に繋がる可能性があります。

a = [1, 2]  # a は要素数 2 の配列
b = a       # b に a を代入すると...
b[0] = 3    # ここで a[0] も 3 になってしまう！

配列を複製したい場合は、面倒でもforループを回して個々に値を代入しましょう。

a = [1, 2]               # a は要素数 2 の配列
b = Array.new(a.length)  # a と要素数の等しい配列を作成（a.length は a の要素数を表す）
for i in 0...a.length
  b[i] = a[i]            # 個々に値を代入
end
b[0] = 3                 # a[0] は 1 のまま

画像の表現

モノクロ画像は2次元配列、カラー画像は3次元配列で表現することが出来ます。2次元配列とは配列の配列とでも言えるもので、配列の各要素が配列になっているような構造を指します。
カラー画像は各画素ごとにRGB（赤・緑・青）の3つの情報を必要とするので、2次元配列の各要素が配列になり、3次元配列となります。このようになるとforループを3重に回さなくてはいけないことが多くなり、処理が複雑になってきます。

配列の前後の値の平均を求める

今回の課題の1つに画像の周囲の点の平均を求める関数 image_average(img, x, y) を作れというものがありますが、最初から2次元を考えるのではなく、1次元の配列の前後の平均を求める関数 array_average(a, x) から考えていくことにしましょう。
ここで前後の点というのは、データの範囲内の点を指すようです。例えば a = [1, 2, 3] のとき、1番目（0からカウントすることに注意）の前後の平均は (1 + 2 + 3) / 3 = 2.0 ですが、0番目の前後の平均は (1 + 2) / 2 = 1.5 のようになります。このように、平均を求める場所が配列の端にある場合は処理が少し変わってくるので、上手に場合分けをしなければなりません。
以下のプログラムは授業スライドの最後の方にあるものを修正 + 若干書き換えたもので、コメントは私が書き足しています。

def array_average(a, x)                # 配列 a の x 番目の前後の平均を求める
  n = 0                                # 足し込んだ要素数を 0 にしておく
  s = 0.0                              # 合計を 0.0 にしておく
  for i in -1..1                       # i = -1, 0, 1 の場合を考える
    if 0 <= x + i && x + i < a.length  # x + i が a の範囲内ならば
      n += 1                           # n を 1 増やし
      s += a[x+i]                      # a の x + i 番目の要素を s に足し込む
    end
  end
  if n == 0                            # n が 0 の場合は 0 除算を避けるため別処理
    return 0.0
  else
    return s / n                       # 足し込んだ要素数で合計を割って平均する
  end
end

この関数を2次元に拡張することで image_average() も書けると思います。提出期限より前に課題の解答例をここに書くつもりはないので、各自で考えてください。

なお私なら array_average() はこう書く、というのを以下に記しておきます。余裕のある人は比較してみると面白いかもしれません。

def array_average(a, x)
  return 0.0 if x < 0 || a.length <= x  # x が範囲外の場合は 0 を返す。if節は後置できる（この場合endは不要）
  n = s = 0.0                           # 2つの変数を一気に宣言 + 初期化
  for i in (x-1)..(x+1)
    next if i < 0 || a.length <= i      # next で以下の処理を飛ばしてループの次の処理に移行できる
    n += 1
    s += a[i]
  end
  return s / n                          # x が範囲外の場合は除外しているので、場合分けが不要
end

2行目のreturnでは返り値を明示するにとどまらず、return文の性質を利用しています。
授業スライドの array_average() では a = [1, 2, 3] , x = -1 のとき1を返しますが、この定義では0を返します。0を返す方が自然だと思うのですが、どうでしょうか？

オリジナル画像の例

オリジナル画像の例として、教科書p.48の練習3.10（いろいろな図形）の (a) ～ (d) のプログラム例を以下に書いておきます。
引数のnは画像の幅と高さを表します。

include(Math)
 
def fig_a(n)
  img = make2d(n, n)
  for y in 0...n
    for x in 0...n
      if x <= y
        img[y][x] = 1.0 * y / n
      else
        img[y][x] = 1.0
      end
    end
  end
  return img
end
 
def fig_b(n)
  img = make2d(n, n)
  for y in 0...n
    for x in 0...n
      if (x + y) % 2 == 0
        img[y][x] = 1.0
      else
        img[y][x] = 0.0
      end
    end
  end
  return img
end
 
def fig_c(n)
  img = make2d(n, n)
  for y in 0...n
    for x in 0...n
      img[y][x] = 0.5 * (x + y) / n
    end
  end
  return img
end
 
def fig_d(n)
  img = make2d(n, n)
  for y in 0...n
    for x in 0...n
      if y < 0.5 * n * (1 + sin(4 * PI * x / n))
        img[y][x] = 1.0 * y / n
      else
        img[y][x] = 1.0
      end
    end
  end
  return img
end

課題4の解答例

original() についてはいくらでも好きなものが書けるので、特に解答例は提示しません。

mono.rb

def image_average(img, x, y)
  h = img.length
  w = img[0].length
  n = 0
  s = 0.0
  for i in -1..1
    if 0 <= y + i && y + i < h
      for j in -1..1
        if 0 <= x + j && x + j < w
          n = n + 1
          s = s + img[y+i][x+j]
        end
      end
    end
  end
  if n == 0
    return 0
  else
    return s / n
  end
end
 
def blur(img)
  h = img.length
  w = img[0].length
  blurred = make2d(h, w)
  for y in 0..h-1
    for x in 0..w-1
      blurred[y][x] = image_average(img, x, y)
    end
  end
  return blurred
end

color.rb

def image_average(img, x, y)
  h = img.length
  w = img[0].length
  n = 0
  s = [0.0, 0.0, 0.0]
  for i in -1..1
    if 0 <= y + i && y + i < h
      for j in -1..1
        if 0 <= x + j && x + j < w
          n = n + 1
          for k in 0..2
            s[k] = s[k] + img[y+i][x+j][k]
          end
        end
      end
    end
  end
  if n == 0
    return [0.0, 0.0, 0.0]
  else
    return [s[0]/n, s[1]/n, s[2]/n]
  end
end
 
# blur(img) は mono.rb と同じで大丈夫

余談：Array.new(n) は必要か？

配列を作るときは a = Array.new(n) とするんだと習いましたが、この Array.new() は教える必要が無いんじゃないかというお話です。授業とは関係無い、割と自己満足な内容になると思うので、興味のある人以外は読み飛ばすのが良いかと思います。

Rubyは非常に高機能なので、実はaは配列ですよという宣言さえしておけば、範囲外の値に代入しても自動的に配列のサイズを拡張してくれます。

a = []     # a は空の配列
a[2] = 42  # 自動的に a = [nil, nil, 42] になる

また、配列の末尾に要素を追加する「<<」という演算子を用いることも出来ます。

a = [2, 3]
a << 5      # a = [2, 3, 5] になる

つまり、こういった機能を利用すれば、Array.new() を使わなくとも make1d(n) は次のように書けるのです。

def make1d(n)
  a = []          # a が配列だという宣言はしておく
  for i in 0...n
    a[i] = 0.0    # a << 0.0 でも良い
  end
  return a
end

さらに、Rubyは足し算で配列を組み合わせたり、掛け算で配列を繰り返すことも出来ます。

a = [1, 2] + [4, 8, 16]  # a = [1, 2, 4, 8, 16] となる
b = [1, 2, 3] * 2        # b = [1, 2, 3, 1, 2, 3] となる

このことを利用すると、make1d(n) はここまで簡単になります。

def make1d(n)
  return [0.0] * n
end

Array.new(n) とかいう長ったらしい宣言をして、forループを回して初期化していたのが馬鹿馬鹿しく思えてくるのではないでしょうか。しかし、調子に乗って make2d(m, n) まで次のように書いてしまってはいけません。

def make2d(m, n)
  return [[0.0] * n] * m  # NG!
end

なぜこれが駄目なのかと言うと、[0.0] * n という1つの同じ配列をm個持つ2次元配列が出来てしまうからです。配列の代入は基本的に行ってはならなかったのを思い出してください。例えばこの make2d(m, n) を a = make2d(3, 2) として呼び出し a[0][0] = 1.0 とすると、a[1][0] も a[2][0] も 1.0 になってしまうのです。

ともかく以上に見てきたように、Rubyでは Array.new() を用いなくとも十分にプログラムが書けると私は思います。それなのになぜ、大学では配列を Array.new() で作るものだとして教えるのでしょうか。以下は完全に私の推測になりますが、Rubyは非常に柔軟で高機能な言語であるために配列をかなり自由に扱うことが出来ますが、他の言語ではそうでないことも多いため、Rubyに限らず通用するプログラミングの技術を教えようとしているのではないでしょうか。例えばC言語では、配列を宣言したら後で要素数を変更できないだけでなく、宣言するときに要素数として変数を用いることすら出来ないなど、Rubyと比べて非常に強い制約がかかっています（Rubyで例えるなら a = Array.new(10) のようにせねばならず、Array.new(n) のnのような変数を含むことが出来ない）。じゃあ何でRubyで教えてんだよって気がしないでもないですが、そういう理由でも無いとわざわざ長ったらしい Array.new() を使わせる必要は無いように思えてしまいます。

まあもしかしたら理由はもっと単純で、a = Array.new(n) でn個の要素を持つ配列を作りましたよ、とする方がプログラミング初心者には分かりやすいだろうと考えたからなのかもしれません。どうせこれで配列を作っても全ての要素はnilなので、a = [ ] とするのと変わりないと思うのですが。

ただ、散々に言われた Array.new() もちょっと書き換えるだけで有効に使うことが出来ます。実は Array.new() には引数を2つ与えることが可能で、1つ目の引数を要素数とし、全ての要素を2つ目の引数で初期化した配列を一発で作ることが出来るのです。これを用いれば、make1d(n) は次のように簡単に書くことも出来ます。

def make1d(n)
  return Array.new(n, 0.0)
end

最初から授業でこれ教えろって話ですわな。

↑ 目次に戻る

第5週 11/8

今回は、同じ処理をする関数を繰り返しと再帰でそれぞれ作ってみるといった内容の授業でした。繰り返しの節で新しく出てきたwhileというキーワードの軽い説明と、考え始めるとドツボに嵌まるかもしれない再帰関数についての解説をしたいと思います。

while

whileは条件式が真である間、処理を繰り返します。whileを用いて階乗を求めるプログラムを書くと次のようになります。

def fact(n)
  f = 1
  while n >= 1
    f *= n     # f = f * n と同じ
    n -= 1
  end
  return f
end

これで if、for、while という3つのキーワードを習ったことになります。この3つのキーワードだけでも様々な処理を記述することができるので、何か自分が面白そうだと思うプログラムを色々と書いて遊んでみるのも良いのではないでしょうか。

再帰関数

再帰関数とは、関数の定義の中でその関数自身を再び呼び出す処理を含む関数のことです。当然、終了条件無しに自分自身を呼び出し続ければ永遠に処理が終わらなくなってしまうので（実際にはスタック領域不足などによりエラー終了しますが）、再帰関数を書くときは次の原則が守られているか注意する必要があります。

終了条件が定義されていること
全ての再帰呼び出しはいずれ必ず終了条件に到達すること

ただ説明するだけでは理解しにくいかもしれないので、具体的な例を挙げて考えることにします。先ほどの階乗を求めるプログラムを再帰を使って書くには、階乗が数学的に次のように書けることを利用します。

$n! = \left\{ \begin{array}{ll} 1 & (n=0,\, 1) \\ n \times (n-1)! & (n\geq 2) \end{array} \right.$

このとき、まず終了条件は n = 0, 1 であることとなります。次に、定義に含まれる再帰呼び出し (n-1)! は、次第に数字が小さくなっていき、いずれ n = 0 または n = 1（実際には n = 1 にしかなりませんが）という終了条件に必ず到達するため、この関数定義は上に書いた再帰関数の原則が守られています。よって、これをプログラムの言葉に書き換えてあげれば、正しく動作するプログラムになるのです。

def fact(n)
  if n == 0 || n == 1
    return 1
  else
    return n * fact(n-1)
  end
end

これは、漸化式を遡って計算していると捉えることも出来ます。漸化式を初項から順に計算しているのが繰り返しによるプログラム、逆向きに遡っているのが再帰によるプログラムと考えると両者の特徴が理解しやすいかもしれません。

なお、こういった再帰関数が具体的にどのように動作しているのかを追い始めると混乱するのではないかと思います。今回の階乗の例は非常に単純なので動作を追うのはそう難しくありませんが、複雑な再帰関数の場合は、終了条件があって全ての再帰呼び出しがいずれ終了条件に到達すれば動作するんだ、という表面的な理解に留めて深追いしないのが良い選択なのではないかと思います。

ところで、再帰により定義したこの fact(n) に n = -1 という引数を与えるとどうなるでしょうか。少し考えると分かる通り、永遠に終了条件には到達せずエラー終了してしまいます。階乗は（拡張云々の話は横に置けば）非負の整数に対してのみ定義されている関数なのでこのような引数は与えるべきではありませんが、再帰関数を書く場合は本当に常に終了条件に到達するかどうかの確認を忘れないようにしましょう。

さて、ここで再帰を用いて組み合わせの数を求めるプログラムを再び考えてみることにします。授業ではパスカルの三角形の要領で関数を再帰的に定義したのでした。授業で扱うだけあって、巧妙に終了条件が洗練されています。

def combination(n, k)
  if k > n
    return 0
  elsif k == 0
    return 1
  else
    return combination(n-1, k-1) + combination(n-1, k)
  end
end

ただ、この関数は確かに正しい答えを有限時間で返すのですが、combination(30, 10) などを計算させてみると分かる通り、処理に非常に時間がかかります。この理由は、次のように考えることが出来ます。

例えば combination(5, 3) を計算させると関数内で combination(4, 2) と combination(4, 3) を呼び出しますが、これら2つの呼び出された関数はどちらも combination(3, 2) という同じ呼び出しを行います。同様に combination(2, 2) と combination(2, 1) は3回、combination(1, 1) は6回、……というように再帰が深くなるにつれて何回も同じ呼び出しを重複して行ってしまうことで、処理に時間がかかってしまうのです。

さらに、この関数定義の特徴から combination(n, k) が呼び出される回数をある程度見積もることも出来ます。この関数は終了条件を満たすときに0か1を返し、それ以外の場合は自身の足し算を行っているので、例えばこの関数が10という値を返したときは、少なくとも関数が1を返す条件で10回呼び出されたことが分かります。つまり、少なくとも返す答えの回数だけ関数が呼び出されるのです。combination(30, 10) の場合は答えである30045015回以上の関数呼び出しを行っていることになり、これでは計算に時間がかかるのも当然です。

そのため、組み合わせの数をパスカルの三角形の要領で求めるプログラムを書くなら、繰り返しによるプログラムを書くのが良いでしょう。

def combination_loop(n, k)  # 先生のページにある combination_loop とは少し処理が異なります
  c = make2d(n+1, n+1)
  for i in 0..n
    for j in 0..i
      if j == 0 || j == i
        c[i][j] = 1
      else
        c[i][j] = c[i-1][j-1] + c[i-1][j]
      end
    end
  end
  return c[n][k]
end

繰り返しではなく再帰にこだわるという場合も、同じ呼び出しを重複して行わなければ良いのだろうということで、既に呼び出した場合についてはメモを残し、再び呼び出すときにメモがある場合には再帰を行わないように改良することで、繰り返しの場合と処理時間を同程度にすることも出来ます。

（とまあ長々と書いたのですが、こういった計算量に関する内容は、恐らくフィボナッチ数を再帰的に求めるプログラムを例に、次週以降の授業で扱われるはずなので今理解する必要は無いです）

以上に再帰関数の特徴や注意点を書いてきたわけですが、これだと繰り返しではなくわざわざ再帰関数を使うメリットは無いように思われてしまうかもしれません（実際、授業で扱った関数や教科書の練習問題で扱われている関数を、繰り返しで書けるにも関わらず再帰を用いて書くメリットはほとんどありません）。そこで、以下では再帰関数の利点を2つ挙げたいと思います。

まず1つ目は、ほとんど数学的な定義のまま関数を書けるため、場合によってプログラムの記述が簡潔で分かりやすくなるということです。ユークリッドの互除法を用いて2つの整数の最大公約数を求める関数を、繰り返しと再帰のそれぞれで書いてみると次にようになります。

def gcd_loop(x, y)
  while y != 0
    t = y
    y = x % y
    x = t
    # 実はこの3行はRubyでは「 x, y = y, x % y 」と1行で書けるのですが、他の言語はそうでないことも多いので...
  end
  return x
end
 
def gcd(x, y)
  if y == 0
    return x
  else
    return gcd(y, x % y)
  end
end

人それぞれではあるかもしれませんが、再帰を用いて書いた方が分かりやすいと感じる人の方が多いのではないでしょうか。このように、再帰を用いると洗練されたプログラムを書くことが出来る場合があります。

利点の2つ目は、再帰を用いないと解けない（あるいは非常に記述量が増えてしまう）ような問題に対応できるということです。今回の課題であるシェルピンスキーのカーペットの生成などがそうですが、典型的な別の例としてハノイの塔の問題を挙げることにします。ハノイの塔についての説明はリンク先のWikipediaで理解してもらうとして、その解き方について考えることにします。

3本の棒にA、B、Cという名前をつけ、AからCにn枚の円盤を移動させるとします。このとき、次のような解法を用いることが出来ます。

n = 1 の場合、A→Cに直接移動する
n > 1 の場合
1. 上からn-1枚の円盤を、Cを作業用に用いつつA→Bに移動する
2. Aの一番下にあった円盤をCに移動する
3. Bに移動したn-1枚を、Aを作業用に用いつつB→Cに移動する

これは解法自体が再帰的になっており、いかにも再帰関数の出番といった感じです。円盤の移動のさせ方を表示するプログラムは次のようになります。

def hanoi(n, from, to, work)      # 4枚の円盤をAからCに移すには hanoi(4, "A", "C", "B") のように使う
  if n == 1
    print from, " -> ", to, "\n"  # A -> C [改行] のように画面に表示するコード
  else
    hanoi(n-1, from, work, to)
    print from, " -> ", to, "\n"
    hanoi(n-1, work, to, from)
  end
end

何とたったの9行でプログラムが書けてしまいました。再帰関数はこのように時として非常に強力な手段となり得るのです。

11/15 追記：
ハノイの塔の記事は11/9（金）の夜に書いたものですが、意図せず課題6と被らせてしまったようです（課題で要求されている内容は若干異なるので、当然上記プログラムのままでは駄目ですが）。今後はこういったことが無いよう、昨年度以前の授業内容を把握しておこうと思います...

課題5の解答例

またしても解答を上げてくれたようなので、リンク貼っときます。
俺としてはこれくらい自分で考えろよと突き放しそうなものだけど、全く親切な人もいたものです。

task5_Sierpinski.png

とりあえず課題8の解答例です。参考程度にどうぞ。
教科書の通りにやれば出来るはず……。
task8_sorting.png

↑ 目次に戻る

最終更新 2012年12月06日 (木) 15時23分52秒

「情報科学」をウィキ内検索

最終更新：2012年12月06日 15:23

添付ファイル

2012年度入学理科一類31組のページ

メニュー

リンク

更新履歴

情報科学

基本情報

目次

自宅の環境でRubyを使う

トラブルシューティング

Emacsの使い方

第1週 10/11

irbを電卓代わりに使う

第2週 10/18

第3週 10/25

return

elsif

median.rbの解答例

第4週 11/1

コメント

繰り返し

配列

画像の表現

配列の前後の値の平均を求める

オリジナル画像の例

課題4の解答例

余談：Array.new(n) は必要か？

第5週 11/8

while

再帰関数

課題5の解答例

名前:
コメント:

2012年度入学 理科一類31組のページ

メニュー

リンク

更新履歴

情報科学

基本情報

目次

自宅の環境でRubyを使う

トラブルシューティング

Emacsの使い方

第1週 10/11

irbを電卓代わりに使う

第2週 10/18

第3週 10/25

return

elsif

median.rbの解答例

第4週 11/1

コメント

繰り返し

配列

画像の表現

配列の前後の値の平均を求める

オリジナル画像の例

課題4の解答例

余談：Array.new(n) は必要か？

第5週 11/8

while

再帰関数

課題5の解答例

2012年度入学理科一類31組のページ