* 第3回 C言語の復習（アルゴリズム） [#u486ad25]
** 目的 [#v6b7e8c7]
前回までに配列と関数の練習をしてもらったが、これらが利用できるようになると、いろいろなプログラムを組めるようになる。そこで、プログラムを作成するときに実際に出てくる問題に対処するため、探索や整列など、簡単なアルゴリズムについて学ぶ。
** 課題 [#f905fdc5]
今回の課題は、進んでいるひと向けの応用問題である。
[[第1回>../2003-F01]]のa1)〜b10)、[[第2回>../2003-F02]]のd1)〜e10)を解き終わっていない人は、引き続きそちらをやってもらいたい。これらの問題を独力で解ける力がないと、今回の課題を解くことは無理だろう。また、この問題が難しすぎると思った人は、[[第4回>../2003-F04]]g1)以降に進んでよい。
提出は、[[提出エリア>../提出]]の自分の提出エリアにアップロードする。なお、プログラムは、きちんとコンパイルし、完全かつ正確に動作することを確認してから、提出すること。
- [[プログラムの提出のしかた>../提出]]
- [[C言語のコンパイルと実行のしかた>../C言語環境]]
*** 中級〜上級レベル [#de4f1b64]
''線形探索（逐次探索）''
> 配列の中からある値を探し出すときのことを考えてみよう。まず、誰でも思いつくのは、配列の先頭から順に値と比較していく方法である。これは線形探索といい、もっとも素朴で確実な探索の方法である。
f1-1) キーボードから、10個の整数を要素とする配列aと、整数xを読み込み、xがaに含まれているかどうか調べて結果を表示するプログラムを作成しなさい。
i→ →| iを0から9まで変化させる
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
a[i]とxを比較
f1-2) 整数配列a、その要素数n、探したい整数xを引数に取り、見つかった場所（添字）を返す関数linear_searchを作成しなさい。ただし、見つからなかった場合には、-1を返すようにしなさい。
int linear_search(int a[], int n, int x);
----
''バブルソート''
> 配列の中身を順番に（小さい順や大きい順に）並べ替えることを考えてみよう。もっとも古くからある方法は、バブルソートと呼ばれている。この方法では、配列を調べて、隣同士が逆順に並んでいるところがあれば交換する。これを何回も繰り返して、交換する必要がなくなるまで続ける。交換の必要がなくなれば、配列の要素はすべて順番に並んだことになる。
f2-1) キーボードから10個の整数を要素とする配列aを読み込み、配列の先頭から順に隣同士の要素を比較して、前の要素が後の要素よりも大きいところをすべて表示するプログラムを作成しなさい。
i→ →| iの変化は8まで
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
a[i]とa[i+1]を比較
f2-2) 以下に示すような動作をするプログラムを作成しなさい。
+ キーボードから10個の整数を読み込み、配列aに格納する。
+ 配列の先頭から順に隣同士の要素を比較して、前の要素が後の要素よりも大きければ交換する。
+ 配列の最後の要素まで到達したら、配列全体を表示して終了する。
f2-3) 以下に示すような動作をするプログラムを作成しなさい。
+ キーボードから10個の整数を読み込み、配列aに格納する。
+ 配列の先頭から順に隣同士の要素を比較して、前の要素が後の要素よりも大きければ交換する。
+ 配列の最後の要素まで到達したら：
-- 交換回数が0回より多ければ、0にセットしなおして2.に戻って繰り返す。
-- 交換回数が0回ならば、配列全体を表示して終了する。
上のプログラムの動作の意味をよく考えて、どうして整列ができるのか理解しなさい。
//f2-4) 整数配列をバブルソートする関数を作成しなさい。引数は、整数配列aとその要素数nである。
// void bubble_sort(int a[], int n);
----
''スタック''
> スタックとは、先入れ後出し方式のデータ構造である。データを上に積み重ねていくような形式のデータ構造であり、一番最後に積んだデータを一番最初に取り出すことができる。一番最初に積んだデータは、後から積んだデータを全部取り出さないと、取り出すことができない。ここでは、段階的にスタックを作ってみよう。
f3-1) キーボードから100個以内の正の整数を読み込んでいき、0以下の数が入力された時点で終了として、それまでに入力された整数をすべて表示するプログラムを作成しなさい。
f3-2) 次のような動作をするプログラムを作成しなさい。f3-1)との違いは最後に逆順に表示することだけである。
+ 100個の整数を保存しておくための配列stackを用意する。
+ キーボードから整数xを読み込む。
+ xの値を判定し：
-- x>0ならば、xをstackの最後に追加して（積んで）2.に戻る。
-- そうでなければ、stackの中身を逆順にすべて表示して、プログラムを終了する。
次の空き
↓
0 1 2 3 4 5 6 7 8 9
stack [●|●|●|__|__|__|__|__|__|__|....
↑
xを積む（push）
次の空き
↓
0 1 2 3 4 5 6 7 8 9
stack [●|●|●|ｘ|__|__|__|__|__|__|....
f3-3) 以下に示すような動作をするプログラムを作成しなさい。
+ 100個の整数を保存しておくための配列stackを用意する。
+ キーボードから整数xを読み込む。
+ xの値を判定し：
-- x>0ならば、xをstackに積んで2.に戻る（push）。
-- x<0ならば、stackに最後に積んだ値を表示して、それをstackから取り除き、2.に戻る（pop）。
-- x=0ならば、stackの中身を逆順にすべて表示して、プログラムを終了する。
次の空き
↓
0 1 2 3 4 5 6 7 8 9
stack [●|●|●|●|●|●|__|__|__|__|....
↓
取り出す（pop）
次の空き
↓
0 1 2 3 4 5 6 7 8 9
stack [●|●|●|●|●|__|__|__|__|__|....
>なお、スタックにデータをしまう操作をpushといい、データを取り出す操作をpopという。また、スタックの現在の最後の位置（または次の空きの位置）を保存する変数をスタックポインタという。
----
''2分探索''
> 配列からある値を検索するとき、もし配列の要素があらかじめ順番に並んでいれば、比較の回数を劇的に減らして速く終わらせることができる。たとえば、小さい順に並んでいる配列からある値xを検索することを考えてみよう。
+ まず、配列の真ん中の要素mとxを比較する。x=mならば発見であり、x<mならばxは配列の前半に、x>mならば後半にあるかもしれないことがわかる。
+ もし、配列の前半にあることが分かったら、さらに前半の中で真ん中の要素m2と比較する。x=m2ならば発見であり、x<m2ならば前半の前半に、x>m2ならば前半の後半にあるかもしれないことがわかる。
>この手順を次々と繰り返していけば、最小の比較回数で配列の中から値を検索することができる。これが、2分探索法である。
f4-1) キーボードから、小さい順に並んだ10個の整数の配列aと、探索したい整数x、探索範囲を示す整数leftおよびrightを読み込み、配列のa[left]〜a[right]の範囲にxがあるかどうか調べるプログラムを作成せよ。探索方法は、線形探索でよい。
left right
↓ ↓
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
|←探索範囲→|
この間にxがあるかどうか
f4-2) キーボードから、小さい順に並んだ10個の整数の配列aと、整数x、整数leftおよびrightを読み込み、xが、配列のa[left]〜a[right]の範囲の、前半あるか後半にあるか調べるプログラムを作成せよ。(left+right)/2番目の要素と1回比較すればよい。
left right
↓ ↓
|←探索範囲→|
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
↑
中心(left+right)/2
f4-3) 以下に示すような動作をするプログラムを作成しなさい。
+ 準備
-- キーボードから小さい順に整列済みの10個の整数を読み込み、配列aに格納する。
-- キーボードから整数xを読み込む。
-- 最初の探索範囲を表す変数として、left = 0, right = 9とする。
+ 探索範囲の中心を表す変数として、mid = (left + right) / 2 とする。
+ xとa[mid]を比較して：
-- x=a[mid]ならば、見つかったので結果を表示して探索終了。
-- x<a[mid]ならば、xは前半にあるので、right=mid-1とする。（4.に進む）
-- x>a[mid]ならば、xは後半にあるので、left=mid+1とする。（4.に進む）
+ もしleft>rightとなってしまったら、見つからなかったので探索終了。
+ 2.に戻って探索を繰り返す。
上のプログラムの動作の意味をよく考えて、どうして探索ができるのか理解しなさい。
//f4-4) 小さい順に整列済みの整数配列a、その要素数n、探したい整数xを引数に取り、見つかった場所（添字）を返す関数binary_searchを作成しなさい。ただし、見つからなかった場合には、-1を返すようにしなさい。
// int binary_search(int a[], int n, int x);
----
''単純挿入ソート''
> また別の古くからある整列アルゴリズムを紹介する。それは、配列から1つずつ要素を取り出して、整列済みの配列の適切な位置に挿入していく方法である。これは単純挿入ソートと呼ばれており、適切な挿入位置を求めるには探索を用いる。
f5-1) まず、大きさ10の整数配列aを用意し、キーボードからa[0]〜a[8]に整数を読み込む。次に、a[2]以降を1つずつずらしてa[2]に0を挿入し、結果を表示するプログラムを作成しなさい。
0 1 2 3 4 5 6 7 8 9
a [●|△|■|◎|▼|○|◇|☆|♪|__]
→ ずらす
a [●|△|__|■|◎|▼|○|◇|☆|♪]
f5-2) まず、大きさ10の整数配列aとbを用意し、キーボードからaに10個の整数を読み込む。そして、aから1つずつ要素を取り出して、bに小さい順に並ぶようにコピーしていくプログラムを作成しなさい。
aからbに値をコピーする前に、線形探索で適切な挿入位置を決め、場所を空けるためにそれ以降の要素を1つずつずらす必要がある。
0 1 2 3 4 5 6 7 8 9
b [_1|_4|_6|_9|12|__|__|__|__|__]
↑
8をここに挿入したいので、ずらす。
b [_1|_4|__|_6|_9|12|__|__|__|__]
↑
8 ここに挿入
f5-3) 今度は、aとbというふたつの配列は使わずに、配列aだけを使って同じことをしよう。aの左側をbの代わりの整列済みの配列として用いる。
以下に示すような動作をするプログラムを作成しなさい。
+ キーボードから10個の整数を読み込み、配列aに格納する。
+ 配列から1つずつ要素を取り出すために、i = 1とする。
+ a[0]〜a[i-1]の中で、a[i]を挿入すべき適切な位置をしらべ、a[j]〜a[i-1]を右に1つずらして挿入する。
+ iに1を加えて、まだ要素が残っていれば3.に戻る。
次に整列する要素
↓
0 1 2 3 4 5 6 7 8 9
a [_1|_4|_8|_3|_9|_5|10|_3|_4|_2]
|
整列済み 整列待ち
→ずらす
a [_1|__|_4|_8|_9|_5|10|_3|_4|_2]
↑ |
3 整列待ち
f5-4) 挿入位置の探索に、2分探索を使ってみなさい。
![[PukiWiki]](image/viLab.png "[PukiWiki]")
