講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ

Presentation on theme: "講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ"— Presentation transcript:

1 講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ

2 今回のプログラミングの課題 (前回の課題で取り上げた）data.txt の要素をソートして、 sorted.txt というファイルに書出す ソート(sort) とは： 数の場合、小さいものから大きなもの(昇順）、もしくは 大きなものから小さなもの(降順）、になるよう、 並び替えること 文字列の場合は、「辞書式順」(アルファベット順、もしくは 「あいうえお順」)が使われる

3 プログラムが作れたら… data.txtの中身 ソートの結果: 2 3 -5 9 12 -10 8 -3 -10 -3 -5 2 3 8 9
9 12 -10 8 -3 -10 -3 -5 2 3 8 9 12

4 プログラムの手順 入力: data.txt 処理: ソート（いろいろな方法がある） 出力: ソートした結果を画面表示する(ファイルに書出す）

5 プログラムの手順 入力: data.txt 処理: ソート（いろいろな方法がある） 出力: ソートした結果を画面表示する(ファイルに書出す）
処理: ソート（いろいろな方法がある） 出力: ソートした結果を画面表示する(ファイルに書出す） ファイルから要素を読み込み、配列に記憶する

6 プログラムの手順 入力: data.txt 処理: ソート（いろいろな方法がある） 出力: ソートした結果を画面表示する(ファイルに書出す）
処理: ソート（いろいろな方法がある） 出力: ソートした結果を画面表示する(ファイルに書出す） 適当な大きさの配列を用意する ファイルの読み込み準備（ファイル変数） ファイルから要素を一個ずつ読み込んで、 　配列に記憶する ファイルから要素を読み込み、配列に記憶する

7 プログラムの手順 入力: data.txt 処理: ソート（いろいろな方法がある）
処理: ソート（いろいろな方法がある） 　ここでは、昇順の選択ソート(selection sort)を考えよう 　「配列の1番目以降の要素で最小の要素を探し、1番目の要素と 交換する 。(これにより1番目の要素が「最小」となる) 　次に配列の2番目以降の要素で最小の要素を探し、2番目の要素 と交換する。(これにより2番目の要素が「2番目に最小」となる) …　この操作を配列の最後の要素まで繰り返す」 (3) 出力: ソートした結果を画面表示する(ファイルに書出す） 注意：配列で1番目の要素の インデックスは 0 同様に 2番目の要素のインデックスは 1 ファイルから要素を読み込み、配列に記憶する

8 昇順の選択ソートプログラム 「配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換する 。
次に配列の2番目以降の要素で最小の要素を探し、2番目の要素と交換する。 …　この操作を配列の最後の要素まで繰り返す」 注意：配列で1番目の要素の インデックスは 0 同様に 2番目の要素のインデックスは 1 ちょっと難しそう。。。なにをどうしたらよいのか？ 考え方：「何かを繰り返す」と書いてあるのだから、 繰り返される処理を「関数」として捉える

9 昇順の選択ソートプログラム 青字：入力 茶色：処理
注意：配列で1番目の要素の インデックスは 0 配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換 次に配列の2番目以降の要素で最小の要素を探し、2番目の要素 と交換… この操作を配列の最後の要素まで繰り返す これに注目 繰り返される処理を「関数」として捉える 青字：入力 茶色：処理 配列のi番目以降の要素で最小の要素を探し、 i 番目の要素と 交換する 最終的に得られるのは… 要素が交換された配列 確認：この部分でも当てはまる？

10 昇順の選択ソート 「配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換。 次に配列の2番目以降の要素で最小の要素を探し、2番目の要素と 交換… この操作を配列の最後の要素まで繰り返す」 という方法が実際にうまくいくのか、自分の手で確かめてみる: 注意：配列で1番目の要素の インデックスは 0 2番目の要素のインデックスは 1 ... 2 3 -5 9 12 -10 8 -3 -10 3 -5 9 12 2 8 -3 -10 -5 3 9 12 2 8 -3 -10 -5 -3 9 12 2 8 3 最小 最小 最小 うまくいきそう。。。

11 昇順の選択ソートプログラム作成 「配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換。
　次に配列の2番目以降の要素で最小の要素を探し、2番目の要素と 交換…　この操作を配列の最後の要素まで繰り返す」 まず、繰り返される処理を行う関数の名前、入力、処理、出力を定める 配列 arr の要素数を nとする 関数名を、（仮に）findAndReplace とする 処理: i番目以降の要素のうちの 最小値を見つけて i番目の要素と取り替える 入力：　整数の配列 int arr[ ] 整数 　int i, int n 出力：　書き換えられた整数の配列 int arr[ ] あとで修正

12 昇順の選択ソートプログラム作成 「配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換。
　次に配列の2番目以降の要素で最小の要素を探し、2番目の要素と 交換…　この操作を配列の最後の要素まで繰り返す」 注意：配列で1番目の要素の インデックスは 0 2番目の要素のインデックスは 1 ... 処理: i番目以降の要素のうちの 最小値を見つけて i番目の要素と取り替える やるべき仕事は２つ (1) 配列のi番目以降の要素から最小値を見つける (2) その要素とi番目の要素を入れ替える

13 「配列から最小値を求めるプログラム」の改訂
配列の1番目の要素（インデックス0）から最後の要素(インデッ クスn-1)までの要素のうちの最小値を求めるプログラム … は前に作った 今回はこれを元に 配列に対し、インデックスiからn-1までの要素のうちの最小値と 最小値の要素の番号(インデックス)を求める」関数 を作る 注意：配列で1番目の要素の インデックスは 0 そして、最小値とインデックスi番目の要素を入れ替える…　 　そのために、最小値の要素のインデックスも記憶する！

14 「配列から最小値を求めるプログラム」の改訂
第２回目演習で「配列の要素の最小値を求める」関数を作った: これを元に「インデックスiからn-1までの要素のうちの最小値と その番号(インデックス)を求める」関数にするには、以下をどの ように変更するかを考えれば良い： 入力 処理 出力 注意：2つのもの（ここでは最小値とそのインデックス）を返す方法はまだ学んでいない… 　しかし！　インデックスさえわかれば最小値がなんであるかは分かる！ 　そこで、「最小値のインデックス」を求める関数を考えてみよう

15 関数 minInArray 出力＝記憶した最小要素 は int 型 入力＝整数を要素とする配列 int ar[] と 要素数 int n
int minInArray (int ar[] , int n) { int min=ar[0]; 今まで見た要素の中で最小のものを記憶する」変数を宣言、その変数に初期値を与える int i; for (i=1; i< n; i++) { if (min > ar[i]) // 一個ずつmin値と比較 min = ar[i]; // minxよりも大きければ更新 } 要素を比較して最小値を求める return min; } 出力=最小要素

16 「配列から最小値を求めるプログラム」の改訂
配列に対し、インデックスiからn-1までの要素のうちの最小値と そのインデックスとを求める」関数に作り変えてみよう 整数型の配列 →　変更なし 配列の要素数 → 最小値を求める先頭のインデックス iと 最後の要素のインデックス n とする つまり, int arr[ ], int i, int n 入力 (2)処理 (3)出力 処理　→　最小要素の値に加えて その要素のインデックス　を記録 最小要素の値　→　その要素のインデックス　を返す　 これにより、最小要素の値を「先頭の要素と取り換え」も容易

17 前回の課題(1) 配列の最小の要素のインデックスを返す関数 IndexOfMin 整数型の配列 ar とその要素数nを引数とし、最小要素のインデッ クスを返す関数 例えば int array[] = { 5,4,3,2,1,6,7}; と宣言されているとき、この要素数は7であり、最小要素は1でそ のインデックスは 4 (つまり array[4] = 1)であるから、 IndexOfMin(array, 7) は 4 を返す。

18 関数 IndexOfMin 出力＝記憶した最小要素 は int 型 入力＝整数を要素とする配列 int ar[] と 要素数 int n
int indexOfMin (int ar[] , int n) { int min=ar[ans] , i; int ans=0; // 答えの候補、初期値は配列の先頭 要素を比較して最小値を求める for (i=1; i< n; i++) { if (min > ar[i]) // 一個ずつmin値と比較 min = ar[ans]; // minxよりも大きければ更新 } ans = i; return ans; } 返却値：最小要素のインデックス

19 昇順の選択ソートプログラム作成 「配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換。
　次に配列の2番目以降の要素で最小の要素を探し、2番目の要素と 交換…　この操作を配列の最後の要素まで繰り返す」 処理: インデックス i 以降の要素から (1) 最小値の要素のインデックスを見つけて (2)インデックス i の要素と取り替える (1) 関数の名前を findMinValueとする。 findMinValue(arr, i n)によりインデックスi番目からn-1番目までの要素のうち、最小値要素のインデックスを返す (2) findMinValue(arr, i, n)の値を k とすると、 arr[i]とarr[k]の値を取り替える(swap)

20 findMinValue(arr, i n)によりインデックスi番目からn-1番目までの要素のうち、最小値要素のインデックスを返す
findMinValue関数は IndexOfMin関数とは違う IndexOfMin 関数は引数の配列の全体で最小値を探し、そのイ ンデックスを返す findMinValue関数は引数の「ある特定の範囲」から最小値を探 し、そのインデックスを返す しかしfindMinValueは IndexOfMinをもとに作れる！

21 配列において指定された範囲における最小の要素を返す関数 MinInRange
MinInArray関数をもとにIndexOfMin関数を作ったように、 findMinValue関数をいきなり作らずに、次のようなMinInRange関数を 作ってから考えよう。 整数型の配列 ar 、最小要素を探すインデックスの値k、arの要素数nを 引数とし、最小要素を返す関数 例えば int array[] = { 1,2,3,5,7,9,4,6,8}; とmain関数で宣言されているとき、この配列の要素数は9 MinInRange(array,0,9) は 1を返す⇒全範囲でarray[0](=1)最小値 MinInRange (array, 3,9) は 4を返す⇒範囲内でarray[6](=4)が最小値 インデックス

22 関数 minInArray 出力＝記憶した最小要素 は int 型 入力＝整数を要素とする配列 int ar[] と 要素数 int n
int minInArray (int ar[] , int n) { int min=ar[0]; 今まで見た要素の中で最小のものを記憶する」変数を宣言、その変数に初期値を与える int i; for (i=1; i< n; i++) { if (min > ar[i]) // 一個ずつmin値と比較 min = ar[i]; // minxよりも大きければ更新 } 要素を比較して最小値を求める return min; } 出力=最小要素

23 関数 MinInRange 出力＝記憶した最小要素 は int 型 int MinInRange
(int ar[] , int s, int n) // sからn-1までの範囲での最小値 { int min=ar[s]; 今まで見た要素の中で最小のものを記憶する」変数を宣言、その変数に初期値を与える int i; for (i=s+1; i< n; i++) { if (min > ar[i]) // 一個ずつmin値と比較 min = ar[i]; // minxよりも大きければ更新 } 要素を比較して最小値を求める return min; } 出力=最小要素

24 配列において指定された範囲における最小の要素のインデックスを返す関数 findMinValue
整数型の配列 ar 、最小要素を探すインデックスの値k、arの要素 数nを引数とし、最小要素を返す関数 例えば int array[] = { 1,2,3,5,7,9,4,6,8}; と宣言されているとき、この要素数は9 findMinValue(array,0,9) は 0を返す⇒全範囲でarray[0](=1)最小値 findMinValue(array, 1,9) は 1を返す⇒範囲内でarray[1](=2)が最小値 findMinValue(array, 2,9) は 2を返す⇒範囲内でarray[2](=3)が最小値 findMinValue(array, 3,9) は 6を返す⇒範囲内でarray[6](=4)が最小値 インデックス

25 関数 MinInRange 出力＝記憶した最小要素 は int 型 int MinInRange
(int ar[] , int s, int n) // sからn-1までの範囲での最小値 { int min=ar[s]; 今まで見た要素の中で最小のものを記憶する」変数を宣言、その変数に初期値を与える int i; for (i=s+1; i< n; i++) { if (min > ar[i]) // 一個ずつmin値と比較 min = ar[i]; // minxよりも大きければ更新 } 要素を比較して最小値を求める return min; } 出力=最小要素

26 関数 findMinValue 出力＝記憶した最小要素 は int 型
int findMinValue (int ar[] , int s, int n) // sからn-1までの範囲での最小値 { int i; int ans=s, min=ar[ans]; for (i=s+1; i< n; i++) { if (min > ar[i]) // 一個ずつmin値と比較 ans = i; min = ar[ans]; // minxよりも大きければ更新 } 要素を比較して最小値を求める return ans; } 出力=最小要素

27 昇順の選択ソートプログラム作成 findAndReplace関数 「配列の1番目以降の要素で最小の要素を探し、1番目の要素と交換。
　次に配列の2番目以降の要素で最小の要素を探し、2番目の要素と 交換…　この操作を配列の最後の要素まで繰り返す」 findAndReplace関数 処理: インデックス i 以降の要素から (1) 最小値の要素のインデックスを見つけて (2)インデックス i の要素と取り替える (1) 関数の名前を findMinValueとする。 findMinValue(arr, i n)によりインデックスi番目からn-1番目までの要素のうち、最小値要素のインデックスを返す (2) findMinValue(arr, i, n)の値を k とすると、 arr[i]とarr[k]の値を取り替える(swap)

28 配列の要素の値の取替え（ちょっと落とし穴）
「arr[i]とarr[k]の値を取り替える(swap) 」についての注意 これは以下のようにすればできる、と勘違いする人が時々いる… arr[i] = arr[k] arr[k] = arr[i] これではできない！ 例: arr[i]=10, arr[k]=3とおくと、最初の実行で arr[i]=arr[k]=3 とな り、 arr[i]が持っていた値 10が消えてしまうからである！ 解決策：　変数をもう一つ用意する(tempとする） そして、 temp = arr[i] ; arr[i]=ar[k]; arr[k]=temp とする（これが動くことを確かめよ） コツ：変数をケチらないこと

29 関数 findAndReplace の完成　 void となっているのは、 「書き換えられた配列」を 内部で作っているから、 配列を出力しなくてよいため 関数 findMinValue を用いて作る void findAndReplace(int arr[ ], int i, int n) { int k, temp; k = findMinValue(arr, i, n); temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } 配列arrのi番目から最後の要素までで 「最小の要素」を探し、そのインデックスが kの値になっている arr[i]とarr[k]の値の交換： arr[i]にはi番目から最後の要素までの最小値が入る arr[k]にはもとのarr[i]の要素がはいる

30 昇順の選択ソートプログラムの作成 整数を要素とする配列 arr 、そのインデックス0からn-1まで(配列 の要素数はn)の要素をソートする: // arrには要素が既に入っているとする for (i=0; i < n; i++) { findAndReplace(arr, i, n); } // この結果 arr の中身はどうなっているだろうか？

31 選択ソート・アルゴリズムの記述 名称: Selection Sort 入力: 整数(もしくは浮動小数点数)型の配列 array, 要素数 n 出力: arrayの要素を昇順に並び替えたもの(関数の返却値はなし） 手順: for i ← 0 until n -1 do (i =0からn-1まで以下を行う) ind ← findMinValue(array, i, n) （arrayのiからn-1までの要素の 中で最小の要素の「インデックス」を求める) swap(array[i], array[index]) (array[i]とarray[index]の値を入れ替 える) findAndReplaace(array,i,n)

32 全体のプログラムの完成 data.txt の要素をソートして、sorted.txt というファイルに書出す #include <stdio.h> // 関数 findMinValue を定義 // 関数 findAndReplaceを定義 int main(void) { // 必要な変数の定義 // ファイルdata.txtから要素を読み込み 配列 arr に記憶 // そのとき、読み込んだ要素数も記憶 (変数nの値とする) // 選択ソートにより、配列 arr の中身を昇順ソート // arr の中身を sotred.txt に書出す return 0; }

33 課題の提出 プログラムを完成させ、 適当なファイル(例えばdata.txt)を与えて その要素をソートし その結果がsorted.txtファイルに書き込まれる ことを確認しよう できたらプログラム（説明付き）と実行結果を提出する。 プログラムは適切にインデントすることをお忘れなく