CLab/2005-FX2
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
開始行:
* 応用課題2(アルゴリズム) [#kec8077f]
** 目的 [#u4b7e743]
前回までに配列と関数の練習をしてもらったが、これらが利用...
** 課題 [#w3b017d9]
今回の課題は、進んでいるひと向けの応用問題である。
[[第1回>../2003-F01]]のa1)〜b10)、[[第2回>../2003-F02]]の...
提出は、[[提出エリア>../提出]]の自分の提出エリアにアップ...
- [[プログラムの提出のしかた>../提出]]
- [[C言語のコンパイルと実行のしかた>../C言語環境]]
*** 中級〜上級レベル [#p1fccf39]
''線形探索(逐次探索)''
> 配列の中からある値を探し出すときのことを考えてみよう。...
f1-1) キーボードから、10個の整数を要素とする配列aと、整数...
i→ →| iを0から9まで変化させる
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
a[i]とxを比較
f1-2) 整数配列a、その要素数n、探したい整数xを引数に取り、...
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) 整数配列をバブルソートする関数を作成しなさい。引...
// void bubble_sort(int a[], int n);
----
''スタック''
> スタックとは、先入れ後出し方式のデータ構造である。デー...
f3-1) キーボードから100個以内の正の整数を読み込んでいき、...
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 [●|●|●|x|__|__|__|__|__|__|....
f3-3) 以下に示すような動作をするプログラムを作成しなさい。
+ 100個の整数を保存しておくための配列stackを用意する。
+ キーボードから整数xを読み込む。
+ xの値を判定し:
-- x>0ならば、xをstackに積んで2.に戻る(push)。
-- x<0ならば、stackに最後に積んだ値を表示して、それをstac...
-- 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といい、データを...
----
''2分探索''
> 配列からある値を検索するとき、もし配列の要素があらかじ...
+ まず、配列の真ん中の要素mとxを比較する。x=mならば発見で...
+ もし、配列の前半にあることが分かったら、さらに前半の中...
>この手順を次々と繰り返していけば、最小の比較回数で配列の...
f4-1) キーボードから、小さい順に並んだ10個の整数の配列aと...
left right
↓ ↓
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
|←探索範囲→|
この間にxがあるかどうか
f4-2) キーボードから、小さい順に並んだ10個の整数の配列aと...
left right
↓ ↓
|←探索範囲→|
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
↑
中心(left+right)/2
f4-3) 以下に示すような動作をするプログラムを作成しなさい。
+ 準備
-- キーボードから小さい順に整列済みの10個の整数を読み込み...
-- キーボードから整数xを読み込む。
-- 最初の探索範囲を表す変数として、left = 0, right = 9と...
+ 探索範囲の中心を表す変数として、mid = (left + right) / ...
+ xとa[mid]を比較して:
-- x=a[mid]ならば、見つかったので結果を表示して探索終了。
-- x<a[mid]ならば、xは前半にあるので、right=mid-1とする。...
-- x>a[mid]ならば、xは後半にあるので、left=mid+1とする。...
+ もしleft>rightとなってしまったら、見つからなかったので...
+ 2.に戻って探索を繰り返す。
上のプログラムの動作の意味をよく考えて、どうして探索がで...
//f4-4) 小さい順に整列済みの整数配列a、その要素数n、探し...
// int binary_search(int a[], int n, int x);
----
''単純挿入ソート''
> また別の古くからある整列アルゴリズムを紹介する。それは...
f5-1) まず、大きさ10の整数配列aを用意し、キーボードからa[...
0 1 2 3 4 5 6 7 8 9
a [●|△|■|◎|▼|○|◇|☆|♪|__]
→ ずらす
a [●|△|__|■|◎|▼|○|◇|☆|♪]
f5-2) まず、大きさ10の整数配列aとbを用意し、キーボードか...
aからbに値をコピーする前に、線形探索で適切な挿入位置を決...
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だけ...
以下に示すような動作をするプログラムを作成しなさい。
+ キーボードから10個の整数を読み込み、配列aに格納する。
+ 配列から1つずつ要素を取り出すために、i = 1とする。
+ a[0]〜a[i-1]の中で、a[i]を挿入すべき適切な位置をしらべ...
+ 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分探索を使ってみなさい。
終了行:
* 応用課題2(アルゴリズム) [#kec8077f]
** 目的 [#u4b7e743]
前回までに配列と関数の練習をしてもらったが、これらが利用...
** 課題 [#w3b017d9]
今回の課題は、進んでいるひと向けの応用問題である。
[[第1回>../2003-F01]]のa1)〜b10)、[[第2回>../2003-F02]]の...
提出は、[[提出エリア>../提出]]の自分の提出エリアにアップ...
- [[プログラムの提出のしかた>../提出]]
- [[C言語のコンパイルと実行のしかた>../C言語環境]]
*** 中級〜上級レベル [#p1fccf39]
''線形探索(逐次探索)''
> 配列の中からある値を探し出すときのことを考えてみよう。...
f1-1) キーボードから、10個の整数を要素とする配列aと、整数...
i→ →| iを0から9まで変化させる
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
a[i]とxを比較
f1-2) 整数配列a、その要素数n、探したい整数xを引数に取り、...
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) 整数配列をバブルソートする関数を作成しなさい。引...
// void bubble_sort(int a[], int n);
----
''スタック''
> スタックとは、先入れ後出し方式のデータ構造である。デー...
f3-1) キーボードから100個以内の正の整数を読み込んでいき、...
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 [●|●|●|x|__|__|__|__|__|__|....
f3-3) 以下に示すような動作をするプログラムを作成しなさい。
+ 100個の整数を保存しておくための配列stackを用意する。
+ キーボードから整数xを読み込む。
+ xの値を判定し:
-- x>0ならば、xをstackに積んで2.に戻る(push)。
-- x<0ならば、stackに最後に積んだ値を表示して、それをstac...
-- 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といい、データを...
----
''2分探索''
> 配列からある値を検索するとき、もし配列の要素があらかじ...
+ まず、配列の真ん中の要素mとxを比較する。x=mならば発見で...
+ もし、配列の前半にあることが分かったら、さらに前半の中...
>この手順を次々と繰り返していけば、最小の比較回数で配列の...
f4-1) キーボードから、小さい順に並んだ10個の整数の配列aと...
left right
↓ ↓
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
|←探索範囲→|
この間にxがあるかどうか
f4-2) キーボードから、小さい順に並んだ10個の整数の配列aと...
left right
↓ ↓
|←探索範囲→|
0 1 2 3 4 5 6 7 8 9
a [__|__|__|__|__|__|__|__|__|__]
↑
中心(left+right)/2
f4-3) 以下に示すような動作をするプログラムを作成しなさい。
+ 準備
-- キーボードから小さい順に整列済みの10個の整数を読み込み...
-- キーボードから整数xを読み込む。
-- 最初の探索範囲を表す変数として、left = 0, right = 9と...
+ 探索範囲の中心を表す変数として、mid = (left + right) / ...
+ xとa[mid]を比較して:
-- x=a[mid]ならば、見つかったので結果を表示して探索終了。
-- x<a[mid]ならば、xは前半にあるので、right=mid-1とする。...
-- x>a[mid]ならば、xは後半にあるので、left=mid+1とする。...
+ もしleft>rightとなってしまったら、見つからなかったので...
+ 2.に戻って探索を繰り返す。
上のプログラムの動作の意味をよく考えて、どうして探索がで...
//f4-4) 小さい順に整列済みの整数配列a、その要素数n、探し...
// int binary_search(int a[], int n, int x);
----
''単純挿入ソート''
> また別の古くからある整列アルゴリズムを紹介する。それは...
f5-1) まず、大きさ10の整数配列aを用意し、キーボードからa[...
0 1 2 3 4 5 6 7 8 9
a [●|△|■|◎|▼|○|◇|☆|♪|__]
→ ずらす
a [●|△|__|■|◎|▼|○|◇|☆|♪]
f5-2) まず、大きさ10の整数配列aとbを用意し、キーボードか...
aからbに値をコピーする前に、線形探索で適切な挿入位置を決...
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だけ...
以下に示すような動作をするプログラムを作成しなさい。
+ キーボードから10個の整数を読み込み、配列aに格納する。
+ 配列から1つずつ要素を取り出すために、i = 1とする。
+ a[0]〜a[i-1]の中で、a[i]を挿入すべき適切な位置をしらべ...
+ 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分探索を使ってみなさい。
ページ名: