授業資料/10 の変更点

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

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

前回の総仕上げの課題は Fibonacci 数列 ''F_0, F_1, F_2, ... '' を計算して出力するプログラムを「二つ」書けというもので，条件は以下のようなものであった．

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

&br;
** 再帰によるプログラミング [#f5c23fdb]

まずは再帰定義を用いてプログラミングをしてみよう．

&br;
*** 全体構造 [#g2de80bf]
とはいえ，まずは全体構造からである．さくっと作ってしまおう．
例えば，もっとも単純に考えると次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# n 番目の Fibonacci 数を返す関数
def fibonacci(n)
  # 実装は後で
  return n
end

# 以下，プログラム本体

# どこまで出力するか
n_upper = ARGV[0].to_i

# n_upper 番目までのFibonacci 数を出力
for i in 0..n_upper do
  print("F_", i," = ",fibonacci(i),"\n")
end
}}

&br;
*** フィボナッチ関数:再帰定義版 [#f8c43410]
さて，次に肝心の関数 fibonacci を定義しよう．
これはフィボナッチ数列の数学的な再帰定義式をそのまま用いれば良いだけなので簡単だ．次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# n 番目の Fibonacci 数を返す関数
def fibonacci(n)
  if (n == 0) then
    return 0
  elsif (n == 1) then
    return 1
  else
    return fibonacci(n-1) + fibonacci(n-2)
  end
end
}}

さて，これで完成だ．動かしてみよう．30 ぐらいまでやらせるとだいぶ遅いことがよくわかる．

&br;
** ループによるプログラミング [#hbb19e3a]

&br;
*** 全体構造 [#qea9ac9f]
全体構造は，まず上のものと全く同じものを考えよう．

&br;
*** フィボナッチ関数:ループ版 [#gcabf172]
ループ版を作るには，次のような作業をループの中に入れれば良い．

+ 前二つの値を足して，「新しい値」とする.
+ 次に備えて，前二つの値を更新する.

それには，素直に作るのならば例えば次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
def fibonacci(n)
  # n = 0 or 1 なら返す．
  if ( (n == 0) || (n==1) )then
    return n
  end

  # ここへ来るのは n >= 2 の場合．
  pp_n = 0
  p_n  = 1

  for i in 2..n do
    cur_n = pp_n + p_n
    pp_n, p_n = p_n, cur_n
  end

  return cur_n
end
}}
普通の人が普通にループ版のプログラムを書くとこんな感じになるだろう．
&br;

&ref(/materials/warning.png); さて，上のプログラムを見て，''if'' の ''else'' を使わずに済んでいることに気づいた人もいるだろう．
これは ''return'' を実行するとそこで関数が終了する仕組みなので，その仕組みを上手に使っているのである．

もう少し大きな枠の言葉で言うと，例外処理(この場合は ''n=0 or n=1'' にあたる)は関数内で上手に行うと''if'' 文の処理がシンプルで済む，ということになる．
言い換えると，

CENTER:&size(24){''複雑な場合分けは関数の中でやるべし''};
&br;

ということになる．

&br;
** 高速化: 計算のムダを省く [#vd8ef59e]

上のプログラムは，どちらにも既に途中で求めた値をなんども求め直す形になっていて無駄がある．
その無駄を詳しく見ると二種類ある．例を使って示すと次のような感じだ．

+ 例えば F_10 を計算する過程で F_0, F_1, ... F_10 まで求まるのに，次の F_11 を求めるときにまた F_0, F_1, ..., F_10 を計算しなおす無駄．
+ 例えば F_10 を計算する過程の中で，F_4 は 6回も計算し直される無駄．

1 は再帰版にもループ版にも共通する無駄であり，2 は再帰版のみにある無駄である．
&ref(/materials/warning.png); この「二種類」の無駄がわかるだろうか．よく考えよう．

そこでそれぞれ対処を考えよう．

まず無駄 1 について考察しよう．
「数列」というものの性質からして，F_n を求める過程で F_0, F_1, ..., F_n のすべてが自然に求められるのは当然だから，それを利用しよう． つまり，「F_n を答える」という関数ではなく，「F_0, F_1, ..., F_n の配列を答える」という関数にすると自然にこれができそうだ．

&ref(/materials/warning.png); このように，関数とプログラム本体間などの情報の「やりとり」を適切に設計するとよい．これも全体構造を考えるということの一種だ．

&br;
*** 全体構造 [#bd1ece18]
上に書いたように，fibonacci 関数に答えの配列を作らせればよいので，例えば次のようになるだろう．

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

# 配列を整理して表示する関数
def list_print(ary)
  # 実装は後で
end

# Fibonacci 数列を配列で返す関数
def fibonacci(n)
  # 実装は後で

  # とりあえずプログラムが動くように空っぽの配列でよいので返しておく
  return []
end


# 以下，プログラム本体

# 上限値をもらって…
n_upper = ARGV[0].to_i

# Fibonacci 数列を配列で求める．
fb_list = fibonacci(n_upper)

# 得られた結果を表示
list_print(fb_list)
}}

&ref(/materials/warning.png); まずは全体構造を設計することを忘れないように！ そろそろ，プログラム本体にぐだぐだ計算が書いてあるプログラムはレポートとして受け付けないよ．

&br;
*** 各関数の実装: 配列の表示 [#w2c5e48a]

まず，配列を整理して表示する関数はすぐできる．例えば次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# 配列を整理して表示する関数
def list_print(ary)
  for i in 0..(ary.size-1) do
    print("F_", i," = ",ary[i],"\n")
  end
end
}}

&br;
*** 各関数の実装: fibonacci 数列を配列で: ループ版 [#xef68b43]

次に，fibonacci 関数を作ろう．
まずはこの場合は簡単なループ版からチャレンジしよう．
これは配列を使うとものすごくわかりやすく書けて，例えば次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# Fibonacci 数列を配列で返す関数
def fibonacci(n)
  # 最初の二つは既にわかっている．
  fb_list = [0,1] 

  # 前二つを足した数字を配列に追加していく
  for i in 2..n do
    fb_list.push( fb_list[i-2] + fb_list[i-1] )
  end

  # 出来上がった配列を返す
  return fb_list
end
}}

これでループ版もほぼ無駄がなくなった．
元のものに比べて，ずいぶん速くなっている．

&ref(/materials/warning.png); n が大きくなった場合，どれくらい違うか予想せよ．

&br;
*** 各関数の実装: fibonacci 数列を配列で: 再帰版: 無駄 1 排除 [#sd8d9667]

さて，まずは無駄 1 を排除しよう．これは言い換えると，F_n を求める過程だけで全体が求まればよいので，例えば次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# Fibonacci 数列を配列で返す関数
def fibonacci(n)
  # まず，初期値の場合.
  if (n == 0) then
      return [0]
    elsif (n == 1) then
      return [0,1]
  end

  # 以下，n >= 2 の場合.
  # 再定義式では前二つに計算を下請けさせて，
  pp_list = fibonacci(n-2)
  p_list = fibonacci(n-1)

  # 答えを計算して配列に追加．
  result = pp_list[n-2] + p_list[n-1]
  fb_list = p_list.push(result)

  # 配列を返す
  return fb_list
end
}}

これで無駄 1 は排除できたことになる．
ただし，実行してみるとわかるがこのプログラムもやはり遅い．
というのも，無駄 2 が無駄 1 より大きいので，そちらの排除が出来ていないこのプログラムではまだまだだということなのである．


&br;
*** 各関数の実装: fibonacci 数列を配列で: 再帰版: 無駄 1,2 排除 [#dcb20fb8]
さて，無駄 2 の排除も考えよう．

ここで少し丁寧に考える必要がある．解説しよう．
まず，無駄 2 は「わかりにくい順番で」「何回も同じ数が」計算されることによって発生する．
計算の順番がわかりやすければそれに応じたプログラムをすれば無駄を省ける可能性があるが，この場合はそうもいかない．

そこで，こうした場合に計算の順番に依存しない対策として，
&br;
CENTER:&size(24){''重複する計算を省く方法の一つ:''};
CENTER:&size(24){'' ''};
CENTER:&size(24){''過去の計算結果を記録しておいて，''};
CENTER:&size(24){''計算をする前に計算済みでないかチェックする(メモ化もどき)''};
&br;

という手段がある．
&br;
&ref(/materials/OK.png); メモ化もどきは，再帰定義に限らずいつでも利用できる．計算に無駄があるという時は積極的に使ってみよう．
&br;

さて，この場合は具体的には，「外から手渡すメモ」を見つつ，結果がすでに書いてあればそれを返し，書いてなければ計算して記録し，そして結果を返すということになる．
今回のプログラムだと，例えば次のようになるだろう．ただし，外から手渡すメモについての記述も必要なので，全体を載せよう．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
# 配列を整理して表示する関数
def list_print(ary)
  for i in 0..(ary.size-1) do
    print("F_", i," = ",ary[i],"\n")
  end
end

# Fibonacci 数列についてのメモを返す関数
def fibonacci(n, m_list)

  # 既にメモに記録があるならば,そのままメモを返却.
  if (m_list[n] > -1) then
    return m_list
  end

  # 以下はメモに記録がなかった場合．

  # 再帰定義式では前二つに計算を下請けさせて.
  pp_n = fibonacci(n-2, m_list)[n-2]
  p_n = fibonacci(n-1, m_list)[n-1]

  # 答えを計算してメモに記録．
  m_list[n] = pp_n + p_n

  # メモを返却.
  return m_list
end

# 以下，プログラム本体

# 上限値をもらって…
n_upper = ARGV[0].to_i

# fibonacci 関数に渡すメモを作る(-1 で「未記録」を意味させてみる)．
memo = Array.new( n_upper+1 ){ -1 }
memo[0] = 0
memo[1] = 1 

# Fibonacci 数列を配列で求める．ほとんど未記入のメモを渡すと，記入されて返ってくる.
fb_list = fibonacci(n_upper, memo)

# 得られた結果を表示
list_print(fb_list)
}}
さて，これを動かしてみよう．
無駄が全く無くなったわけではないが，それでも，再帰定義であるにもかかわらず高速に動作することが分かるだろう．

&br;
* 文字列処理 [#g78b8481]

さて，今回は少し毛色を変えて文字列処理について学ぼう．
文字列とは文字の集合で，大抵のコンピュータ言語では配列のような扱いを受けるものと思って良い．

まずは以下に簡単な文法の表を示そう．

''文字列処理 簡易表''
| 操作 | 文法説明 | 例. s="aiueo kakiku keko" としている |h
| コピー | .dup をつけて代入する．&color(blue){いくつかのコンピュータ言語では文字列のコピーは特殊なので要注意．}; | a = s.dup とすると a は s と同じ中身をもつ文字列になる．&color(blue){けして a = s としないこと!}; |
| 長さ | .length をつける | s.length は 17 になる |
| 連結 | + を使う | s + "sa" は "aiueo kakiku kekosa" になる |
| 上書き連結 | << を使う | s << "sa" は&color(blue){ s が書き換えられて}; "aiueo kakiku kekosa" になる |
| 空白で分割 | .split() をつける. 結果は配列. | s.split() は ["aiueo", "kakiku", "keko"] になる |
| ある文字で分割 | .split("その文字") をつける．結果は配列． | s.split("i") は ["a", "ueo kak", "ku keko"] になる |
| n番目の文字を指定 (*1) | 配列同様，[n-1] をつける．&color(blue){この場合だけ結果が文字コードなので要注意};． | s[4] は 111 になる(111 は "o" の文字コード) |
| 文字コードを文字に直す | .chr をつける | s[4].chr は "o" になる |
| i文字目から j文字目までの部分文字列を指定 (*2) | [(i-1)..(j-1)] をつける. | s[0..4] は "aiueo" になる |
| i文字目から n個の文字の部分文字列を指定 (*3) | [(i_1),n] をつける | s[0,5] は "aiueo" になる |
| 指定した部分を置き換える. | 指定した部分 = "新しい文字列" とするだけでよい．指定した部分と新しい文字列の長さは違って良い. &color(blue){(*1,2,3)すべてで使える};. | s[4] = "z" とすると s は "aiuez kakiku keko" になる |
| 左検索 | .index("検索したい文字列") をつけると，左から探して初めて見つかった位置を返す |  s.index("u") は 2 になる |
| 右検索 | .rindex("検索したい文字列") をつけると，右から探して初めて見つかった位置を返す |  s.rindex("u") は 11 になる |
| 左検索 場所指定 | .index("検索したい文字列",文字位置) をつけると，指定した文字位置から始めて，左から探して初めて見つかった位置を返す |  s.index("u",2) は 2 になるが s.index("u",3) は 11 になる |
| 右検索 場所指定 | .rindex("検索したい文字列",文字位置) をつけると，指定した文字位置から始めて，右から探して初めて見つかった位置を返す |  s.rindex("u",11) は 11 になるが s.rindex("u",10) は 2 になる |
| 検索and置換(一箇所のみ) | .sub("置き換えたい古い文字列", "置き換えたい新しい文字列") をつける. &color(blue){最初に見つかった一箇所だけが置換される}; |  s.sub("a","A") とすると，s は "Aiueo kakiku keko" になる |
| 検索and置換(全部) | .gsub("置き換えたい古い文字列", "置き換えたい新しい文字列") をつける.  &color(blue){該当箇所全部が置換される}; |  s.gsub("a","A") とすると，s は "Aiueo kAkiku keko" になる |
| 最後に改行文字が入っていれば削除する | .chomp! をつける | (以前やったね)|
| 数字などを文字列に変換する | .to_s をつける |  1234.to_s は "1234" になる |

&br;
** 慣れてみよう: 3がつく数字… [#k2953cd7]
まずは簡単な例題で慣れよう．

&ref(/materials/notes.png); (以前とりあげた) 3の倍数 or 3がつく数についてのみ特殊な表示を行う関数を作り，それを使って起動時に与えた数字(30 ぐらいを想定)までその関数で表示させてみよう．
&br;
これは例えば
  ruby -w test.rb 30

として実行すると，
>  1
>  2
>  !!!!
>  4
>  5
>  !!!!
>  7
>  8
>  !!!!
>  10
>  11
>  !!!!
>  !!!!
>  14
>  !!!!
>  16
>  17
>  !!!!
>  19
>  20
>  !!!!
>  22
>  !!!!
>  !!!!
>  25
>  26
>  !!!!
>  28
>  29
>  !!!!

というような結果がでるようにせよ，ということになる．
&br;

&ref(/materials/warning.png); (上級者向け) ''index'' で検索文字列が見つかった場合は整数が答になり，見つからない場合は答えは nil という特殊なものになる．
そして，
&br;
CENTER:&size(24){''Ruby は nil と false を「偽」として扱い，''};
CENTER:&size(24){''それ以外は「真」として扱う''};
&br;

ので，''index'' 式をそのまま ''if'' 文などの判定部分に使うことができる．
感覚としては，''s = gets'' を ''while'' の条件に使うのによく似ている．


&br;
** 逆さの数字も素数か? [#bba9bd4d]

ひっくり返しても素数になるような素数を探すことを考える．

具体的には，例えば 113 は素数で，それを前後ひっくり返した数字 311 もやはり素数である．
(当然，二桁以上でないと意味がないね)

&ref(/materials/notes.png);  こうした数字(の組)を，11以上指定した数字以下の範囲から見つけて列挙するプログラムを作ろう．
&br;
具体的には，例えば
  ruby -w inv.rb 800
として実行すると，
>  (11, 11) are prime numbers.
>  (13, 31) are prime numbers.
>  (17, 71) are prime numbers.
>  (31, 13) are prime numbers.
>  (37, 73) are prime numbers.
>  (71, 17) are prime numbers.
>  (73, 37) are prime numbers.
>  (79, 97) are prime numbers.
>  (97, 79) are prime numbers.
>  (101, 101) are prime numbers.
>  (107, 701) are prime numbers.
>  (113, 311) are prime numbers.
>  (131, 131) are prime numbers.
>  (149, 941) are prime numbers.
>  (151, 151) are prime numbers.
>  (157, 751) are prime numbers.
>  (167, 761) are prime numbers.
>  (179, 971) are prime numbers.
>  (181, 181) are prime numbers.
>  (191, 191) are prime numbers.
>  (199, 991) are prime numbers.
>  (311, 113) are prime numbers.
>  (313, 313) are prime numbers.
>  (337, 733) are prime numbers.
>  (347, 743) are prime numbers.
>  (353, 353) are prime numbers.
>  (359, 953) are prime numbers.
>  (373, 373) are prime numbers.
>  (383, 383) are prime numbers.
>  (389, 983) are prime numbers.
>  (701, 107) are prime numbers.
>  (709, 907) are prime numbers.
>  (727, 727) are prime numbers.
>  (733, 337) are prime numbers.
>  (739, 937) are prime numbers.
>  (743, 347) are prime numbers.
>  (751, 157) are prime numbers.
>  (757, 757) are prime numbers.
>  (761, 167) are prime numbers.
>  (769, 967) are prime numbers.
>  (787, 787) are prime numbers.
>  (797, 797) are prime numbers.

というような出力をするプログラムを書こう，ということになる．
&br;

&ref(/materials/warning.png); 文字列の順序を逆さまにする命令もあるけれども，練習のために自分で書いてみよう．

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

以下，すこしややこしい? 問題なので練習も含め，いくつかに分けよう．

&br;
** 数あてゲームの準備 [#s3dfc007]

二つの「桁数が同じ」数桁の整数 n, m があるとしよう．
そして，n の 1の位の数を a_1, 10 の位の数を a_2, 100 の位の数を a_3, ... m の 1の位の数を b_1, 10 の位の数を b_2, 100 の位の数を b_3, ... とおく．
このとき，以下のような条件を満たすプログラムを書こう．

+ n, m はプログラムの起動時にパラメータとして与えられる．
+ X と Y という数を次のように定義する．
++ もしも a_i = b_i ならば X_i =  1, そうでなければ X_i = 0.
++ a_i = b_i ではないが，b_i と同じ a_j があるならば Y_i = 1, そうでなければ Y_i = 0.
++ もしも a_i = b_i ならば X_i =  1, そうでなければ X_i = 0.  X_i = 1 とした a_i, b_i は以降は調査対象としない．
++ さらに，a_i = b_i ではないが，b_i と同じ a_j があるならば Y_i = 1, そうでなければ Y_i = 0.  Y_i = 1 とした a_j, b_i は以降は調査対象としない．
++ X = X_i の合計，Y= Y_i の合計
+ n, m に対して，上の X, Y を計算し，出力する関数 xy(n,m) がプログラム中にある．
+ xy(n,m) を使って求めた X, Y を表示する．

これは例えば，
  ruby -w xy.rb 12345 54321

として実行すると，
>  X: 1, Y: 4

という出力を返すようにしろ，ということになる．
(俗に言う Hit and Blow と呼ばれる数あてゲームのルールである．よく知らない人はネットワークで調べてみよう)

&br;
** 数あてゲーム [#zc6b962a]

上の「準備」を利用して数あてゲームを作ろう．
上の n に相当する数をプログラムに乱数で作らせて，人間が入力した数に対して X, Y を出力することでヒントを与え，あてるまで入力を繰り返せるようにしよう．
このとき，条件は以下の通り．

+ 「何桁の n にするか」の桁数はプログラムの起動時にパラメータとして与えられる．
+ n は乱数で生成される．
+ 人間の入力は ''gets'' で受ける．
+ 入力を受けたら X, Y を出力し，再び入力を待つようにする．
+ n と全く同じ整数を人間が入力したら，その旨を表示して終了する．

&ref(/materials/warning.png); 起動時にパラメータを与えると，''gets'' はそれをファイル名だとみなしてそこから読み込もうとする． 今回はこれは困るので，単に ''gets'' とするのではなく，''$stdin.gets'' というコマンドとして使おう．
&br;

例えば，テストのために ''n'' を出力させるようにしておいてこのプログラムを
  ruby -w hb.rb 2
などとして起動すると，次のようにやりとりできることになる．

>  Ans: 29
>  m? : 21
>  X: 1, Y: 0
>  m? : 12
>  X: 0, Y: 1
>  m? : 19
>  X: 1, Y: 0
>  m? : 91
>  X: 0, Y: 1
>  m? : 92
>  X: 0, Y: 2
>  m? : 29
>  Conguratulaions!

&br;
** (上級者向け) 数あてゲーム: コンピュータが挑んでくる [#zc879f28]

上のゲームのルールで，人間が問題を出してコンピュータが数を当てようとしてくるというプログラムを作れるだろうか．


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

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

もちろん各自の

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

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

* about Icons, ClipArts [#c13e71ea]
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){{}}