(9) 12/04の授業内容:再帰

再帰とは

ある事柄の定義にそれ自身が登場することを再帰という。例えば、今日の授業は何回目かと考えた場合、「前回の回数に1を足したものである」と定義することができる。このような定義は「去年は20歳だったから今年は21歳」、「昨日は15日だったから今日は16日」というように様々な場面で登場する。

この定義にしたがう場合、回数を明らかにする定義の中に、再度回数が出現することになる。これだといつまでたっても今回の回数が明らかにならないような気がするが、「それ以上前に授業がない場合は1回目とする」という定義を付け加えれば、必ず回数は確定する。

複雑な問題を解く場合に、再帰を用いた方が簡単になる場合がある。

再帰を利用したプログラミング

階乗の計算を使って、再起についてもう少し考えてみよう。

階乗の計算とは n! で表記され n!=n*(n-1)*(n-2)*・・・2*1で表現される。例えば5の階乗であれば、5!=5*4*3*2*1となる。

再帰的な方法で階乗の計算の方法を定義してみよう。

再帰的定義
Nの階乗とは　N-1の階乗とNを掛けたものである。ただし、1の階乗は1である

これをプログラムで書くと下記の通りになる（factorial.rb）

#!/usr/koeki/bin/ruby/
def factorial(n)
  if n <= 1
    1
  else
    n * factorial(n-1)
  end
end

STDERR.print "好きな数字を入力してください"
number = gets.chomp!.to_i

printf ("%dの階乗は%dです\n",number,factorial(number))

問題となるのはdef-endの定義内容である。特に下記の行に着目しよう。

n * factorial(n-1)

factorialというメソッドの定義の中で、再度factorialが呼び出されている。

number=4とした場合の、このプログラムの動きを確認してみよう

  1. factorial(4)が呼び出される
  2. factorial(4)=4*factorial(4-1)なのでfactorial(3)が呼び出される
  3. factorial(3)=3*factorial(3-1)なのでfactorial(2)が呼び出される
  4. factorial(2)=2*factorial(2-1)なのでfactorial(1)が呼び出される
  5. factorial(1)=1なのでfactorial(1)として1が返される
  6. factorial(2)=2*factorial(1)なのでfactorial(2)として2が返される
  7. factorial(3)=3*factorial(2)なのでfactorial(3)として6が返される
  8. factorial(4)=4*factorial(3)なのでfactorial(4)として24が返される
  9. 「4の階乗は24です」と表示される

プログラムの流れは上記の通りである。階乗の計算は比較的単純であるため、こんな複雑なことをしなくてもプログラムを書くことができそうな気がする。しかし、再帰的な方法は、複雑な処理を繰り返し行う場合には大きな力を発揮する。

再帰を使用する際のポイントは下記の通りとなる。

  • 問題を分割して考えたときに、分割した部分を解く方法と、全体を解く方法が同じである場合、再帰を使うことができる
  • 問題分割を繰り返し、これ以上問題が分割できない場合に 結果そのものを返す条件ブロックを入れる
  • 分割した問題を再帰的に同じメソッドを呼んで得られた結果を合成したものを最後の結果として返す

再帰を用いたソート

大小関係が定められたデータを、大きい順（降順）や小さい順（昇順）に並べ替える作業をソートという。Rubyにはsortメソッドが備わっており、ソート自体を実行するプログラムを書く必要はない。しかし、実際にはソートは奥の深いテーマであり、いかに効率的に実行するかという観点より様々な方法が提案されている。

クイックソート

n個の要素から任意の要素aを取り出す。残りの要素についてaよりも大きければ右側、小さければ左側に配置する。先頭の要素を基準として左右に振り分ける作業をクイックソートと呼ぶ。クイックソートを繰り返すことで、左右に振り分けられる値が0個もしくは1個となる。この時点で並び替えは終了となる。

クイックソートの考え方

この図では最初に先頭の要素である6を取り出している。そして6を基準として、6よりも大きければ右側に配置し、小さければ左側に配置している。次に左右に配置された要素について、それぞれ先頭（左は3、右は8）を基準として同様にクイックソートを行っている。

2回目のクイックソートを行った時点で、8の左側の山は値が「7」の1つのみとなっている。1つの場合はこれ以上の並び替えはできないため、これで順番が確定になる。3の左右、8の右側についてクイックソートを継続する。

3回目のクイックソートを行うと左から2つの山については順番が確定となる。一番右側の山のみまだ順番が確定していない。

一番右側の山について4回目のクイックソートを実行する。これですべての順番が確定する。

これをプログラムで書くと下記のとおりになる（quicksort.rb）。

#!/usr/koeki/bin/ruby

def quicksort(data)	# 配列(順番がばらばらなデータ)を受け取る

  if data.length <= 1	# データが1個以下なら
    data		# そのものを返して並べ換え完了
  else
    left = []	        # left(左側配列)を新規作成 left = Array.new でも可
    right = [] 	        # right(右側配列)を新規作成 right = Array.new でも可
    k = data.shift	# 配列dataの先頭を取り出してkにする(破壊的操作)

    for x in data	# 残ったdata全てに対して繰り返す
      if x < k 	   	# kより小さかったら
         left << x	# 左側に追加(<<は配列末尾への破壊的要素追加、pushと同じ)
      else
         right << x	# 右側に追加(同上)
      end               # ifに対するend
    end			# forに対するend

    quicksort(left) + [k] + quicksort(right)
    # quicksort(left) と k と quicksort(right) を合体したものが最終結果	
    # kは要素なので[]で括って配列にする
  end                   # ifに対するend
end                     # defに対するend

def ketsugo(a)          # 配列を受け取ってjoinメソッドで結合して返す
  printf("[%s]\n", a.join(", "))
end                     # defに対するend

array = []
while true              # 配列に好きな数値を順次代入
  STDERR.print "好きな数字を入力(終了はq)"
  datum = gets.chomp!
  if datum == "q"
    then break
  end
  array.push(datum.to_i)  # pushで配列arrayの末尾に追加(<<でも同じ)
end

print "もとの順番\n"
ketsugo(array)             # ketsugoメソッドの呼び出し 
print "並べ替え後\n"
ketsugo(quicksort(array))  # ketsugoメソッドの呼び出し
                           # 引数はquicksortを呼び出した結果
%ruby quick_sort.rb
好きな数字を入力(終了はq)400
好きな数字を入力(終了はq)204
好きな数字を入力(終了はq)346
好きな数字を入力(終了はq)958
好きな数字を入力(終了はq)225
好きな数字を入力(終了はq)367
好きな数字を入力(終了はq)784
好きな数字を入力(終了はq)q
もとの順番
[400,204,346,958,225,367,784]
並べ替え後
[204,225,346,367,400,784,958]

その他のソート(1)　バブルソート

n個の要素を想定した場合に、一番最後の値であるA[n]を基準として、A[n-1]、A[n-2]、...と大小比較をしていく。添え字が小さいほうに小さい値が保持されるようにする。例えばA[n]とA[n-1]の大小比較を行った場合、A[n-1]の方が小さければそのまま、A[n]の方が小さければA[n]とA[n-1]を入れ替え、A[n-1]に小さい値が入るようにする。次にA[n-1]とA[n-2]の大小比較をする。今度はA[n-2]に小さい値が入るようにする。これを順番に繰り返しながら先頭のA[1]まで比較を行う。これにより最も小さい値がA[1]に入る。

A[1]に最も小さい値が入ったら、2回目はA[n]から開始してA[2]まで大小比較を行う。2回目の大小比較を行った結果としてA[2]に2番目に小さい値が入ることになる。これを繰り返すことで、最終的に小さい順の並び替えが完了する。

バブルソートの考え方

その他のソート(2)　バゲットソート

最大値をmとするn個の要素がある場合に、これらの数字を記憶する領域（バケット）をm個用意する。10という数値は10番目のバケット、iはi番目のバケットに放り込むというように、対応するバケットに放り込む。これを最後まで繰り返し、最後に1番のバケットから順番に取り出していくと小さい順に並ぶ。20個のデータで、最小1、最大100万というようなセットの場合、20個の並び替えに100万個のバケットが必要になる。

[3,1,7,2]の並び替えを行う場合、並び替え後の配列をbucketとすると、bucket[3]=3, bucket[1]=1というように、代入する値とインデックスを同じ値にして代入をする。この結果としてbucketの中は[nil,1,2,3,nil,nil,nil,7]となる。値が存在しないところは空っぽであるという意味のnilが表示される。あとはnilを取り除けば並び替えが完了となる。

バケットソートの考え方

その他のソート(3)　基数ソート

バケットソートの応用。各要素が全てk桁のm進数（例えば3桁の10進数）であらわされるときに有効なアルゴリズム。まず1桁目についてバケットソートを行い、続けて2桁目についてバケットソートを行う。この際は1回目のバケット番号の小さい順に値を保持する。同様に繰り返し、最後のk桁目のバケットソートを行い、k-1桁目のバケット番号の小さい順に並べれば小さい順に並ぶ。

基数ソートの考え方

ペイント系ソフトGIMPの使い方

GIMPはAdobe Photoshopと同じペイント系のソフトである。GIMPを使用すると簡単にロゴを作成することができる。

起動準備

GIMPを起動する前に、様々な英語フォント(書体)を追加する。これは必須ではないが、標準フォントのみではバリエーションに欠けてしまう。フォントの追加は addfont コマンドを使う(101/102教 室の場合)。

irsv{C10xxxx}% addfont[Return]

GIMPの起動

ktermからgimpと入力して起動する。

irsv{C10xxxx}% gimp &[Return]

& を付けないと、GIMPを終了するまでそのktermで作業ができなくなる。

起動後に表示される「GIMP今日の技」（以下参照）はいろいろなテクニックを紹介しているのみで、特にロゴを作るうえでは不要なので「閉じる」で閉じる。。

今日の技。すぐに閉じてよい

GIMPの終了

起動したGIMPの「道具箱」ウィンドウ（ウィンドウタイトルがThe GIMPとなっているもの）より

ファイル(F) → 終了で終了となる。

The GIMPと書いてあるウィンドウよりファイル→終了で終了

GIMPの強制終了

GIMPを使用していると時折固まることがある。この場合GIMPを起動したktermからkillコマンドを利用して強制終了する。

irsv{C10xxxx}% kill -9 %gimp

これでもうまくいかない場合は、GIMPのどれかのウィンドウの左上のボタンを押し「Destroy」を選択する。この際、保存していないファイルがあり、なおかつ保存ができるようであれば事前に全てしておくこと。固まったままのGIMPを放置するとシステムの負荷が高くなり、他の利用者にも迷惑をかけるので必ず対処する。わからない場合は教員やTAを呼ぶこと。

ロゴの作成→フォントの選択

GIMPの道具箱ウィンドウで「拡張(X) → Script-Fu → ロゴ」と選ぶ とロゴを作成するウィンドウが現れる。ロゴには「立体縁取り」や「エイリアン発光」など様々な種類があるが、ここではとりあえず「霜」（下の図では切れていて見えていないが）を選んだものとして説明を続ける。

ロゴを作る場合、拡張→Script-Fu→ロゴを選ぶ

霜を選ぶと以下のウィンドウが出現する。他を選んでも同じようなウィンドウが出現する。ここで文字とフォントサイズとフォントを変更する。文字は自分で作りたいロゴに使用する言葉とする。フォントサイズは一度作成してから適宜変更してみると良い。フォントの変更は複雑なので以下で詳細に説明する。

文字とフォントサイズとフォントを指定する

フォントを変更するためには上のウィンドウでフォントの右のボタンを押す。すると以下のようなフォント選択ウィンドウが出現するので左側のフォントのリストから自由にフォントを選ぶ。日本語の場合は101/102教室で利用できるのはricoh, kochi, aqua, yozの4種類となる。フォントを選ぶと右側のフォントスタイルでさらに斜体や太字を選ぶことができる場合がある。必要に応じてこれもいずれかを選択する。設定したら「了解」を押す。

フォント設定方法

元のウィンドウに戻るので、さらに「了解」を押すとロゴが生成される。

ロゴの例

保存の方法

作成したロゴを右クリックするとメニューが出現する。そこから「ファイル」→「保存」を選ぶ。保存をするときの形式はPNGを選ぶ。ファイル名をつけ、保存する場所を適宜選択して「了解」を押す。すると、エクスポートするかなど幾つかの質問が行われるが、全てYesに相当するボタンをクリックすると保存が完了する。

その他、 「GIMPの使い方」というキーワードでgoogle検索するとたくさん参考となるページが出てくるのでこれを読めばほとんどの説明は得られるだろう。

GIMPでの画像の大きさの変え方

全体の大きさを変えることができる。画像の上で右クリック、「画像」→「拡大縮小」を選ぶ。幅と高さがXとYで表示されているので、適宜比率を変化させればよい。

出席課題

GIMPでロゴを作成し、PNG形式で保存して添付ファイルで送る。ロゴ自体の完成度については問わないものとする。正しく添付ファイルを送ることができるかどうかを見る。ロゴのテーマも何でも良い。

制限時間は10分。出席点は2点だが、添付ファイルがない場合は1点とする。提出要領は下記の通り。

  • 提出先：naoya@e.koeki-u.ac.jp
  • メールのSubject：ruby09
  • 本文の構成：1行目で学籍番号、氏名を記載する。その他、ロゴを作成した感想があれば記載する。

Tips：emacsでの日本語入力のオンオフはCtrl-oです

Tips：Mewによるメールの送り方はMewコマンドを参照

レポート課題

以下のうちいずれかを選んで解答する。

問題1（6点満点）：GIMPを使用して基礎プログラミング（もしくは情報表現）をあらわす素敵なロゴを作る。6点満点だが極めてよくできている場合は芸術点がさらに加算される場合がある。

問題2（8点満点）：バゲットソートを再帰を使わずに書く。def-endも使用しなくても良い。

問題3（10点満点）：バブルソートを再帰を用いて書く。

  • 提出先：naoya@e.koeki-u.ac.jp
  • 提出期限：12/10(日）23:59
  • メールのSubject：自分の学籍番号-kadai07
  • 本文の構成：1行目で学籍番号、氏名を記載する。2行目以降は下記の構成とする

問題1の場合

  1. GIMPの感想
  2. 作成したロゴを添付

問題2、3の場合

  1. 作成したプログラム
  2. プログラムの実行結果
  3. プログラムの説明
  4. 感想
  • 採点基準（問題1）：期限内提出点（2点）、メールの体裁（1点）、芸術点（3点）
  • 採点基準（問題2、3）：期限内提出点（2点）、メールの体裁（1点）、プログラム（2〜4点）、プログラムの説明（3点）
  • プログラムの説明：問題2は具体的にソートを行っている部分について、問題3はdef-endの中身について、それぞれ詳しく説明する。
  • 説明に関して、文章の意味がわかりづらい場合や、Webページを単にコピー&ペーストしたものは減点することがある。一度読み直してから提出すること。
  • 驚異的に良くできているレポートについては満点を超える得点をつけることがある。
  • よくできていたレポートは、他の人の参考になるよう、本人が特定できないような形で掲載する。掲載してほしくない場合はメールでの課題提出時にその旨記載すること。

Tips：emacsでの日本語入力のオンオフはCtrl-oです

Tips：ktermでのプログラムの実行結果をメールに貼り付けるには、コピーしたい箇所をマウスで選択し、emacs（Mew）上でマウスの真ん中ボタンをクリックする

Tips：Mewによるメールの送り方はMewコマンドを参照