Document

プログラムのパタン演習
解説
（１）MIN/MAXパタン
型関数名(引数の並び) {
// 引数には、配列とその要素数(int)
// 変数宣言：答えを記憶する変数、繰り返しパラメタ
例: 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 答え;
}
return ans;
}
// 答えを返す
問題1. 配列の２番目に大きな要素を求める second
ヒント: 答えの候補と、最大の要素の二つを記憶する必要がある
この２つの変数に適切に初期値を与えること
繰り返しにおいては、この二つを更新する
int 配列の要素を返すので int
答えを返すのは、２番目に大きな要素だけ
型関数名(引数の並び) {
// 引数には、配列とその要素数(int)
// 変数宣言：答えの記憶、繰り返しパラメタ
// 答えを記憶する変数に初期値を与える、
// 大抵は配列の先頭の要素
// 繰り返し処理
// return 答え;
}
int second(int ar[], int n) {
int f, s, i, tmp; // iは繰り返しのパラメタ, fは最大, sは2番目
f = ar[0]; s = ar[1];
// fとsに仮の値を入れる
// fがsより大きいことを保証する
if (s > f) { tmp=f; f =s; s=tmp; }
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;
// 答えを返す
ar[0]とar[1]は調査済みなので
ar[2]から繰り返しを始める
}
問題2. 目標値(引数で与えられる)に最も
近い配列の要素を求める nearest int 配列の要素を返すので int
ヒント: 配列の要素と答えの候補の比較には、「目標値との差の2乗」を用いる
その値を記憶する変数 dif を用意し、また答えの候補が変わるたびにこの変数も更新するとよい
注意: math.hをincludeして使えるようになる「絶対値」関数 abs を用いても良い
型関数名(引数の並び) {
// 引数には、配列とその要素数(int)
// 変数宣言：答えの記憶、繰り返しパラメタ
// 答えを記憶する変数に初期値を与える、
// 大抵は配列の先頭の要素
// 繰り返し処理
// return 答え;
}
目標値の変数を 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;
// 答えを返す
}
問題3. 条件が複数ある例：配列の要素の
うち、奇数で最大のものを求める
oddMax
注意: 配列の要素に奇数がない場合は「ない」と答えなければならない
いろいろなやり方がある。
(1) 奇数があるかどうかをチェックし、あった場合はその中で「最大」の要素
を求める
(2) 配列の要素から奇数だけを抜き出して配列を作り、その中で「最大」の要
素を探す
などなど…
注意: 整数 x が偶数 ⇔ xが2で割り切れる  条件 x % 2 == 0 が成立
整数 x が奇数 ⇔ xが2で割り切れない  条件 x % 2 != 0 が成立
(1) 奇数があるかどうかをチェックし、
あった場合はその中で「最大」の要素を
求める
型関数名(引数の並び) {
// 引数には、配列とその要素数(int)
// 変数宣言：答えの記憶、繰り返しパラメタ
// 答えを記憶する変数に初期値を与える、
// 大抵は配列の先頭の要素
// 繰り返し処理
// return 答え;
}
int oddMax(int ar[], int n) { // 配列の型と関数の型は一致
// n は配列の要素数なので int になる
int ans, i; // ansは答えの候補、iは繰り返しのパラメタ
ans = ar[0]; // ansに初期値を入れる
iffor
(i (i
===n)
0;}{ // 配列の要素を繰り返しで調べる
// 奇数がなかった場合0を返す
1;{i return
< n; i++)
for (i++
i < <n;ar[i])
i++) { // 配列の要素と答え候補を比較
if (; ans
if ((ar[i] % 2 !=0)
(ar[i]
> ans)) //奇数でansより大きい
ans =&&
ar[i];
// 答えの候補を更新
{}
ans = ar[i];
// ansの値の更新
} }// ここまで繰り返し処理の内容
}
return 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を引数とし、最小要素のインデッ
クスを返す関数を作れ。
例えば
0 1 2 3 4 5 6
インデックス
int array[] = { 5,4,3,2,1,6,7};
と宣言されているとき、この要素数は7であり、最小要素は1でそ
のインデックスは 4 (つまり array[4] = 1)であるから、
IndexOfMin(array, 7) は 4 を返す。
課題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を引数とし、最小要素を返す関数を作れ。
例えば
0 1 2 3 4 5 6 7 8 インデックス
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)が最小値

Download Report