アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月22日

Presentation on theme: "アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月22日"— Presentation transcript:

1 アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月22日
アルゴリズムとデータ構造 第1章　アルゴリズムと計算量 4月22日 情報知能学科 白井英俊

2 4月15日の課題 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 例: a = [1,2,3] とすると seiret3(a)は [1,2,3] を返し、 a = [20,10,30] とすると seiret3(a)は [10,20,30] を返し、 a = [33,22,11] とすると seiret3(a)は [11,22,33] を返す

3 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方： ３つの要素(仮にx,y,zとする)を小さいものから大きいものに並び替えるとすれば６通りの可能性がある( 3! = 6) (1) x ≦ y ≦ z (2) x ≦ z ≦ y (3) y ≦ x ≦ z (4) y ≦ z ≦ x (5) z ≦ x ≦ y (6) z ≦ y ≦ x

4 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方： まずxとｙの大きさを比べる… は x ≦ y の場合の可能性 (1) x ≦ y ≦ z (2) x ≦ z ≦ y (3) y ≦ x ≦ z (4) y ≦ z ≦ x (5) z ≦ x ≦ y (6) z ≦ y ≦ x

5 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方： まずxとｙの大きさを比べる… 次にx と zの大きさを比べる（x ≦ z の場合) (1) x ≦ y ≦ z (2) x ≦ z ≦ y (5) z ≦ x ≦ y 最後にy と zの大きさを比べて(1)か(2)が決まる

6 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 if (x <= y) if ( x <= z) if (y <= z) return [x,y,z] # x<= y<= z else return [x,z,y] # x<= z <= y end #if (y<=z) end # if (x<=z) end # if (x<=y) # xとｙの大きさを比べる… # 次にx と zの大きさを比べる # 最後にy と zの大きさを比べる これにならって他の場合を書きこむ！

7 4月15日の課題(4)続 ４．三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3 if (x <= y) # x ≦ y if ( x <= z) # x ≦ y , x ≦ z if (y <= z) # x ≦ y , x ≦ z, y≦z return [x,y,z] else # x ≦ y , x ≦ z, y > z return [x,z,y] end #if (y<=z) end # if (x<=z) end # if (x<=y) else # x ≦ y かつ x > z return [z,x,y]

8 4月15日の課題(4)続 ４．三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3 if (x <= y) # x ≦ y if ( x <= z) # x ≦ y , x ≦ z if (y <= z) # x ≦ y , x ≦ z, y ≦ z return [x,y,z] # x<= y<= z else return [x,z,y] # x<= z <= y end #if (y<=z) end # if (x<=z) else # x > y end # if (x<=y) else # x ≦ y , x > z return [z,x,y] この場合について考えみよう

9 4月15日の課題(4)続 これらのうちどの場合かを判別する コードをかけばよい！ (いろいろな方法があるけれど…)
「else」のところに処理が来るのは、 (1) x ≦ y ≦ z (2) x ≦ z ≦ y (3) y ≦ x ≦ z (4) y ≦ z ≦ x (5) z ≦ x ≦ y (6) z ≦ y ≦ x (なぜなら… (1),(2),(5)は処理済み (return)) これらのうちどの場合かを判別する コードをかけばよい！ (いろいろな方法があるけれど…)

10 4月15日の課題(4)続 (3) y ≦ x ≦ z (4) y ≦ z ≦ x (6) z ≦ y ≦ x
このように２つに分けるとすれば、 そのどちらであるかを見分ける条件文は？ 答: if (y <= z) 　　 # y ≦ z # (3)か(4)の場合 else 　　　　　　# (6)の場合 end 注意: (4)+(6)と(3) という分け方も可能 そのための条件式 はどうなるか？

11 4月15日の課題(4)続 (3) y ≦ x ≦ z (4) y ≦ z ≦ x (6) z ≦ y ≦ x さらに(3)と(4)を分ける:
if (y <= z) # y≦z if (x <= z)　　 # y≦z, x≦z return [y,x,z] else 　　 # y≦z, x > z return [y,z,x] end # if (x<=z) else # y > z 　　　　　　return [z,y,x] end # if (y<=z)

12 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 if (x <= y) # x ≦ y if ( x <= z) # x ≦ y, x ≦ z if (y <= z) # x ≦ y, x ≦ z, y≦z return [x,y,z] else # x ≦ y, x ≦ z, y>z return [x,z,y] end #if (y<=z) else # x ≦ y, x > z end # if (x<=z) elsif (y <= z) # y<x, y≦z if ( x <= z) # y<x, y≦z,x≦z return [y,x,z] else # y<x, y≦z, x > z return [y,z,x] end #if (x<=z) else # y < x , z < y return [z,y,x] end

13 ちょっと条件分岐について一言 これらは同じ処理
if (x <= y) 処理 else if (x <= z) return [y,x,z] return [y,z,x] end # if (x<=z) return [z,y,x] end # if (y<=z) end if (x <= y) 処理 elsif (x <= z) return [y,x,z] else return [y,z,x] end # if (x<=z) 　　　 return [z,y,x] end

14 練習問題（１） n個の実数x1, x2, …, xnが与えられて、その中の最小値を求める アルゴリズムを書く プログラムを書く
適当なデータを与えて、プログラムを実行してみる。そして最小値を返すことを確認する。

15 練習問題（２） n個の実数x1, x2, …, xnが与えられて、その中の２番目に大きな数を求める アルゴリズムを書く プログラムを書く
適当なデータを与えて、プログラムを実行してみる。そして2番目に大きな数を返すことを確認する。

16 課題（３と４は提出を求める宿題） プログラムを書くために、Rubyを復習しよう 次の問題にチャレンジしてみよう
　(1)最古のアルゴリズム(ユークリッドの互除法）をプログラム化する 　(2) ファイルから実数を読み込み、その中の最大値を答える（つまり、数がファイルに書いてある） 　(3) 最大値と最小値からなる配列を返す (4) 最大値と最小値からなる配列を答えるだけではなく、それらが何番目の要素であるかも答える 宿題の提出期限は4月28日（木曜日）まで。あて先はウェブページ参照

17 プログラム課題提出の注意 （これこれの問題を解く）「プログラムを書け」、もしくは「アルゴリズムを書け」という課題が多く出される
この時に求められているのは「プログラム（やアルゴリズム）」だけではないことに注意 要求事項がちゃんと満たされていることも示す（検証する）必要がある そのために、プログラムの中身、その実行例（複数個の例題）、実行結果の吟味（ちゃんと目的を果たしているかどうか）を示す

18 ユークリッドの互除法 入力：正整数p, q 出力：pと q の最大公約数 手続き：
　　1. q > p ならば、 p と q の値を入れ替える 　　2. r ← （p の q による剰余） 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p ← q, q ← r として、１へ。 p = 72, q = 30 として、試してみよう

19 基本的な用語の確認 aとｂの公約数：aもbも正整数であることが前提 aの約数とbの約数で共通する数のこと
　例： 30 の約数は 1, 2, 3, 5, 6, 10, 15, 30 72の約数は 1, 2, 3, 4, 6, 8, 9, 12, …, 36, 72 aとｂの最大公約数(GCD)：aとｂに共通する公約数のうち最大のもの 30と72の最大公約数(これをGCD(30,72)と書く）は…

20 ちょっと休憩

21 前回の練習:『最小値』を求める 問題：「n個の数x1, x2, …, xnが与えられたときに、その『最小値』を求める」アルゴリズムとプログラムを書く。 「最大値」の要素を求めるアルゴリズムがヒント

22 確認:『最大値』の要素を求める 最小値 min(n,x) def max(n,x) y = x[0] for i in 1..(n-1)
if (x[i] > y) y = x[i] end # if end # for return y end # def min(n,x) Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y; MIN 最小値 < <

23 練習問題２の解説 問題：実数x1, x2, …, xnが与えられて、これらを大きい順に並べた時に2番目に来る値を求めるアルゴリズムを作れ。
教科書の解答例１(p.183)によれば1行で書ける…しかし、これはこの課題の狙いではない 教科書の解答例２を見てみよう：

24 練習問題２の解説（続） 問題：実数x1, x2, …, xnが与えられて、これらを大きい順に並べた時に2番目に来る値を求める
教科書による解答：「最大値を求めるアルゴリズムの拡張」 入力： 自然数nと、n個の実数x1, x2, …, xn 出力： x1, x2, …, xnのうち2番目に大きな値 手続き： 1. y ← Max(x1, x2) ; z ← Min(x1, x2)　# 先頭２要素の大と小 2. for i ← 3 until n do 　　　　# 三番目の要素から調べる if (xi > z) then # 2番目の要素よりもxiが大きければ if (xi > y) then z ← y and y ← xi else z ← xi 　# 更新 3. return z

25 練習問題２の解説：プログラムへ このアルゴリズムも「関数」として記述する。 関数の名前をsecondとする。 したがって、概略は：
入力： 自然数nと、n個の実数x1, x2, …, xn 出力： x1, x2, …, xnのうち2番目に大きな値 手続き： 1. y ← Max(x1, x2) ; 　　 z ← Min(x1, x2) 2. for i ← 3 until n do if (xi > z) then if (xi > y) then z ← y and y ← xi else z ← xi 3. return z このアルゴリズムも「関数」として記述する。 関数の名前をsecondとする。 したがって、概略は： def second(n,x) … end というようになる。ここでnは自然数、xはn個の実数を要素とする配列

26 練習問題２解説：プログラム（続) 手続きの部分をプログラムにする。
1のステップは、二つの実数から最大値(max)と最小値(min)をそれぞれyとzに代入 よって if x[0] > x[1] y,z = x[0],x[1] else y,z = x[1],x[0] end とすれば目的は達成される 入力： 自然数nと、n個の実数x1, x2, …, xn 出力： x1, x2, …, xnのうち2番目に大きな値 手続き： 1. y ← Max(x1, x2) ; 　　 z ← Min(x1, x2) 2. for i ← 3 until n do if (xi > z) then if (xi > y) then z ← y and y ← xi else z ← xi 3. return z なぜx[0]とx[1]を比較しているのか？

27 練習問題２解説：プログラム（続) for i in 2..(n-1) if (x[i] > z) if (x[i] > y)
2のステップは、素直にかける： for i in 2..(n-1) if (x[i] > z) if (x[i] > y) z, y = y, x[i] else z = x[i] end # if end #for ３は簡単。 入力： 自然数nと、n個の実数x1, x2, …, xn 出力： x1, x2, …, xnのうち2番目に大きな値 手続き： 1. y ← Max(x1, x2) ; 　　 z ← Min(x1, x2) 2. for i ← 3 until n do if (xi > z) then if (xi > y) then z ← y and y ← xi else z ← xi 3. return z

28 練習問題２の解説：プログラム 以上、まとめて： 入力： 自然数nと、n個の実数x1, x2, …, xn
def second(n,x) if x[0] > x[1] y,z = x[0],x[1] else y,z = x[1],x[0] end # if for i in 2..(n-1) if (x[i] > z) if (x[i] > y) z, y = y, x[i] z = x[i] end #for return z end #def 入力： 自然数nと、n個の実数x1, x2, …, xn 出力： x1, x2, …, xnのうち2番目に大きな値 手続き： 1. y ← Max(x1, x2) ; 　　 z ← Min(x1, x2) 2. for i ← 3 until n do if (xi > z) then if (xi > y) then z ← y and y ← xi else z ← xi 3. return z

29 練習問題２のプログラムの検証 プログラムを書いただけで安心してはいけない。具体的なデータを与えて、検証してみよう。
その全体は以下のようになるだろう： def second(n,x) # 先ほどのsecond関数の定義 end 　 # 検証用のデータ x = [0.3, 0.5, 1.1, 0.8, 1.3, 0.4] print second(x.size,x)

30 練習問題３ 問題：実数x1, x2, …, xnが与えられて、これらを小さい順に並べた時に2番目に来る値を求めるプログラムを作れ。

31 ファイルからの読み込み 「ファイルから実数を読み込み、その中の最大値を答える」問題について
『最大値』アルゴリズムがあるのだから、この問題は、それを使って解くのが良い。 つまり、ファイルから「最大値を求める」対象の配列を作ればよい。そうすれば「最大値」アルゴリズムを使って答えが求められる。 したがって、考えるべきは、ファイルに書いてある数を読み込み、それから配列を作る方法

32 確認:『最大値』の要素を求める def max(n,x) y = x[0] for i in 1..(n-1)
if (x[i] > y) y = x[i] end # if end # for return y end # def Algorithm MAX(n, x1, x2, …, xn)： 入力（Input): 正整数 n と n 個の実 　　数x1, x2, …, xn 出力（Output): x1, x2, …, xnの中　 　　の最大値 手続き（Procedure): 　 1. y ← x1 ; 2. for i ← 2 until n do 　　　 if xi > y then y ← xi ; 3. return y;

33 問題：ファイルから数を読み込み… Ruby (に限らず多くのプログラミング言語）では、 ファイルから数を読み込むには
　1. ファイルを読み込み用に「開く」(openする、という） 　2. ファイルから一行ずつ「文字列」を取りだす 　3. 取り出した文字列を数に変換する 　4. 変換した数を集めて配列にする 書き込むために『開く」　のもある 実は、一字ずつ取り出すなど、いろいろできる とすればよい

34 覚えていますか？…Rubyの操作（１） １．ファイルを読み込み用に「開く」
　例： inFile = open(“realNumebrs.txt”,”r”) 　開いた結果を変数(ここでは inFile)に記憶するのを忘れないこと

35 覚えていますか？…Rubyの操作（２） 2. ファイルから一行ずつ「文字列」を取りだす 例1: 一回限りの取り出しなら
2.　ファイルから一行ずつ「文字列」を取りだす 　例1: 一回限りの取り出しなら ｙ = inFile.gets 　　　これを使ってまとめて取り出す方法： 　　　z = [ ] # 空っぽの配列を作っておく while (y = inFile.gets) z << y #　配列の後に付け足す z.push(y) end 　 例２： 別なやりかた： z = inFile.readlines

36 覚えていますか？…Rubyの操作（3） 3＆4. 取り出した文字列を数に変換し、配列に yが文字列とすると、 y.to_f
２のgetsの方式と組み合わせると、 ２のreadlinesの場合は…(自分で考えよう） to_f は「実数」にする to_i は「整数」にする z = [ ] # 空っぽの配列を作っておく while (y = inFile.gets) z << y.to_f #　配列の後ろに入れる end y.to_f >> z は駄目！

37 プログラムの完成 # ファイルにある数の最大値を求める def max(n,x) # 最大値を求めるプログラムをここに挿入 end
# ファイルを開いて数の配列を作る inFile = open(“realNumbers.txt”,”r”) x = [ ] # 空っぽの配列を用意 while (y = inFile.gets)　　# ファイルから一行ずつ読み込む x << y.to_f　　# 読み込んだ文字列を実数にしてｘに追加 end # while inFile.close # ファイルを『閉じる』 print max(x.size,x)

38 参考：ファイル名を引数とする関数に def max(n,x) # 最大値を求めるプログラムをここに挿入 end
# ファイルを引数とする関数にする def findMaxInFile(f) inFile = open(f, “r”) x = [ ] # 空っぽの配列を用意 while (y = inFile.gets)　　# ファイルから一行ずつ読み込む x << y.to_f　　# 読み込んだ文字列を実数にしてｘに追加 end # while inFile.close # ファイルを『閉じる』 print max(x.size,x) end # def # findMaxInFile(“realNumbers.txt”)

39 再度:アルゴリズムとは コンピュータ（や人間）が計算をするための手順 ユークリッドの互除法：最大公約数を求めるアルゴリズム
aとｂの公約数：aもbも整数であることが前提 　　aの約数とbの約数で共通する数のこと 　例： 30 の約数は 1, 2, 3, 5, 6, 10, 15, 30 72の約数は 1, 2, 3, 4, 6, 8, 9, 12, …, 36, 72 aとｂの最大公約数(GCD)：aとｂに共通する公約数のうち最大のもの 30と72の最大公約数(これをGCD(30,72)と書く）は 6

40 再度：アルゴリズムとは(続き) ユークリッドの互除法 （最古のアルゴリズム） 入力：正整数p, q 出力：pと q の最大公約数 手続き：
　　1. q > p ならば、 p と q の値を入れ替える 　　2. r ← p の q による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p ← q, q ← r として、１へ。 p = 72, q = 30 として、試してみよう pをqで割った余り

41 ユークリッドの互除法を試す プログラムを作る前に、自分でやってみることが大事 p = 72, q = 30 として ユークリッドの互除法
1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。 ステップ1: p > qなので次 ステップ２：　ｒ ←１２ ステップ３：　ｒ != 0 なので 　p←30, q←12 としてステップ１へ ステップ1: p > qなので次 ステップ２：　ｒ ←6 ステップ３：　ｒ != 0 なので p←12, q←6としてステップ１へ ステップ1： p > qなので次 ステップ２：　ｒ ← 0 ステップ３：　ｒ == 0 なので qの値が最大公約数

42 参考：ユークリッドの互除法の仕組み なぜ、ユークリッドの互除法で最大公約数が求まるか？
入力p，qは「正整数」なので必ず最大公約数がある（たとえそれが１であっても！） それを m で表すと、p = a*m, q = b*m と表される（しかも、aとｂは互いに素—最大公約数は１） p≧q　（つまりa ≧ b)とすれば、pとqの差 r = p – q = (a-b)*m であり、ｒとｑの最大公約数もm。しかも p > rのはず qとrの大きい方をp, 小さい方をqとして、上の方法を繰り返していけば、いつか必ずmが求まる（ｒ＝０になる）

43 アルゴリズムで大事なこと 入力が何か、出力（結果）が何かが明示されていること 計算の順番が明示されていること
計算の停止の条件が明示されていること 必ず有限時間内に停止し、答えを返すこと ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。

44 (復習） アルゴリズムからプログラムへ 本講義で扱う「アルゴリズム」はコンピュータの計算の手順のこと
したがって、アルゴリズムの書き方は、それを見て迷うことなくプログラムとして表現できるものが望ましい しかし、いきなりそのように書くのは難しいかもしれないので、「人間が読んで、計算の手順が明確な物」を、ここではアルゴリズムと考える 実際「プログラム」は、プログラム言語によって、いろいろな表現がある。教科書では、プログラミング言語ＣでもＲｕｂｙでも表現しやすいように、アルゴリズムが書かれている

45 (復習）アルゴリズムを関数として表現 関数：　入力を取り、それに基づいて一連の手続き（計算）を行い、その結果を出力する（返す）、というプログラムの単位

46 は仮引数という。『定義』のための仮のもの
(復習）関数について 関数定義の引数(xとｙ) は仮引数という。『定義』のための仮のもの 関数名を func とすると 　関数の定義の書き方： 　　　　　　def func(x,y) … プログラム(「コード」とも)… 　　　　　　　　　…どこかにreturn文が必要… end 関数の呼び出し： ans = func(3,5) 関数呼出の引数(3と5) は実引数。計算に用いられる実物。

47 (復習）関数の利点 一連の手続きに『名前』をつけ、入力と出力を明示することで、その手続きが何をしているかが明確になる
プログラムを関数に分けることで、そのプログラムの構造が明確になる 関数ごとにデバッグをすることで、誤りが発見しやすい。また変更も容易になる 同じような処理をする場合に、冗長性が減る 『再帰』は関数を使わないと書けない

48 ユークリッドの互除法のアルゴリズムをRubyのプログラムとして表す
確認： ステップ１の「pとqの値を入れ替える」はどうやるか？ ステップ２の剰余の求め方は？ ステップ３で、どうやって１に処理をもどすか？ ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。

49 Rubyのプログラムへ(1) ステップ１の「pとqの値を入れ替える」方法 普通の方法：第3の変数を持ち込む(例えばzとする）
　　　　 z = p; p = q; q = z Rubyならではの方法：多重代入（並行的な評価） 　　　　 p, q = q, p 試してみよう： p, q = 3, 5 p, q = q, p

50 Rubyのプログラムへ(2) 剰余の求め方 －－－ これ自体、関数？ def modulo(p,q) r = p/q
剰余の求め方　－－－　これ自体、関数？ 　 def modulo(p,q) r = p/q return p-r*q end 実は… p % q または　p.modulo(q) と書ける 試してみよう： 72 % 30 95.modulo(10)

51 アルゴリズムからRubyプログラムへ 関数の書き方 四則演算などの計算の書き方 + - * / % ** 変数への代入の書き方
+ - * / % ** 変数への代入の書き方 　　r = p % q 　（ 「←」は使わない） 条件文：判定式と、その結果に基づく処理の分岐 　 if (判定式) 　　　　判定式が成り立つ場合の処理 else 　　　　判定式が成り立たない場合の処理 　 end 判定式 ：等しい、大きい、小さい、以上、以下、等しくない、等 　　　 == > < >= 　<= !=

52 Rubyのプログラムへ(３) ステップ３で、どうやって１に処理をもどすか？ Cならば goto 文を使いたいところ
Rubyにはgoto文はない。だから、 　　繰り返しか再帰を用いる 再帰(recursion)とは、形の上では、ある関数の手続きにおいて、その関数自身の呼び出しを含む（行う）こと。再帰を使いこなすことは、アルゴリズムやプログラムの理解で重要

53 「階乗計算」を例に 階乗(factorial)計算: 正整数nの階乗を n! と書く。
　定義：　n! = n * (n-1) * (n-2) *　・・・ * 2 * 1 　特別に 0! = 1 。 プログラムによる実現法：　繰り返しを使う def factorial(n) 　 x = 1 for m in 1..n x = x * m end # for return x end # def

54 再帰？ 階乗を計算する関数を factorial(n) とすると、 factorial(n) = n!
= n * (n-1) * (n-2) *　・・・ * 2 * 1 （n-1)! = factorial(n-1)

55 再帰！ つまり factorial(n) = n * factorial(n-1) def factorial(n)
if (n >= 1) return n*factorial(n-1) else return 1 end # if end # def

56 ユークリッドの互除法のアルゴリズムをRubyのプログラムとして表す
確認： ステップ１の「pとqの値を入れ替える」はどうやるか？解決 ステップ２の剰余の求め方は？解決 ステップ３で、どうやって１に処理をもどすか？ ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。

57 ユークリッドの互除法を試す 繰り返しが起こっている p = 72, q = 30 として ユークリッドの互除法
1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。 ステップ1: p > qなので次 ステップ２：　ｒ ←１２ ステップ３：　ｒ != 0 なので 　p←30, q←12 としてステップ１へ ステップ1: p > qなので次 ステップ２：　ｒ ←6 ステップ３：　ｒ != 0 なので p←12, q←6としてステップ１へ ステップ1： p > qなので次 ステップ２：　ｒ ← 0 ステップ３：　ｒ == 0 なので qの値が最大公約数

58 再帰と繰り返し つまり、繰り返し部分において　q と r の最大公約数を求める、という問題を次に解こうとしているのだ（p,qの役割から）⇒再帰！ return gcd(q,r) 教訓：再帰は、繰り返しを実現する方法のひとつ。再帰の方が「繰り返し」文よりも分かりやすい場合がある 注意： 本講義では「繰り返し」文としてwhile文、for文、loop文、each文を主として考える 今作ろうとしている関数gcd をgcd定義の中で使う！

59 ユークリッドの互除法のアルゴリズムをRubyのプログラムとして表す
def gcd(p,q) if (q > p) p, q = q, p end # if r = p % q if (r == 0) return q else return gcd(q,r) end　# if end # def ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。

60 『繰り返し』文を用いたプログラム ユークリッドの互除法 考え方：1から3までが繰り返されて
いるのだから、全体を「whileやloop」という繰り返し文で括ってしまう。 def gcd(p,q) while (true) if (q > p) p, q = q, p end # if r = p % q if (r == 0) return q p, q = q, r end # while end # def ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。 これと再帰とでは、どちらが分かりやすいだろうか？

61 『繰り返し』文を用いたプログラム 別な考え方： (2)と(3)が「繰り返し」を構成していると考えれば、 (2)も含めて次のように書ける:
別な考え方：　(2)と(3)が「繰り返し」を構成していると考えれば、 (2)も含めて次のように書ける: #(2)と(3)の前半を 　while ((r = p % q) != 0) 　　　　　p = q 　 q = r 　end 　return q ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。 r == 0 ならばwhile終了

62 ユークリッドの互除法のアルゴリズムをRubyのプログラムとして表す
繰り返し文を用いると… def gcd(p,q) if (q > p) p, q = q, p end # if while ((r = p % q) != 0) p = q q = r end # while return q end # def ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を入れ替える 2. r ← p の q　による剰余 3. r = 0 ならば、q が最大公約数（終了） さもなくば、 p← q, q ← r として、１へ。 注意：p、qが正整数なので、qによるpの剰余(r)はqよりも小さい

63 おまけ（基礎的な用語） aとbの公倍数：aとbを約数に持つ数 注意：aとbは正の整数であることが前提
例： 8と12の公倍数は、24, 48, 72, … aとｂの最小公倍数(LCM) aとbの公倍数のうちで最小の正数 aとbのLCM = a * b / GCD(a, b) aとbが互いに素：整数aとbの最大公約数が1 素数：約数が１とそれ自身だけの1より大きな正整数 　注意：1は素数とは言わない

64 ユークリッドの互除法のプログラム ここまでで質問は？
『再帰』を使うほうが、「繰り返し」文を使うほうよりも分かりやすかったのではないでしょうか？ だから、再帰に慣れましょう！ 分かりにくかったとしても、再帰は必要！

65 Rubyの「数」について 今まで「実数」と「整数」と書きましたが、「実数」は、正式には「浮動小数点数」(Float)といいます。
Rubyでは、かなりの大きさの整数を表現できます(これも正確に言えば、FixnumとBignumの二種類があって、Bignumのおかげで、かなり大きい整数を表現できるのです） 試してみよう： 3.class class 3.14.class

66 Rubyの「数」について(続き) 問題: 1を３で割るといくらでしょう？
答え：　人間が答えるか、計算機が答えるかで、答えは変わります。また、計算機であっても、どのように計算させるかで、答えが変わります。

67 Rubyの「数」について(続き) 試してみよう： 1 / 3 1.0 / 3 1 / 3.0 1.0 / 3.0 1 / 3.to_f
　1 / 3 1.0 / 3 1 / 3.0 1.0 / 3.0 1 / 3.to_f 1 / 3.0.to_i

68 Rubyの「数」について(続き) 浮動小数点数では、表現できる数の「精度」に限界があります（これはRubyに限ったことではありません）
試しに次をやってみてください： 　　 a = 1.0/3.0 print a,”\n” printf(“%30.28f\n”,a) b = a – # 3が18個 　　 printf(“%30.28f\n”,b) この結果については、講義で説明します

69 数の表現について（補足） print 0.0000000000004 (小数点以下0が12個） をしてみると、どのような表示になるでしょう？
　　　(小数点以下0が12個） をしてみると、どのような表示になるでしょう？ これについても、講義で

70 他の問題について… (3) 最大値と最小値を答える 方針：maxにならって min という関数を用意する
　　もしくは、max関数を作り変えて、max と min 同時に求めるようにする（どちらが良いか？） (4) 最大値と最小値を答えるだけではなく、それらが何番目の要素であるかも答える 　　方針：『何番目の要素だったか』を記憶する変数を別に用意し、最大値や最小値が変わるたびに、その番号を記憶する

71 再帰の問題（１）：チャレンジ 『再帰』の仕組みを理解し、「再帰関数」を作れるようにしておこう。（以下は『配列』の扱いが難しいので、次回以降の宿題…） １．配列の深さを求めるアルゴリズムとプログラム 　　配列の深さ(depth)の定義： 　　　　　要素に配列がなければ、１ 　　　　　そうでなければ、要素の「配列の深さ」の最大値＋１（「配列」でない要素の『深さ』を０とすると考えやすい） 　　注意：このように定義自体が「再帰的」になっている場合、　 　　「再帰関数」を考えるのはとっても自然でやりやすい 　　例： [ 3, 5, 1] の深さは　１ 　　　　　[ 2, [3,5,1], 4]の深さは　2 [5, [ 2, [3,5,1], 4], [1,2,3] , [7] ]の深さは　2　　

72 再帰の問題（２）：チャレンジ １か２については考えてみてください。
２．配列を入力とし、配列に埋め込まれた要素すべてからなる配列を返すアルゴリズムとプログラム（関数名を flat とする） 　注意：関数が帰す結果において、要素の順番も、要素の重複　　　も問わないことにする 　　例： flat([ 3, 5, 1] ) ⇒ [3,5,1] ([1,3,5]など他の並びも可） 　　　　 flat([ 2, [3,5,1], 4]) ⇒ [2, 3,5,1, 4] 　（他の並びも可） flat([5, [ 2, [3,5,1], 4], [1,2,3] , [7] ]) 　　　　　　　　⇒[5,2,3,5,1,4,1,2,3,7] (注意：要素の重複も可） １か２については考えてみてください。

73 計算量とオーダ(予習） アルゴリズムの「理論的な」計算量は、処理する計算機の性能と、アルゴリズムの手続きを解析することにより、入力の大きさをnとすると、例えば、3n**2+8*n+6のように求めることができる。これを、できるだけ簡単なnの関数で表したものがオーダ。 元の式からオーダを求めるには、 定数は無視する(元の式がnを含まない場合は1とする)、 nが無限大に近付くときに最も大きくなるnの項を取り出す 。 例えば、3n**2+8*n+6のオーダはn**2。これを O(n**2) と表す

74 計算量とオーダ(続) オーダを求めるには、 log(n), n, n*log(n), n**2, n**2*log(n), n**3,
　　2**n, n!, n**n 　のような関数が、nの値の変化に対して(特にnが大きな値のときに）どのように大きくなるかを認識する必要がある。 それを図示するソフトウェア の一つが GnuPlot。 対数 の知識も不可欠。

75 Gnuplotの使用例 log(x), (log(x))**2, x, x log(x), x**2の比較

76 Gnuplotの使用例 log(x), x**0.5, x, x**2, x**3の比較

77 Gnuplotの使用例 x, x**2, x**3, 2**x, x!, x**xの比較

78 プログラムの計算量 以下のような繰り返しでは、計算量は繰り返しの回数に比例 例： for i in 1..n # n回繰り返す⇒ O(n)
print i, i**2, i**3,”\n” end #for 以下のような二重の繰り返しは、繰返し回数の積⇒　O(n*m) 例： for i in 1..n # n回繰り返す for j in 1..m 　　# m回繰り返す print a[i,j]*a[j,i],”\n” end #for j end #for i

79 プログラムの計算量(続) 関数を用いている場合 関数の性質によって計算量は異なる 入力の大きさを n とすると一般に：
　関数の性質によって計算量は異なる 入力の大きさを n とすると一般に： 　　　ソート(並び替え） ⇒ O(n*log(n)) 　　　配列への操作（代入、アクセス）　⇒　O(1) 配列への要素の追加　⇒ O(n) 再帰関数の場合はいろいろ．．．第5章参照