アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月22日 情報知能学科 白井英俊 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] を返す 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月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 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身 を、小さいものから大 きいものになるよう並び かえた配列を返す関数seiret3の定義 考え方： まずxとｙの大きさを比べる… 次にx と zの大きさを比べる（x ≦ z の場合) (1) x ≦ y ≦ z (2) x ≦ z ≦ y 最後にy と zの大きさを比べて(1)か(2)が決まる (5) z ≦ x ≦ y 4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身 を、小さいものから大 きいものになるよう並び かえた配列を返す関数seiret3の定義 if (x <= y) # xとｙの大きさを比べる… if ( x <= z) # 次にx と zの大きさを比べる if (y <= 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) end # if (x<=y) 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) else # x ≦ y かつ x > z return [z,x,y] end # if (x<=z) end # if (x<=y) 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) else # x ≦ y , x > z return [z,x,y] end # if (x<=z) else #x>y この場合について考えみよう end # if (x<=y) 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)) これらのうちどの場合かを判別する コードをかけばよい！ (いろいろな方法があるけれど…) 9 4月15日の課題(4)続 (3) y ≦ x ≦ z (4) y ≦ z ≦ x (6) z ≦ y ≦ x このように２つに分けるとすれば、 そのどちらであるかを見分ける条件文は？ 答: if (y <= z) #y≦z # (3)か(4)の場合 注意: (4)+(6)と(3) という分け方も可能 else そのための条件式 # (6)の場合 はどうなるか？ 10 end 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) 11 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] elsif (y <= z) # y<x, y≦z else # x ≦ y, x ≦ z, y>z if ( x <= z) # y<x, y≦z,x≦z return [x,z,y] return [y,x,z] end #if (y<=z) else # y<x, y≦z, x > z else # x ≦ y, x > z return [y,z,x] return [x,z,y] end #if (x<=z) end # if (x<=z) else # y < x , z < y return [z,y,x] end ちょっと条件分岐について一言 これらは同じ処理 if (x <= y) 処理 else if (x <= z) return [y,x,z] else return [y,z,x] end # if (x<=z) else 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) else return [z,y,x] end 13 練習問題（１） • n個の実数x1, x2, …, xnが与えられて、その中 の最小値を求める (1)アルゴリズムを書く (2)プログラムを書く (3)適当なデータを与えて、プログラムを実行して みる。そして最小値を返すことを確認する。 14 練習問題（２） • n個の実数x1, x2, …, xnが与えられて、その中 の２番目に大きな数を求める (1)アルゴリズムを書く (2)プログラムを書く (3)適当なデータを与えて、プログラムを実行して みる。そして2番目に大きな数を返すことを確 認する。 15 課題（３と４は提出を求める宿題） • プログラムを書くために、Rubyを復習しよう • 次の問題にチャレンジしてみよう (1)最古のアルゴリズム(ユークリッドの互除法）をプ ログラム化する (2) ファイルから実数を読み込み、その中の最大値 を答える（つまり、数がファイルに書いてある） (3) 最大値と最小値からなる配列を返す (4) 最大値と最小値からなる配列を答えるだけでは なく、それらが何番目の要素であるかも答える 宿題の提出期限は4月28日（木曜日）まで。あて先はウェブページ 16 参照 プログラム課題提出の注意 • （これこれの問題を解く）「プログラムを書け」、もしく は「アルゴリズムを書け」という課題が多く出される • この時に求められているのは「プログラム（やアルゴ リズム）」だけではないことに注意 • 要求事項がちゃんと満たされていることも示す（検 証する）必要がある • そのために、プログラムの中身、その実行例（複数 個の例題）、実行結果の吟味（ちゃんと目的を果たし ているかどうか）を示す 17 ユークリッドの互除法 入力：正整数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 として、試してみよう 18 基本的な用語の確認 整数ｘが整数aの約数 ⇔ aがｘで割り切れる • 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)と書く） は… 19 ちょっと休憩 20 前回の練習:『最小値』を求める 問題：「n個の数x1, x2, …, xnが与えられたときに、その 『最小値』を求める」アルゴリズムとプログラムを書く。 「最大値」の要素を求めるアルゴリズムがヒント 最小値 確認:『最大値』の要素を求める 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 Algorithm MIN 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; 練習問題２の解説 • 問題：実数x1, x2, …, xnが与えられて、これら を大きい順に並べた時に2番目に来る値を求 めるアルゴリズムを作れ。 • 注意：「実数x1, x2, …, xnを大きい順に並べ ろ」とは書いていない。出力すべき値の記述 でしかないことに注意。 • 教科書の解答例１(p.183)によれば1行で書け る…しかし、これはこの課題の狙いではない • 教科書の解答例２を見てみよう： 練習問題２の解説（続） • 問題：実数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 練習問題２の解説：プログラムへ このアルゴリズムも「関数」 として記述する。 関数の名前をsecondとする。 したがって、概略は： def second(n,x) … end というようになる。ここでnは 自然数、xはn個の実数を要素 とする配列 入力： 自然数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 練習問題２解説：プログラム（続) 入力： 自然数nと、n個の実数x1, 手続きの部分をプログラムに x2, …, xn する。 出力： x1, x2, …, xnのうち2番目に 1のステップは、二つの実数 大きな値 から最大値(max)と最小値 手続き： (min)をそれぞれyとzに代入 1. y ← Max(x1, x2) ; なぜx[0]とx[1]を比 よって z ← Min(x1, x2) 較しているのか？ if x[0] > x[1] 2. for i ← 3 until n do y,z = x[0],x[1] if (xi > z) then else if (xi > y) then z ← y and y,z = x[1],x[0] y ← xi else z ← xi end 3. return z とすれば目的は達成される 練習問題２解説：プログラム（続) 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 # 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 練習問題２の解説：プログラム 以上、まとめて： 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] else z = x[i] end # if end # if 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 練習問題２のプログラムの検証 • プログラムを書いただけで安心してはいけな い。具体的なデータを与えて、検証してみよう。 その全体は以下のようになるだろう： def second(n,x) # 先ほどのsecond関数の定義 end # 検証用のデータ x = [0.3, 0.5, 1.1, 0.8, 1.3, 0.4] print second(x.size,x) 練習問題３ 問題：実数x1, x2, …, xnが与えられて、これらを 小さい順に並べた時に2番目に来る値を求め るプログラムを作れ。 30 ファイルからの読み込み • 「ファイルから実数を読み込み、その中の最大値を 答える」問題について • 『最大値』アルゴリズムがあるのだから、この問題は、 それを使って解くのが良い。 • つまり、ファイルから「最大値を求める」対象の配列 を作ればよい。そうすれば「最大値」アルゴリズムを 使って答えが求められる。 • したがって、考えるべきは、ファイルに書いてある数 を読み込み、それから配列を作る方法 確認:『最大値』の要素を求める 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; 問題：ファイルから数を読み込み… Ruby (に限らず多くのプログラミング言語）では、 ファイルから数を読み込むには 書き込むために『開く」 のもある 1. ファイルを読み込み用に「開く」(openする、 実は、一字ずつ取り出すなど、い という） ろいろできる 2. ファイルから一行ずつ「文字列」を取りだす 3. 取り出した文字列を数に変換する 4. 変換した数を集めて配列にする とすればよい 覚えていますか？…Rubyの操作（１） １．ファイルを読み込み用に「開く」 例： inFile = open(“realNumebrs.txt”,”r”) 開いた結果を変数(ここでは inFile)に記憶するのを 忘れないこと 覚えていますか？…Rubyの操作（２） 2. ファイルから一行ずつ「文字列」を取りだす 例1: 一回限りの取り出しなら ｙ = inFile.gets これを使ってまとめて取り出す方法： z = [ ] # 空っぽの配列を作っておく while (y = inFile.gets) z << y # 配列の後に付け足す z.push(y) end 例２： 別なやりかた： z = inFile.readlines 覚えていますか？…Rubyの操作（3） 3＆4. 取り出した文字列を数に変換し、配列に yが文字列とすると、 y.to_f to_f は「実数」にする ２のgetsの方式と組み合わせると、to_i は「整数」にする z = [ ] # 空っぽの配列を作っておく while (y = inFile.gets) z << y.to_f # 配列の後ろに 入れる end y.to_f >> z は駄目！ ２のreadlinesの場合は…(自分で考えよう） プログラムの完成 # ファイルにある数の最大値を求める 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) 参考：ファイル名を引数とする関数に 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”) 再度:アルゴリズムとは • コンピュータ（や人間）が計算をするための手順 • ユークリッドの互除法：最大公約数を求めるアルゴリ ズム • 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 39 再度：アルゴリズムとは(続き) • ユークリッドの互除法 （最古のアルゴリズム） 入力：正整数p, q 出力：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 として、試してみよう 40 ユークリッドの互除法を試す • プログラムを作る前に、自分でやってみることが大事 p = 72, q = 30 として ステップ1: p > qなので次 ステップ２： ｒ ←１２ ステップ３： ｒ != 0 なので p←30, q←12 としてステップ１へ ステップ1: p > qなので次 ステップ２： ｒ ←6 ステップ３： ｒ != 0 なので p←12, q←6としてステップ１へ ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を 入れ替える 2. r ← p の q による剰余 3. r = 0 ならば、q が最大公約 数（終了） さもなくば、 p← q, q ← r とし て、１へ。 ステップ1： p > qなので次 ステップ２： ｒ ← 0 ステップ３： ｒ == 0 なので qの値が最大公約数 41 参考：ユークリッドの互除法の仕組み なぜ、ユークリッドの互除法で最大公約数が求まるか？ • 入力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が求まる（ｒ＝０になる） 42 アルゴリズムで大事なこと • 入力が何か、出力（結果 ）が何かが明示されてい ること • 計算の順番が明示され ていること • 計算の停止の条件が明 示されていること • 必ず有限時間内に停止 し、答えを返すこと ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を 入れ替える 2. r ← p の q による剰余 3. r = 0 ならば、q が最大公約 数（終了） さもなくば、 p← q, q ← r とし て、１へ。 43 (復習） アルゴリズムからプログラムへ • 本講義で扱う「アルゴリズム」はコンピュータの計算 の手順のこと • したがって、アルゴリズムの書き方は、それを見て 迷うことなくプログラムとして表現できるものが望ま しい • しかし、いきなりそのように書くのは難しいかもしれ ないので、「人間が読んで、計算の手順が明確な物 」を、ここではアルゴリズムと考える • 実際「プログラム」は、プログラム言語によって、いろ いろな表現がある。教科書では、プログラミング言 語ＣでもＲｕｂｙでも表現しやすいように、アルゴリズ ムが書かれている 44 (復習）アルゴリズムを関数として表現 関数： 入力を取り、それに基づいて一連の手続き （計算）を行い、その結果を出力する（返す）、という プログラムの単位 45 (復習）関数について 関数定義の引数(xとｙ) は仮引数という。『定義』 のための仮のもの • 関数名を func とすると 関数の定義の書き方： def func(x,y) … プログラム(「コード」とも)… …どこかにreturn文が必要… end 関数呼出の引数(3と5) は実引数。計算に用い 関数の呼び出し： られる実物。 ans = func(3,5) 46 (復習）関数の利点 • 一連の手続きに『名前』をつけ、入力と出力を 明示することで、その手続きが何をしているか が明確になる • プログラムを関数に分けることで、そのプログ ラムの構造が明確になる • 関数ごとにデバッグをすることで、誤りが発見 しやすい。また変更も容易になる • 同じような処理をする場合に、冗長性が減る • 『再帰』は関数を使わないと書けない 47 ユークリッドの互除法のアルゴリズム をRubyのプログラムとして表す 確認： 1. ステップ１の「pとqの値 を入れ替える」はどうや るか？ 2. ステップ２の剰余の求 め方は？ 3. ステップ３で、どうやっ て１に処理をもどす か？ ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を 入れ替える 2. r ← p の q による剰余 3. r = 0 ならば、q が最大公約 数（終了） さもなくば、 p← q, q ← r とし て、１へ。 48 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 49 Rubyのプログラムへ(2) • 剰余の求め方 －－－ これ自体、関数？ def modulo(p,q) r = p/q return p-r*q end 実は… p % q または p.modulo(q) と書ける 試してみよう： 72 % 30 95.modulo(10) 50 アルゴリズムからRubyプログラムへ • 関数の書き方 • 四則演算などの計算の書き方 + - * / % ** • 変数への代入の書き方 r = p % q （ 「←」は使わない） • 条件文：判定式と、その結果に基づく処理の分岐 if (判定式) 判定式が成り立つ場合の処理 else 判定式が成り立たない場合の処理 end • 判定式 ：等しい、大きい、小さい、以上、以下、等しくない、等 == > < >= <= != 51 Rubyのプログラムへ(３) • ステップ３で、どうやって１に処理をもどす か？ Cならば goto 文を使いたいところ Rubyにはgoto文はない。だから、 繰り返しか再帰を用いる 再帰(recursion)とは、形の上では、ある関数の手続きにおいて、 その関数自身の呼び出しを含む（行う）こと。再帰を使いこなす ことは、アルゴリズムやプログラムの理解で重要 52 「階乗計算」を例に • 階乗(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 53 再帰？ • 階乗を計算する関数を factorial(n) とすると、 factorial(n) = n! = n * (n-1) * (n-2) * ・・・ * 2 * 1 （n-1)! = factorial(n-1) 54 再帰！ つまり factorial(n) = n * factorial(n-1) def factorial(n) if (n >= 1) return n*factorial(n-1) else return 1 end # if end # def 55 ユークリッドの互除法のアルゴリズム をRubyのプログラムとして表す 確認： 1. ステップ１の「pとqの値 を入れ替える」はどうや るか？解決 2. ステップ２の剰余の求 め方は？解決 3. ステップ３で、どうやっ て１に処理をもどす か？ ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を 入れ替える 2. r ← p の q による剰余 3. r = 0 ならば、q が最大公約 数（終了） さもなくば、 p← q, q ← r とし て、１へ。 56 ユークリッドの互除法を試す • 繰り返しが起こっている p = 72, q = 30 として ステップ1: p > qなので次 ステップ２： ｒ ←１２ ステップ３： ｒ != 0 なので p←30, q←12 としてステップ１へ ステップ1: p > qなので次 ステップ２： ｒ ←6 ステップ３： ｒ != 0 なので p←12, q←6としてステップ１へ ユークリッドの互除法 pとqは正整数とする 1. q > p ならば、 p と q の値を 入れ替える 2. r ← p の q による剰余 3. r = 0 ならば、q が最大公約 数（終了） さもなくば、 p← q, q ← r とし て、１へ。 ステップ1： p > qなので次 ステップ２： ｒ ← 0 ステップ３： ｒ == 0 なので qの値が最大公約数 57 再帰と繰り返し つまり、繰り返し部分において q と r の最大公 約数を求める、という問題を次に解こうとして いるのだ（p,qの役割から）⇒再帰！ return gcd(q,r) 今作ろうとしている関数gcd をgcd定義の中で使う！ 教訓：再帰は、繰り返しを実現する方法のひと つ。再帰の方が「繰り返し」文よりも分かりや すい場合がある 注意： 本講義では「繰り返し」文としてwhile文、for文、 loop文、each文を主として考える 58 ユークリッドの互除法のアルゴリズム を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 とし て、１へ。 59 『繰り返し』文を用いたプログラム 考え方：1から3までが繰り返されて いるのだから、全体を「whileやloop」という 繰り返し文で括ってしまう。 ユークリッドの互除法 def gcd(p,q) while (true) pとqは正整数とする if (q > p) 1. q > p ならば、 p と q の値を 入れ替える p, q = q, p 2. r ← p の q による剰余 end # if 3. r = 0 ならば、q が最大公約 r=p%q 数（終了） if (r == 0) さもなくば、 p← q, q ← r とし return q て、１へ。 end # if p, q = q, r end # while end # def これと再帰とでは、どちらが分かりやすいだろうか？ 60 『繰り返し』文を用いたプログラム 別な考え方： (2)と(3)が「繰り返し」を構成して いると考えれば、 (2)も含めて次のように書ける: ユークリッドの互除法 #(2)と(3)の前半を while ((r = p % q) != 0) pとqは正整数とする 1. q > p ならば、 p と q の値を p=q 入れ替える 2. r ← p の q による剰余 q=r 3. r = 0 ならば、q が最大公約 r == 0 ならばwhile終了 数（終了） end さもなくば、 p← q, q ← r とし て、１へ。 return q 61 ユークリッドの互除法のアルゴリズム を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よりも小さい 62 おまけ（基礎的な用語） • 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は素数とは言わない 63 ユークリッドの互除法のプログラム • ここまでで質問は？ • 『再帰』を使うほうが、「繰り返し」文を使うほう よりも分かりやすかったのではないでしょう か？ • だから、再帰に慣れましょう！ 分かりにくかったとしても、再帰は必要！ 64 Rubyの「数」について • 今まで「実数」と「整数」と書きましたが、「実数」は、 正式には「浮動小数点数」(Float)といいます。 • Rubyでは、かなりの大きさの整数を表現できます (これも正確に言えば、FixnumとBignumの二種類 があって、Bignumのおかげで、かなり大きい整数を 表現できるのです） 試してみよう： 3.class 33333333333333333333333.class 3.14.class 65 Rubyの「数」について(続き) • 問題: 1を３で割るといくらでしょう？ 答え： 人間が答えるか、計算機が答えるかで、 答えは変わります。また、計算機であっても、ど のように計算させるかで、答えが変わります。 66 Rubyの「数」について(続き) 試してみよう： 1/3 1.0 / 3 1 / 3.0 1.0 / 3.0 1 / 3.to_f 1 / 3.0.to_i 67 Rubyの「数」について(続き) • 浮動小数点数では、表現できる数の「精度」に限界 があります（これはRubyに限ったことではありませ ん） • 試しに次をやってみてください： a = 1.0/3.0 print a,”\n” printf(“%30.28f\n”,a) b = a – 0.333333333333333 # 3が18個 printf(“%30.28f\n”,b) この結果については、講義で説明します 68 数の表現について（補足） print 0.0000000000004 (小数点以下0が12個） をしてみると、どのような表示になるでしょう？ これについても、講義で 69 他の問題について… (3) 最大値と最小値を答える 方針：maxにならって min という関数を用意する もしくは、max関数を作り変えて、max と min 同時 に求めるようにする（どちらが良いか？） (4) 最大値と最小値を答えるだけではなく、それ らが何番目の要素であるかも答える 方針：『何番目の要素だったか』を記憶する変数を 別に用意し、最大値や最小値が変わるたびに、その 番号を記憶する 70 再帰の問題（１）：チャレンジ 『再帰』の仕組みを理解し、「再帰関数」を作れるようにしておこ う。（以下は『配列』の扱いが難しいので、次回以降の宿題…） １．配列の深さを求めるアルゴリズムとプログラム 配列の深さ(depth)の定義： 要素に配列がなければ、１ そうでなければ、要素の「配列の深さ」の最大値＋１ （「配列」でない要素の『深さ』を０とすると考えやすい） 注意：このように定義自体が「再帰的」になっている場合、 「再帰関数」を考えるのはとっても自然でやりやすい 例： [ 3, 5, 1] の深さは １ [ 2, [3,5,1], 4]の深さは 2 [5, [ 2, [3,5,1], 4], [1,2,3] , [7] ]の深さは 2 71 再帰の問題（２）：チャレンジ ２．配列を入力とし、配列に埋め込まれた要素すべてからなる 配列を返すアルゴリズムとプログラム（関数名を 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] (注意：要素の重複も可） １か２については考えてみてください。 72 計算量とオーダ(予習） • アルゴリズムの「理論的な」計算量は、処理する計算 機の性能と、アルゴリズムの手続きを解析することによ り、入力の大きさをnとすると、例えば、3n**2+8*n+6 のように求めることができる。これを、できるだけ簡単 なnの関数で表したものがオーダ。 • 元の式からオーダを求めるには、 1. 定数は無視する(元の式がnを含まない場合は1とす る)、 2. nが無限大に近付くときに最も大きくなるnの項を取り 出す 。 例えば、3n**2+8*n+6のオーダはn**2。これを O(n**2) と表す 73 計算量とオーダ(続) • オーダを求めるには、 log(n), n, n*log(n), n**2, n**2*log(n), n**3, 2**n, n!, n**n のような関数が、nの値の変化に対して(特にnが大き な値のときに）どのように大きくなるかを認識する必 要がある。 • それを図示するソフトウェア の一つが GnuPlot。 • 対数 の知識も不可欠。 74 Gnuplotの使用例 log(x), (log(x))**2, x, x log(x), x**2の比較 1e+008 x log(x) x*log(x) x**2 (log(x))**2 1e+007 1e+006 100000 10000 1000 100 10 1 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 1000075 Gnuplotの使用例 log(x), x**0.5, x, x**2, x**3の比較 1e+009 x**0.5 x 1e+008 log(x) x**2 x**3 1e+007 1e+006 100000 10000 1000 100 10 1 100 200 300 400 500 600 700 800 900 1000 76 Gnuplotの使用例 x, x**2, x**3, 2**x, x!, x**xの比較 1e+090 x x**x 1e+080 fact(x) 2**x x**3 1e+070 1e+060 1e+050 1e+040 1e+030 1e+020 1e+010 1 5 10 15 20 25 30 35 40 45 50 77 プログラムの計算量 以下のような繰り返しでは、計算量は繰り返しの回数に比例 例： 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 78 プログラムの計算量(続) • 関数を用いている場合 関数の性質によって計算量は異なる 入力の大きさを n とすると一般に： ソート(並び替え） ⇒ O(n*log(n)) 配列への操作（代入、アクセス） ⇒ O(1) 配列への要素の追加 ⇒ O(n) • 再帰関数の場合はいろいろ．．．第5章参照 79
© Copyright 2024 ExpyDoc
