プログラムのパタン演習 解説

（１）MIN/MAXパタン 型 関数名(引数の並び) { // 引数には、配列とその要素数(int) // 変数宣言：答えを記憶する変数、繰り返しパラメタ // 答えを記憶する変数に初期値を与える、 // 大抵は配列の先頭の要素 // 繰り返し処理 // return 答え; } 例: int max(int ar[], int n) { // 配列の型と関数の型は一致 // n は配列の要素数なので int になる int ans, i; // ansは答えの候補、iは繰り返しのパラメタ ans = ar[0]; // ansに初期値を入れる for (i = 1; i < n; i++) { // 配列の要素を繰り返しで調べる if ( ans < ar[i]) { // 配列の要素と答え候補を比較 ans = ar[i]; // 答えの候補を更新 } } // ここまで繰り返し処理の内容 return ans; // 答えを返す

問題1. 配列の２番目に大きな要素を求める second ヒント: 答えの候補と、最大の要素の二つを記憶する必要がある この２つの変数に適切に初期値を与えること 繰り返しにおいては、この二つを更新する 答えを返すのは、２番目に大きな要素だけ int 配列の要素を返すので int int second(int ar[], int n) { int f, s, i, tmp; // iは繰り返しのパラメタ, fは最大, sは2番目 f = ar[0]; s = ar[1]; // fとsに仮の値を入れる for (i = 2; i < n; i++) { // 配列の要素を繰り返しで調べる if ( f < ar[i]) { // 最大要素候補があった s = f; f = ar[i]; // fとsの値を更新 } else { // f >= ar[i]の場合はここにくる if (s < ar[i]) // 二番目に最大の候補がきた { s = ar[i]; } // s の値を更新 } } // ここまで繰り返し処理の内容 return s; // 答えを返す 型 関数名(引数の並び) { // 引数には、配列とその要素数(int) // 変数宣言：答えの記憶、繰り返しパラメタ // 答えを記憶する変数に初期値を与える、 // 大抵は配列の先頭の要素 // 繰り返し処理 // return 答え; } // fがsより大きいことを保証する if (s > f) { tmp=f; f =s; s=tmp; } ar[0]とar[1]は調査済みなので ar[2]から繰り返しを始める

問題2. 目標値(引数で与えられる)に最も近い配列の要素を求める nearest int 配列の要素を返すので int ヒント: 配列の要素と答えの候補の比較には、「目標値との差の2乗」を用いる その値を記憶する変数 dif を用意し、また答えの候補が変わるたびにこの変数も更新するとよい 注意: math.hをincludeして使えるようになる「絶対値」関数 abs を用いても良い 目標値の変数を target とした int nearest(int ar[], int n, int target) { int ans, i; // iは繰り返しのパラメタ, ansは答え候補 int dif, dif2; // difで答え候補と目標値との差の2乗を記憶 ans = ar[0]; dif = (ans – target)* (ans – target); // 初期値 for (i = 1; i < n; i++) { // 配列の要素を繰り返しで調べる // これは基本的に「最小」の要素を求める関数 // ただし「目標値との差の2乗」を最小にする dif2 = (ar[i] – target)* (ar[i] – target); if (dif > dif2) { dif = dif2; ans = ar[i]; } // 値の更新 } // ここまで繰り返し処理の内容 return ans; // 答えを返す } 型 関数名(引数の並び) { // 引数には、配列とその要素数(int) // 変数宣言：答えの記憶、繰り返しパラメタ // 答えを記憶する変数に初期値を与える、 // 大抵は配列の先頭の要素 // 繰り返し処理 // return 答え; }

問題3. 条件が複数ある例：配列の要素のうち、奇数で最大のものを求める oddMax 注意: 配列の要素に奇数がない場合は「ない」と答えなければならない いろいろなやり方がある。 (1) 奇数があるかどうかをチェックし、あった場合はその中で「最大」の要素 を求める (2) 配列の要素から奇数だけを抜き出して配列を作り、その中で「最大」の要 素を探す などなど… 注意: 整数 x が偶数 ⇔ xが2で割り切れる  条件 x % 2 == 0 が成立 整数 x が奇数 ⇔ xが2で割り切れない  条件 x % 2 != 0 が成立

(1) 奇数があるかどうかをチェックし、あった場合はその中で「最大」の要素を求める int oddMax(int ar[], int n) { // 配列の型と関数の型は一致 // n は配列の要素数なので int になる int ans, i; // ansは答えの候補、iは繰り返しのパラメタ ans = ar[0]; // ansに初期値を入れる for (i = 1; i < n; i++) { // 配列の要素を繰り返しで調べる if ( ans < ar[i]) { // 配列の要素と答え候補を比較 ans = ar[i]; // 答えの候補を更新 } } // ここまで繰り返し処理の内容 return ans; // 答えを返す 型 関数名(引数の並び) { // 引数には、配列とその要素数(int) // 変数宣言：答えの記憶、繰り返しパラメタ // 答えを記憶する変数に初期値を与える、 // 大抵は配列の先頭の要素 // 繰り返し処理 // return 答え; } if (i == n) { return 0;} // 奇数がなかった場合0を返す for (i++ ; i < n; i++) { if ((ar[i] % 2 !=0) && (ar[i] > ans)) //奇数でansより大きい { ans = ar[i]; // ansの値の更新 } for (i=0; i<n; i++) { if (ar[i] % 2 !=0) { ans = ar[i]; break; } この後、 i == nの時は、奇数がなかった！ そうでない場合は 続けて(ar[i+1]の要素から)調べれば良い

(2) 配列の要素から奇数だけを抜き出して配列を作り、その中で「最大」の要素を探す int oddMax(int ar[], int n) { // 配列の型と関数の型は一致 int odds[NUM], i, j=0 ; // odds配列に奇数を入れる。 // iは繰り返しのパラメタ、jはodds配列のどこまで数を入れたかを記憶する for (i = 0; i < n; i++) { // 配列の要素を繰り返しで調べる if (ar[i] % 2 != 0) { // 奇数ならば odds[j++] = ar[i]; // odds配列に奇数を記憶 } } // ここまで繰り返し処理の内容 if (j == 0) // 奇数がなかった場合 { return 0; } // 0を返すことで「奇数がなかった」ことを表すものとする // それ以外の場合はここにくる return maxInArray(odds, j ); // 配列oddsの中の最大要素を求める(関数maxInArrayを利用) }

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

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

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