(10)12/07の授業内容

再帰とは

ある対象の定義にそれ自身が登場することを再帰といいます。例えば、今日の授業は何回目かと考えた場合、「前回の回数に1を足したものである」と定義することができます。

このような定義は、一見堅苦しく見えますが、「前回は9回目だったから今回は10回目」や「去年は20歳だったから今年は21歳」などと考えることはよくあることです。

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

複雑な問題を解く場合には、再帰的な方式に則って解いたほうが簡単になるものもあります。

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

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

階乗の計算とは n! で表記され n!=n*(n-1)*(n-2)*・・・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の中味です。特に下記の行に着目しましょう

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よりも大きければ右側、小さければ左側に配置する。左右それぞれに配置された要素についてクイックソートを繰り返すことで最終的に並び替えが完了する。



これをプログラムで書くと下記のとおりになります（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]

バブルソート

n個の要素を想定した場合に、A[n]を基準として、A[n-1]、A[n-2]、... と比較をしていく。比較を行うごとに小さいほうの値を保持し、A[1]まで比較をしていき、その結果をA[1]に入れる。これにより最も小さい値がA[1]に入る。次に同じ動作をA[n]からA[2]まで繰り返し行い、結果をA[2]に入れる。これを繰り返すと一番最後に小さい順に並べ替えが完了する。



バケットソート

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



基数ソート

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



GIMPの使い方

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

起動準備

GIMPを起動する前に、様々な英語フォント(書体)を追加します。これは必須ではないですが、ロゴを作る場合は標準フォントだけだと、 大きな文字をなめらかに作ることができず、さらに種類も少なくなってしまう。フォントの追加は addfont コマンドを使います(101/102教 室の場合)。

% addfont

ただし、フォントを追加すると不安定になるので強制終了する方法も 良くおぼえておくこと(後述)。ロゴを作らない(画像処理だけやる)ときはフォントの追加はしない方が良い。

GIMPの起動

KTermからgimpコマンドを、バックグラウンドで起動する。

% gimp &

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

GIMPの終了

起動したGIMPの「道具箱」ウィンドウ、または任意の画像ウィンドウ で右クリックして

ファイル(F) → 終了

の順に選ぶと終了する。

GIMPの強制終了

フォントをたくさん追加した状態で巨大なロゴを作っていると フォントの供給が間に合わずGIMPが無反応になって固まることがある。 この場合はGIMPを起動したKTermからkill コマンドを利用して、GIMPを強制終了させる。

% kill -9 %gimp

これでもだめならGIMPのどれかのウィンドウの枠にある左上ボタンを クリックし、「Destroy」を選択する。これは少し危険な操作なのでエディ タで作成しているファイルは全て保存してからDestroyすること。なお、固まったままのGIMPを放置するとシステムの負荷が高くなり、迷惑をかけ るので必ず対処すること。

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

GIMPの道具箱ウィンドウで「拡張(X) → Script-Fu → ロゴ」と選ぶ とロゴを作成するウィンドウが現れる。このウィンドウで「フォント」ボ タンをクリックしてフォントを選択する。このときに出てくる フォント選択ウィンドウでは、きれいなフォントを出すために以下の操作 をする。

o 英字の場合

1. 上部の「フィルタ」をクリックする

2. 「鋳造所:」一覧で freefont を選択する

3. 上部の「フォント」をクリックして元に戻る

これで大きな文字が滑らかに出るフォントだけが候補に残る。

o 日本語の場合

日本語は滑らかに出せるフォントが(101教室の場合) 4種類しかない

1. 上部の「フィルタ」をクリックする

2. 「鋳造所:」一覧で ricoh, kochi, aqua, yoz のいずれかを選択する

(freefontが選ばれていたら解除する)

3. 上部の「フォント」をクリックして該当する書体を選び元に戻る

英字のときと同様大きな文字が滑らかに出るフォントだけが候 補に残る。

フォント選択ウィンドウの下部の「プレビュー」枠に 適当な文字をいれておくと、選択しようとしているフォントがどのような 文字の形を持つものか確認することができる。

保存の方法

ロゴの該当する部分を右クリックしてファイルから保存を選ぶ。 保存するときの形式はPNGを選ぶ

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

gimp での署名の入れ方

加工する画像を開く。"T" というアイコンをクリックした後に、署名をする場所を選ぶ。フォントを選び、プレビューに署名を入れる。移動は十字型の矢印が出たら動かすことが出来る。やり直しは Ctrl z。 Ctrl s で保存。PNG 型式にする。

Tips: 日本語は yoz, aqua, zatsuji などがある。 日本語は後に半角の空白を入れるとバランスが取れる (gimp のバグ?)。重ね合わせなどを用いてもっと工夫できるならば他の方法でもよい。

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

全体の大きさを変えることができる。画像の上で右クリック、画像、拡大縮小を選ぶ。比率を変化させると小さくなる。

課題

以下の4つから1つを選んで実施する。

1. バブルソートもしくは基数ソートを実施するプログラムを再帰を使って書く(10点満点で採点)
2. バブルソート、バケットソート、基数ソートを実施するプログラムを再帰を使わずに書く(9点満点で採点)
3. これまでに作成したプログラムを1つ選び、自分のWebページで公開する(8点満点で採点)
4. GIMPを使って情報表現を表すとっても素敵なロゴを作成する(基準点6点+芸術点)

---

作成したプログラム，実行結果をメールでnaoya@e.koeki-u.ac.jp宛に送る．

課題の提出期限は12月13日（火）23:59まで

---

メール送信時の注意

• Subjectは「学籍番号-1207」とすること
• メール本文の構成は選んだ問題によって異なる
• 問題1、2の場合
• 作成したプログラム
• プログラムの説明
• 実行結果
• 感想
• 自由製作課題のメンバー(未提出者のみ)
• 問題3の場合
• 作成したWebページのURL
• 感想
• 自由製作課題のメンバー(未提出者のみ)
• 問題4の場合
• 感想
• 自由製作課題のメンバー(未提出者のみ)
• 作成したロゴを添付する

レポート採点基準(問題1と2):期限内提出(2点)、指示どおりのメールを送っているか(1点)、プログラム(3〜4点)、プログラムの説明(3点)

説明のポイント:今回新しく出てきたメソッド、def-endの中味

レポート採点基準(問題3):期限内提出(2点)、指示どおりのメールを送っているか(1点)、htmlファイルを作成している(2点)、正しい文法で記述されているか(3点)

正しい文法で記載されているかどうかは、下記のサイトでの採点結果に基づき配点を決定します
Another HTML-lint gateway
ここでDATAに自分の書いたWebページを貼り付け、チェックをする
得点がマイナスの場合は0点、50点未満は1点、100点未満は2点、100点は3点とし ます。

Tips

emacsについて

• emacsで新しいファイルを作成する場合は，C-x C-fを押し，ミニバッファにkensaku/kadai2.rbのようにファイル名を入力する
• ファイルの保存はC-x C-s
• 日本語入力のオンオフの切り替えはC-o

Mewについて

• emacsを起動する
• Escとxを押し，mewと入力しReturn（Escとxを押すことを，一般にM-xと表記します）%<--これでMewが起動します
• Mewを起動するとパスワードがたずねられるので入力しReturn
• 新着メールの確認およびパスワードを間違えた場合はiと入力しReturn
• メールを読む場合は，カーソルキー（矢印キー）で読みたいメールを選びReturn
• メールの新規作成はwと入力
• e-mailの本文にテキストファイルを読み込むには，新規送信メール画面の本文を記入するエリアにカーソルを移動し，Ctrl+x，iとすると，ミニバッファにInsert file: ~/と表示されるので，読み込みたいファイル名を入力する。
• プログラムの実行結果の貼り付けは，kterm上の出力結果部分をマウスで選択し，Mewの本文の貼り付け位置にカーソルを移動し，マウスの真ん中ボタンをクリックする
• メールの送信はC-c C-cと入力するか，もしくはメニューのsendアイコンをクリックする
• Mewを終了するにはqと入力
• emacsを終了する