前回の授業では、def-endを用いてメソッドを定義する方法について学んだ。プログラムの中で繰り返し使用する処理をメソッドとして独立させておくと、毎回呼び出せばよいことになり、同じことを何度も書く必要がなくなるというメリットがあった。今日は、メソッドが自分自身を呼び出すという特殊な用法について学ぶ。メソッドが自分自身を再度呼び出すことを再帰呼び出しと呼ぶ。

1つ例を挙げよう。以下の図は10進数XをY進数に変換する手続きを示したものである。これまでは10進数を2進数や16進数に変換する方法を取り上げてきたが、同じ方法で6進数や9進数に変換することもできる。

ここでは2進数への変換を取り上げるため、左端の10進数150を2進数に変換する手続きのみを確認する。2進数に変換するためには2で割り続け、商を下に書き、余りを右に書く。これを延々と繰り返し、商が0になった時点で右側に書かれた余りを下から上に向かって読むと、2進数に変換した結果となる。

ここで、10進数の150を2進数に変換する手続きを以下のように言うことも出来る。

75を2進数に変換した結果は「1001011」であるから、150を2進数にするためには、末尾に150%2の結果である「0」を追加して、「10010110」となる。では、10進数75を2進数に変換するためにはどうしたらよいだろうか。これは次のように定義をすることができる。

登場する数字は異なるが、定義自体は150の場合と同様である。同じように37を2進数に変換する場合も

となる。同じ定義が延々と繰り返されるわけである。プログラムの中で同じ処理を繰り返し行う場合は、def-endでメソッドを作って呼び出すのが効率的であることから、これについてもメソッドを作成することが考えられる。

しかし、10進数150を2進数に変換するためのメソッドを作っている最中であるとすれば、そのメソッドが行う処理の内容を書いている途中で、再度そのメソッドを呼び出さなければならないと言うことになる。これが、再帰呼び出しである。

ちなみに、これまでの定義では150とか37というような具体的な数字を入れ込んでいたが、これをもう少し一般化してみよう。

これらの数字に着目すると、150と75の関係、75と37の関係はいずれも150/2=75、75/2=37というように2で割った値であることがわかる（整数なので小数点以下は切捨てとなるので75/2=37が成り立つ）。したがって、10進数nを2進数に変換するための定義は次のように書くことができる。

nを使えば、これまで延々と書いてきた定義を、1つの定義で済ませることができる。ただし、これだけでは定義としては不十分である。進数変換は商が0になった時点で終了というストップルールがある。割られる数<割る数の場合に商が0となるので、この条件を組み込めば上の定義は次のように書き直すことができる。

2進数への変換の場合は割る数は常に「2」なので、n<2としている。n<2であれば必ず商は0になるので、この時のn%2の値が変換した2進数の先頭の値になる。

では、上で作成した定義に基づいてプログラムを作成してみよう。

#!/usr/koeki/bin/ruby
# -*- coding: utf-8 -*-

def henkan(n)
  if n < 2
    n%2
  else
    sho = n/2
    amari = n%2
    henkan(sho).to_s + amari.to_s
  end
end

print "10進数を入力（2進数に変換します）："
data = gets.chomp!.to_i
printf("%dを2進数に変換すると%dです。\n",data, henkan(data))

プログラムを実行するとdef-endの下から処理が始まり、10進数の入力が促される。これをdataに代入し、最終行のhenkan(data)でhenkanメソッドを呼び出している。

henkanメソッドはif文を用いた分岐が行なわれており、if側は2で割り付けた際の最後の1回の処理の時のみ使われる（ストップルール）。これは、先ほどの定義のうち、「ただし、n<2の場合は変換結果はn%2となる」の部分に相当する。

else側がそれ以外の場合で、2で割った値をshoに、2で割った余りをamariに代入した上で、henkan(sho).to_s + amari.to_s　としている。これは、定義の中の「10進数n/2を2進数に変換した結果の末尾にn%2をつけたものである。」の部分を書いたものである。n/2を2進数に変換した結果は既知ではないので、henkan(sho)として、再度メソッドを呼び出している。なお、余りを末尾に追加するにあたり、仮にhenkan(sho)+amariとすると数字の足し算となるため、たとえば1+1は11にならず2になってしまう。これを避けるため.to_sメソッドをつけて文字列に変換している。

10進数を2進数に変換するプログラムをみてきたが、6進数や9進数への変換も同様の手続きで行なうことが出来る。これを踏まえた上で、次の1番、2番を実施しなさい。難しいと感じる場合は1番のみでも構わない。

1. 10進数XのY進数への変換について再帰的な定義をせよ。定義を文章で書けばよい。
2. 10進数を2進数に変換するプログラムを書き換え、10進数を2〜9進数に変換できるようにせよ。実行時に元の10進数に加え、何進数に変換したいか（ただし、2〜9進数に限定）を入力させ、この2つの値を使ってhenkanメソッドを呼び出せばよい。

制限時間は15分。出席点は2点。提出要領は下記の通り。

• 提出先：課題提出用メールアドレス
• メールのSubject：attend06
• 本文の構成：1行目で学籍番号、氏名を記載する。2行目以降に解答を記載する。

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

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

1からNまでの足し算

1からNまでの足し算を例に挙げ、再帰について考えてみよう。

例えば、5までの足し算の場合、1+2+3+4+5とか5+4+3+2+1と書く。Nまでの足し算の場合はN+(N-1)+(N-2)+...+2+1となる。

再帰的な方法で1からNの足し算の計算方法を定義してみよう。

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

#!/usr/koeki/bin/ruby
# -*- coding: utf-8 -*-

def sum(n)
  if n == 1
    1
  else
    n + sum(n-1)
  end
end

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

printf("1から%dまで足すと%dになります。\n",number,sum(number))

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

n + sum(n-1)

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

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

1. sum(4)が呼び出される
2. sum(4)=4+sum(4-1)なのでsum(3)が呼び出される
3. sum(3)=3+sum(3-1)なのでsum(2)が呼び出される
4. sum(2)=2+sum(2-1)なのでsum(1)が呼び出される
5. sum(1)=1なのでsum(1)として1が返される
6. sum(2)=2+sum(1)なのでsum(2)として3が返される
7. sum(3)=3+sum(2)なのでsum(3)として6が返される
8. sum(4)=4+sum(3)なのでsum(4)として10が返される
9. 「1から4まで足すと10になります」と表示される

階乗の計算

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

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

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

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

#!/usr/koeki/bin/ruby
# -*- coding: utf-8 -*-

def factorial(n)
  if n <= 1
    1
  else
    n * factorial(n-1)
  end
end

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
# -*- coding: utf-8 -*-

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              # 配列に好きな数値を順次代入
  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を呼び出した結果

sime{c1xxxxx}% chmod +x quick_sort.rb[Return]
sime{c1xxxxx}% ./quick_sort.rb[Return]
好きな数字を入力(終了は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]

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番目に小さい値が入ることになる。これを繰り返すことで、最終的に小さい順の並び替えが完了する。

tgifはドロー系のソフトである。ドロー系ソフトとは線や四角、円などのパーツを組み合わせて図形描画を行うソフトである。パワーポイントで図形を描画するのと同じ要領である。

Tgifではこんな絵を描くことができる。

• 2008年度
• 2010年度
• 2011年度
• 2012年度
• 2013年度
• 2014年度
• 2015年度

起動と終了

デスクトップで左クリックをしてルートメニューを出し、[グラフィクス]→[tgif]で起動

終了はtgif画面でCtrl+qまたは、メニューバーのFileからQuit

メニュー

左側のボタンが図形を描画するための作図メニュー、上部のボタンが塗りつぶしパターンや塗りつぶし色、線の太さなどの書式設定メニューとなる。

各メニューの詳細は、Tgifの使い方のページ（外部ページ）を確認のこと。

作図方法

日本語を入力する方法

左側の作図メニューでT（Text）を選び、ドローエリア内の文字を配置したい場所をクリックする（後で移動できるので適当な位置でよい）。その後Ctrl+SPCを押すと、knput2（日本語入力窓）が起動する。アルファベットを先に入力してしまうと英語フォントに切り替わってしまい、Ctrl+SPCを押してもkinput2が起動しない。うまくいかない場合は、Fontメニューで日本語フォントであるRyuminかGothicを選択してからCtrl+SPCを押す。なお、Fontメニューはドローエリア内でマウスの中ボタンをクリックすると出現する。

日本語入力のOFFは、SHIFT+SPC

Ctrl+SPCを押したときに

There is no Selection Owner of _JAPANESE_CONVERSION_

というエラーが出るときは、kinput2が落ちている。ktermから

sime{c1xxxxx}% kinput2 &[Return]

とすると、kinput2が使えるようになる。

グリッドの変更

保存