授業資料/09 の変更点

追加された行はこの色です。
削除された行はこの色です。
授業資料/09 へ行く。
授業資料/09 の差分を削除
#contents

* 前回の課題について [#f3b70592]

まず前回の総仕上げを再掲すると，以下のようであった．
&br;
n x m 行列のデータを入力したら，その行列と転置行列をそれっぽく表示するプログラムを書こう．
&ref(/materials/warning.png); もちろん，任意のサイズの行列に対して動作しないといけない！
ただし，行列の形になっていないデータは想定しなくても良い．
&br;

** 全体構造 [#u0c10b6b]
なにはともあれ，最初は全体構造からである．
今回の場合，行列の転置操作なども必要なので，それも考慮すると例えば次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# ベクトルを表示する(以前のプログラムからコピー)
def print_vec(v_x)
  print("[ ")
  for i in 1..v_x.size do
    print(v_x[i-1]," ")
  end
  print("]\n")
end

# 行列を表示する(以前のプログラムからコピー)
def print_mtx(m_a)
  for i in 1..m_a.size do
    print_vec(m_a[i-1])
  end
end

# 行列の転置を行う
def transposed_mtx(m_a)
  # 実装は後で．
  return m_a
end


# 以下，プログラム本体

# 行列の入力を受ける部分

# 入力行列．大きさが分からない以上，最初は空っぽにしておくしかない．
matrix = []

# 入力を促す
print("? : ")
while (x = gets) do
  x.chomp!
  data = x.split()
  data.map!{ |e| e.to_f }
  # この上までは決まったパターン.

  # さて，行列にデータを動やって足し込む？

  # 入力を促す
  print("? : ")
end

# 入力行列の表示
print("Input matrix = \n")
print_mtx(matrix)

print("\n")

# 入力行列の転置の表示
print("Transposed matrix = \n")
print_mtx(transposed_mtx(matrix))
}}
こう書いてしまうと残った処理はごく簡単なことが分かる．

** 入力データを行列として扱う [#q83107de]

まずは，入力された「行データ」を行列に足し込む処理部分を完成させよう．そのあたりは次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# 入力を促す
print("? : ")
while (x = gets) do
  x.chomp!
  data = x.split()
  data.map!{ |e| e.to_f }
  # この上までは決まったパターン.

  # 行データを push するだけでよい！！
  matrix.push(data)

  # 入力を促す
  print("? : ")
end
}}

** 行列の転置操作 [#l6b7567e]

あとは転置処理だけだ．これももう今となっては簡単で，次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
def transposed_mtx(m_a)
  # 考えると，縦横のサイズは下の方法で得られる．
  n = m_a.size
  m = m_a[0].size

  # 転置行列のもとを作る．
  m_b = Array.new(m){ Array.new(n){0.0} }
  
  # 中身を入れていくだけ.
  for i in 1..n do
    for j in 1..m do
      m_b[j-1][i-1] = m_a[i-1][j-1]
    end
  end

  # 転置行列を出力．
  return m_b
end
}}
やってみればこれだけの話だ．難しくないだろう．

* 関数の自己言及: 再帰定義 [#o676defb]

さて，Ruby などのある程度真っ当な言語では，非常に便利な機能「関数の再帰定義」が可能である．
そこで，この再帰定義について学ぼう．
&br;

まず用語の説明をしておくと，関数の再帰定義が可能とは，「関数の定義文中に，自分自身の呼び出しが使える」というものである．
といってもピンと来ないだろうから，例を使って説明しよう．
&br;

&ref(/materials/notes.png); ''sum(n) := 1 + 2 + ... + n'' という関数を再帰定義を使って定義してみるので，以下の例から理解しよう．
&br;

まず，対象となる関数を自分自身を呼び出す形で「数学的に」定義しなおす．
この ''sum'' の例だと，(n を正整数として)次のようにできることをまず理解しよう．
&ref(./sum.png);
&ref(/materials/warning.png); 左辺を定義する式である右辺に，左辺と同じ ''sum'' 関数が登場していることに着目すべし．
&br;

&size(24){''再帰定義が成り立つ条件とは?''};

この再帰定義が「意味を持つ」には以下のポイントが満たされていることが必要である．よく考えてみよう．
+ ''左辺を右辺で置き換え，さらに右辺で置き換え… と続けていける形になっている．''
+ ''置換えの繰り返しが「必ず終わる」ようになっている''：この例だと，必ず ''n=1'' の場合に到達するようになっている．

&ref(/materials/NG.png); 定義置換えの繰り返しが「終わらない」定義を行った場合，プログラムは永遠に停止しない! 必ず定義が最終的に完結するように注意して定義しよう．
&br;

さて，再帰定義の意味はわかったとして，これをプログラムで利用するにはどうするかを学ぼう．
実は使い方は簡単で，「ほぼそのまま」書けば良い．
例えばこの例の場合はプログラムを書くと次のような感じになる．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
def sum(n)
  if (n == 1) then
      return 1
    else
      return sum(n-1) + n
  end
end
}}
&br;

さて，これで動くのだろうか? という疑問を持つ学生もいるだろう．そこで実際に試してみよう．
上の再帰定義を使って，''sum(10)'' などが確かに正しい数字になることを確認してみよう．
&br;

さて，再帰定義のなにが便利なのかを示そう．鋭い学生にはもうわかると思うが，再帰定義の最大の利点はつぎのものである．
&br;
CENTER:&ref(/materials/OK.png);&size(24){''再帰定義は「定義を書くだけでよい」.''};
CENTER:&size(24){''計算手順をプログラムしなくて良い.''};
&br;

よく考えれば不思議なことではない．繰り返して定義を適用すればいつか必ず完結する定義なのだから，コンピュータがそうしてくれるだけなのだ．
しかし，これが実際はとても便利なことが多いのだ．以下，例で理解しよう．

** ユークリッドの互除法 [#aa8190f7]

二つの正整数 ''n, m'' (n >= m) の最大公約数を考えよう．
この時，数学的に次の性質が成り立つ．
CENTER:&size(18){''n と m の最大公約数は m と (n mod m) の最大公約数に等しい''};
&br;

よって，これを使うと二つの正整数 ''n, m'' (n >= m) の最大公約数を求める関数 ''gcd(n,m)'' について次のような再帰定義式が成り立つ．
&ref(./gcd.png);
&ref(/materials/warning.png); この式が再帰定義の条件を満たしていることを確認しよう.
&br;

これをそのままプログラミングすると以下のようになる．ただし，(n >= m) という条件を念のために確実にしておこう．そのためにちょっとだけ処理が必要だがどうやっているかは下のプログラムを読もう． 
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
def gcd(n,m)
  # 念のため，n >= m を確実にしておく.
  if (n < m) then
    n,m = m,n
  end

  # あとは再帰定義の式の通り.
  if (n % m == 0) then
      return m
    else
      return gcd(m, (n % m) )
  end

end
}}
&ref(/materials/notes.png); これで実際に例えば 120 と 45 の最大公約数 15 が正しく求まることを確認しよう．
&ref(/materials/warning.png); この再帰定義を「使わずに」最大公約数を求めるプログラムがどれくらい面倒なものになるか想像しよう.
&br;
なお，途中の経過がよく分からないという人は，次のように途中経過を出力するように数行付け加えたプログラムを動かしてみると良い．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# 最大公約数を求める関数
def gcd(n,m)
  # 念のため，n >= m を確実にしておく.
  if (n < m) then
    n,m = m,n
  end

  # 現在 対象としているの二つの数字と，その mod を出力.
  print(n," mod ",m, " = ",n % m,"\n")

  # あとは再帰定義の式の通り.
  if (n % m == 0) then
      # 計算終了
      print("Finished. \n")
      return m
    else
      return gcd(m, (n % m) )
  end
end

# 以下，プログラム本体
n = 1071
m = 1029

# 最大公約数を関数を使って計算して表示
print("gcd(",n,", ",m,") = ",gcd(n,m),"\n")
}}

** ループ操作との関係 [#x2f67147]

''for'' や ''while'' などのループではループが終わってから再びループに入る動作が主な動作だが，これは自分自身を呼び出す再帰定義と本質的には同じ行為だ．
ということは，ループ計算は再帰定義で書きなおすことができるはずだし，逆もまた真のはずだ．
つまり，
&br;
CENTER:&size(24){''ループ計算は再帰定義で書き直すことが出来，''};
CENTER:&size(24){''再帰定義はループ計算で書き直すことが出来るはず．''};
&br;

ということになる．

*** ループを再帰で書き直す例 [#ga7a420b]

例えば，先の Fizz Buzz 関数で数字が何回変換されたかをチェックするプログラムを再帰定義を使って書き換えると以下のようになる．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# Fizz Buzz 関数
def fb(n)
  if (n % 15 == 0) then
      return "Fizz Buzz"
    elsif (n % 3 == 0) then
      return "Fizz"
    elsif (n % 5 == 0) then
      return "Buzz"
    else 
      return n
  end
end

# 変換された整数が last_n になるまで調べ続ける関数
# i は Fizz Buzz 関数でこれからチェックする整数．
# n は これまで変換された整数の個数．
def fb_count(i, n, last_n)

  # まだ「変換数」が足りないなら
  if (n < last_n) then 
    # 画面出力
    print(fb(i),"\n")

    #「Fizz Buzz の出力が単なる数字でない = 変換された」としてカウントを増やす
    if (fb(i) != i) then
      n += 1
    end

    # 次の数へ
    i += 1

    # 自分自身を下請けにして
    fb_count(i, n, last_n)

  end
end

# 以下，プログラム本体

# 変換された整数をいくつ数えるか
n_upper = ARGV[0].to_i

# 変換された整数が n_upper になるまでチェックさせる.
fb_count(1,0,n_upper)
}}
&ref(/materials/warning.png); ''while'' ループの代わりに再帰定義が使われている部分に特に着目して，理解しよう．

&br;
*** 再帰をループで書き直す例 [#e26fc0a8]

例えば最初の再帰定義の例である ''sum'' 関数も，''for'' ループで書き直すのは簡単だ．
また, ユークリッドの互除法も同様に適切なループで書き換え可能である．

&ref(/materials/notes.png);  (時間に余裕のある人向け) ユークリッドの互除法を再帰定義を使わずにプログラミングしてみよう．

&br;
*** 再帰とループ，どっちが得? [#b14d721d]

再帰定義とループ計算が本質的に同じなら，どちらを選ぶべきかという問題がでてくる．
これについては，二つの視点がある．
&br;

まず，プログラムのわかりやすさだが，これは問題による．ユークリッドの互除法などは再帰定義がわかりやすいが，先の Fizz Buzz などはループの方がわかりやすいだろう．
大きく書いておくと，
&br;
CENTER:&size(24){''再帰とループのどちらがわかりやすいかは問題による''};
&br;

次に，計算の速さやコンピュータにかかる負荷についてである．
これはほぼはっきりしていて，自分自身を何回も呼び出す仕組み上再帰定義の方が負荷が高い．
これを大きく書いておくと，
&br;
CENTER:&size(24){''再帰は魔法なので MP を喰う''}; (MP = Machine Power)
&br;

となる．
結局，メリットもデメリットもあるので，再帰定義を使うべきかどうかはケースバイケースということになる．

&br;
* 今日の総仕上げ [#f5f3dd6e]

Fibonacci 数列 ''F_0, F_1, F_2, ... '' を計算して出力するプログラムを「二つ」書こう(Fibonacci 数列の定義を知らない人は調べよう)．
ただし，以下の条件を満たすものとする．

+ F_0 = 0, F_1 = 1 とする.
+ 起動時に正整数パラメータ ''n'' (30ぐらいを想定)が与えられ，F_0, F_1, F_2,... F_n までを出力するものとする．
+ プログラムA は，再帰定義を用いて計算するとする．
+ プログラムB は，ループ計算を用いて計算するとする．

具体的には，例えばプログラムA のファイル名が fibonacciA.rb だとすると，
  ruby -w fibonacciA.rb 30

として実行すると，
>  F_0 = 0
>  F_1 = 1
>  F_2 = 1
>  F_3 = 2
>  F_4 = 3
>  F_5 = 5
>  F_6 = 8
>  F_7 = 13
>  F_8 = 21
>  F_9 = 34
>  F_10 = 55
>  F_11 = 89
>  F_12 = 144
>  F_13 = 233
>  F_14 = 377
>  F_15 = 610
>  F_16 = 987
>  F_17 = 1597
>  F_18 = 2584
>  F_19 = 4181
>  F_20 = 6765
>  F_21 = 10946
>  F_22 = 17711
>  F_23 = 28657
>  F_24 = 46368
>  F_25 = 75025
>  F_26 = 121393
>  F_27 = 196418
>  F_28 = 317811
>  F_29 = 514229
>  F_30 = 832040

という結果がでるようにしろ，ということになる．

&ref(/materials/warning.png); プログラムが二つできたら，両方実行して「答えがおなじになること」「計算速度が違うこと」をきちんと確かめよう． また，プログラムの作り易さの違いについても考察しておこう．
&br;
&ref(/materials/warning.png); (上級者向け) 再帰定義でありながら「実行速度が速い」プログラムを書いてみよう．どうすればよいだろうか.

&br;
* レポート [#h0fb364d]

本日受けた講義および行った実習について，簡単にまとめた報告をせよ.
また，総仕上げの部分で自分で書いたプログラムを報告せよ.

もちろん各自の

+ 所属(学部，学科)
+ 学籍番号
+ 学年
+ 氏名
+ 日時
+ 肝心のレポート内容(得た知見，作業について気づいたこと等も)

を書くのを忘れないように. 

* about Icons, ClipArts [#h567ccfb]
Some icons in this page are downloadable at [[ICONFINDER:http://www.iconfinder.net/]].

The "note" icon &ref(/materials/notes.png); designed by [[Marco Martin:http://www.notmart.org/]] is distributed with the LGPL licence,
the "warning" icon &ref(/materials/warning.png); designed by [[Alexandre Moore:http://nuovext.pwsp.net/]] with the GPL licence
and the "triangle" icon &ref(/materials/JNorth_arrow-right-sm.png); designed by [[Joseph North:http://sweetie.sublink.ca/]] is distributed with the [[Creative Commons (Attribution-Noncommercial-Share Alike 3.0 Unported):http://creativecommons.org/licenses/by-nc-sa/3.0/]] licence.

Some clip arts used in this page are downloadable at [[Open Clip Art Library:http://www.openclipart.org/]].
We deeply appreciate their superb works. With licence, they describe that "the actual clipart content on open clipart library is Public domain" in the web.

// ━┃┏┓┛┗┣┳┫┻╋


// コマンドライン入力は「行頭をブランクで始める」.
// コマンドライン出力は「行頭を > で始める」.

// 実習アイコン
// &ref(/materials/notes.png); 

// 注意アイコン
// &ref(/materials/warning.png);

// Link アイコン
// &ref(/materials/JNorth_arrow-right-sm.png);

// 大文字での強調 
// CENTER:&size(24){''ほげほげ''};

// programu source 表記
// #highlighter(language=ruby,number=on,cache=on){{}}