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

Slides:



Advertisements
Similar presentations
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第3回 配列(1) 情報・知能工学系 山本一公
Advertisements

プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
プログラムのパタン演習 解説.
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第4回 配列(2) 情報・知能工学系 山本一公
プログラミング基礎I(再) 山元進.
プログラミング言語としてのR 情報知能学科 白井 英俊.
情報基礎演習B 後半第5回 担当 岩村 TA 谷本君.
ファーストイヤー・セミナーⅡ 第8回 データの入力.
配列(2) 第10回[平成15年6月26日(木)]:PN03-10.ppt 今日の内容 1 素数を求める(教科書の例):復習
数値計算及び実習 第3回 プログラミングの基礎(1).
基礎プログラミングおよび演習 第9回
アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月26日
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング演習(2組) 第12回
C言語 配列 2016年 吉田研究室.
情報科学1(G1) 2016年度.
第6章 2重ループ&配列 2重ループと配列をやります.
プログラミング入門2 第2回 複合文、繰り返し 情報工学科 篠埜 功.
配列(1) 第9回目 [6月15日、H.16(‘04)] 本日のメニュー 1)前回の課題について 2)前回の宿題について 3)配列 4)課題
第7回 条件による繰り返し.
岩村雅一 知能情報工学演習I 第8回(後半第2回) 岩村雅一
情報処理3 第5回目講義         担当 鶴貝 達政 11/8/2018.
C言語講座 第3回 ポインタ、配列.
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
プログラミング2 関数
繰り返し計算 while文, for文.
関数と配列とポインタ 1次元配列 2次元配列 配列を使って結果を返す 演習問題
関数の定義.
第10回関数 Ⅱ (ローカル変数とスコープ).
アルゴリズムとプログラミング (Algorithms and Programming)
2011/06/21-24 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊
講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ
第7回 条件による繰り返し.
第7回 プログラミングⅡ 第7回
岩村雅一 知能情報工学演習I 第10回(後半第4回) 岩村雅一
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
アルゴリズムとデータ構造 第1章 アルゴリズムと計算量 4月22日
アルゴリズムとデータ構造 はじめに 第1章 アルゴリズムと計算量
プログラミング 4 探索と計算量.
第2回課題 配布した通り.氏名・学生番号を忘れないこと.
アルゴリズムとデータ構造 2011年7月8日課題の復習
Cプログラミング演習資料.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとプログラミング (Algorithms and Programming)
復習 2次元配列 4列 j = 0 j = 1 j = 2 j = 3 i = 0 i = 1 i = 2 3行
補講:アルゴリズムと漸近的評価.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
アルゴリズムからプログラムへ GRAPH-SEARCH
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
復習 breakとcontinueの違い int i; for (i = 1; i <= 100; i++) { ・・・処理1・・・・
復習 Cにおけるループからの脱出と制御 break ループを強制終了する.if文と組み合わせて利用するのが一般的. continue
アルゴリズムとプログラミング (Algorithms and Programming)
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
第5回 プログラミングⅡ 第5回
復習 breakとcontinueの違い int i; for (i = 1; i <= 100; i++) { ・・・処理1・・・・
情報処理Ⅱ 2005年10月28日(金).
ヒープソート.
コンパイラ 2012年10月11日
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
岩村雅一 知能情報工学演習I 第10回(後半第4回) 岩村雅一
高度プログラミング演習 (07).
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
プログラミング演習II 2004年11月 2日(第3回) 理学部数学科・木村巌.
プログラミング入門2 第5回 配列 変数宣言、初期化について
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
計算技術研究会 第5回 C言語勉強会 関数(function)を使う
岩村雅一 知能情報工学演習I 第7回(後半第1回) 岩村雅一
Presentation transcript:

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

復習 アルゴリズム+データ構造=プログラム 本講義は「プログラミング」の講義ではない。 使用するプログラミング言語に(あまり)依存しない、いろいろな種類のプログラムを作るための 「基本的な知識と技術の習得」 が本講義の目的 その基本知識と技術が アルゴリズム と データ構造

例えて言えば... 復習 アルゴリズムは料理のレシピ 入力 ... 料理の材料 (小麦粉、キャベツなど) 入力 ... 料理の材料 (小麦粉、キャベツなど) 出力 ... 料理 (お好み焼き、カレーライスなど) 料理を作るには材料をどんな手順でどのように調理するか、が必要 ... アルゴリズム データ構造は、料理のための道具 レシピが読めても、料理を作れないのでは意味がない!⇒ ちゃんと動くプログラムを書けなければ意味がない。。。さらに効率性も大事。。。

前回の問題:配列を使ったプログラム 問題1.変数aには配列が値として入っている。   たとえば、 a= [ 1, 2, 3,“a”,“ab”,“abc” ] ここで、a[1]とa[2]の値を取り換えるコード(プログラムの断片)は? 問題2.変数aには配列が値として入っている。   aの偶数番目の要素と奇数番目の要素をすべて取り換えるコードは?  たとえば、 a= [ 1, 2, 3,“a”]ならa= [ 2,1, “a”,3]となる

問題1. a[1]とa[2]の値を取り換える 例題: a= [ 1, 2, 3,“a”,“ab”,“abc” ] これは確かに例題には適用できるが  aがどんな値でもできるものではない --- 解として不適

問題1の関連問題 変数x と y の値を取り替える(swap) ダメな解答: x = y ; y = x x=3, y=5ならば、これによりx=5, y=3になる x,yの値に関係なくちゃんと動くことが条件 ダメな解答: x = y ; y = x その理由が即答できない人は『よく考えてみよう』 ; は複数のコードを一行で書くためのもの 正解:使われていない変数(ここではzとする)を用いる   z = x; x = y ; y = z 別解(Rubyの特性): x, y = y, x

プログラミング言語における=の意味 プログラミング言語の等号(=)の左辺と右辺は意味が異なる *例えば、数学的には、 x = x+1 はありえない   = の右側は「値」(変数なら、それが記憶している数値や文字列)   =の左側は「記憶場所」 だから、アルゴリズムの記述では代入に←を使ったりする * x = x+1  xの値に1を足した結果を記憶場所xに記憶 *a[1] = a[2] a[2]の「値」をa[1]の場所に書き込む x ← x+1 と書いた方がしっくりくる?

問題1. a[1]とa[2]の値を取り換える 例題: a= [ 1, 2, 3,“a”,“ab”,“abc” ] 一案: 使われていない変数xを用いて      x = a[1] ; a[1] = a[2] ; a[2] = x 別解:   a[1], a[2] = a[2], a[1] Rubyでは多重代入と呼びます

問題2.配列aの偶数番目の要素と奇数番目の要素をすべて取り換えるコード a= [ 1, 2, 3,“a”] なら a= [ 2,1, “a”,3] となる ダメな解答(1): a[2n] = a[2n+1]; a[2n+1] = a[2n] ダメな解答(2): a[0], a[1], a[2], a[3] = a[1], a[0], a[3], a[2] 配列の要素の個数だけ、「値の取替」の必要がある ⇒ 繰り返し を使う 解答例: i = 0 while ( i < a.length) a[i], a[i+1] = a[i+1],a[i] i = i+2 end # while 例題だけではなく、より広い範囲で(「一般的」に)適用できる解を求める!

アルゴリズムの例 入力 出力 問題(教科書p.1): n個の実数x1, x2, …, xnが与えられて、その中の最大値を求める

アルゴリズムの例(続) より明確な記述(p.2) 入力: 正の整数nとn個の実数値x1, x2, …, xn  手続き: 1. y ← x1 (yは「それまでの最大値」を記録) 2. i = 2,3,…,nに対して順に次を行う:    xi > y ならば y ← xi 3. yを出力する 「変数y に x1の値を代入する」

アルゴリズムの例(続) 「プログラム」風(p.3) 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言語の対応」参照 アルゴリズムにおいて「出力する」とは、 printするという意味でなく、returnによって 値を「返す」ということ

アルゴリズムの検証 このアルゴリズムがちゃんと動くかは 頭で考え、手を動かす アルゴリズムを反映したプログラムを作り、 アルゴリズムを反映したプログラムを作り、    適切な入力を与えて動かし、結果を調べる ことで検証する、つまり、正しいかどうかを確認する

アルゴリズムからRubyプログラムへ 2ページと3ページのどちらの記述でもよいがそれに基づいてRubyプログラムを書く 君たちはちゃんとマスターしていると信じたい!

アルゴリズムからRubyプログラムへ(続き:代入と配列の使用) 入力は、変数nとxとする。ただし、nの値は正整数、xの値は実数を要素とする配列 手続きの最初をRubyで書くのは簡単… 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プログラムでは=を使う y = x[1] 実はこれだと問題があるが、今はこれで進める

アルゴリズムからRubyプログラムへ(続き:繰り返し) 2番目の手続きは「繰返し」  Rubyには、『繰り返し』のメソッドはいろいろある: while, for, downto, times, … (適切なものを選べるようにしよう!) ここではforを使うのが適切 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; 実はこれだと問題があるが、今はこれで進める 書き方: for i in 2..n 繰り返される処理 end

アルゴリズムからRubyプログラムへ(続き:条件分岐) 「繰り返される処理」は ここでは「条件分岐」である。  Rubyの条件文の書き方:  if (条件式)   「条件式が成り立つ時の処理」  else   「条件式が不成立の時の処理」 end 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; elseと「条件式が不成立の時の処理」は、なくても可

アルゴリズムからRubyプログラムへ(2番目の処理のまとめ) 2番目の処理をまとめると以下のように書ける: for i in 2..n if (x[i] > y) y = x[i] end #if end #for 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プログラムへ(3番目の処理) 3番目の return y はyの値を返すもの。 でも、どこに返すのか? ここでの選択  (1) 画面に表示する(printを使う)  (2) アルゴリズムMAXの結果としてMAXを呼び出したモノに返す ここでは(2)を考える。 でも、「アルゴリズムMAXの結果として返す」とはどういうこと? 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プログラムへ (関数/メソッド) 「アルゴリズムMAXの結果として返す」とは、 Ruby の関数(メソッド)をつくり、それにmaxと名をつけ、maxの関数の処理として1から3までの処理をやらせる、 ということ 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では関数名を大文字にできないのでmaxとする return文が大事

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

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

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

アルゴリズムからRubyプログラムへ (完成) 関数は以下のようにdef を使って定義する: def max(n,x) y = x[1] for i in 2..n if (x[i] > y) y = x[i] end return y 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; # if # for Rubyのプログラムでは、endがdefやforやifなどと対応するため対応関係がわかりにくい。そこで、インデント(段付け)をして対応が分かるように書く # def

実際に検証してみよう 先のプログラムは単に「アルゴリズム」をプログラムに直しただけ。 それがちゃんと期待通りに計算するかは、 (1) 具体的な(入力)データを与える  (2) アルゴリズムが返した結果を表示させる ということが必要。

実際に検証してみよう(続き) この内容をmax.rbとして、実行させてみると… 具体的には以下のようなプログラムを作る: def max(n,x) y = x[1] for i in 2..n if (x[i] > y) y = x[i] end return y # ここからが検証用のデータ print max(10, [0.3, 0.1, 0.7, 0.9, 1, 0.2, 0.5, 0.8, 0.4, 1.0]) # if # for # def この内容をmax.rbとして、実行させてみると…

動かない… ちゃんと書いたはずなのだが、以下のようなエラーメッセージが出て動かない… max.rb:5:in `max': undefined method `>' for nil:NilClass (NoMethodError) from max.rb:4:in `each' from max.rb:4:in `max' from max.rb:12

めげない! エラーメッセージに理由が書いてある。それを読んで、理由を理解して、直してみよう。 講義用のウェブページにある「Rubyのエラーメッセージとその対処 」を読んでみよう。 これはそのうちのどこにあたるか?

プログラムの修正 「(5) 未定義(undefined)なメソッド(method)/関数によるエラー 」に相当することが分かる 解釈:この場合は、5行目に使われている> という「未定義なわけがない」演算子がやり玉にあがっている。 ここは、つまり「for nil:NilClass」が問題。つまり「nil」には > が使えない、と言っている。 対処法:このようなエラーが起きるのは、配列の要素の指定が間違っているか、要素の値の初期化(例えば0にする)ことを忘れている場合が多い

プログラムの修正(続き) わかっただろうか?配列の要素の指定に問題があったのである。 プログラムを見てみよう: def max(n,x) y = x[1] for i in 2..n if (x[i] > y) y = x[i] end return y yに配列の先頭の要素を与えた「つもり」 配列の2番目の要素から最後の要素まで、要素を一つ一つ調べている「つもり」 # if Rubyの配列のインデックスは、いくつから始まり、いくつが最後の要素をさすものだったかな? # for # def

プログラムの修正(完成) # maxアルゴリズムの検証 def max(n,x) y = x[0] for i in 1..(n-1) if (x[i] > y) y = x[i] end return y # ここからが検証用のデータ print max(10, [0.3, 0.1, 0.7, 0.9. 1.1, 0.2, 0.5, 0.8, 0.4, 1.0]) 実行させた結果は… # if # for # def

参考 プログラミング言語Cで書くと: float max(int n, float x[ ]) { int i; float y=x[0]; for (i=1; i < n; i++) { if (x[i] > y) { y=x[i]; } } return y; 実際には以下のプログラムに挿入 #include <stdio.h> #define Num 10 /* ここにいれる */ int main() { static float data[Num] = { 0.3, 0.1, 0.7, 0.9. 1.1, 0.2, 0.5, 0.8, 0.4, 1.0}; printf(“%f\n”, max(Num,data)); }

4月15日の課題 2. 配列aのx番目の要素とy番目の要素を取り換えて得られる配列を返 す関数定義torikae(a,x,y) 例: a = [1,2,3,4,5] 、とすると torikae(a,1,3)は [1,4,3,2,5] を返す 回答 概略は次のようになる(わからない人はいますか?)

4月15日の課題(2) z = a[x] a[x] = a[y] a[y] = z 配列aのx番目の要素とy番目の 2. 配列aのx番目の要素とy番目の要素を取り換えて得られる配列を返す関数定義torikae(a,x,y) def torikae(a,x,y) end # def z = a[x] a[x] = a[y] a[y] = z 配列aのx番目の要素とy番目の 要素を取りかえるコードは? ここに課題を満たすコード (プログラム)を書く # 最後に配列を返す--- return a 参考: 最初の3行は  a[x], a[y] = a[y], a[x] とも書ける

4月15日の課題(3) 2つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数の定義seiret2 例: a = [1,2] とすると seiret2(a)は [1,2] を返し、 a = [20,10] とすると seiret2(a)は [10,20] を返す 回答  概略は次のようになる(わからない人はいますか?)

4月15日の課題(3)続 if (a[0] > a[1]) a[1], a[0] = a[0], a[1] 2つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数の定義seiret2 例: a = [1,2] とすると seiret2(a)は [1,2] を返し、 a = [20,10] とすると seiret2(a)は [10,20] を返す def seiret2(a) end #def if (a[0] > a[1]) a[1], a[0] = a[0], a[1] end # if 参考: 2行目は a = torikae(a,0,1)  とも書ける 配列aの1番目の要素が2番目の要素より 大きければ、これらを取りかえるコード! return a # 最後に配列を返す

4月15日の課題(4) 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の定義 def seiret3(a) end # def ここに課題を満たすコード (プログラム)を書く これはちょっと考えないといけない…

4月15日の課題(4)続 4. 三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 考え方: 3つの要素(仮にx,y,zとする)を小さいものから大きいものに並び替えるとすれば6通りの可能性がある( 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とyの大きさを比べる… は 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とyの大きさを比べる… 次にx と zの大きさを比べる (1) x ≧ y ≧ z (2) x ≧ z ≧ y (5) z ≧ x ≧ y 最後にy と zの大きさを比べて(1)か(2)が決まる

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

4月15日の課題(4)続 4.三つの要素(いずれも数)をもつ配列aの中身を、小さいものから大 きいものになるよう並びかえた配列を返す関数seiret3の定義 完成させよう!

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

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

出欠レポート ここまでの作業内容を出欠レポートとして書く 次は、宿題について

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

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

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

基本的な用語の確認 aとbの公約数: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とbの最大公約数(GCD):aとbに共通する公約数のうち最大のもの 30と72の最大公約数(これをGCD(30,72)と書く)は…