プログラムの１行目で要求されている引数を用意します。
まずはプログラムに入力する数値を集めます。
このプログラムは１行目で x[ ]、n、k を要求しています。
すべて揃わないとプログラムは動作しません。
設問１の値を利用します。
| x[1 2 3 4 5 6 7] | n | k |
|---|---|---|
| 3 5 6 4 7 2 1 | 7 | 3 |
初期値を設定します。
3行目 Top←1
4行目 Last←n なので Last は 7
| Top | Last |
|---|---|
| 1 | 7 |
6行目 Pivot←x[k] なので Pivot は 6
7行目 i←Top なので i は 1
8行目 j←Last なので j は 7
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 6 4 7 2 1 | 6 | 1 | 7 |
１回目
10行目で X[1] すなわち 3 と Pivot すなわち 6 を比べるのですがこれは頭の中で行います。
結果はTrueです。
11行目 i←i + 1 は書き換えなので表に書き込みます。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 6 4 7 2 1 | 6 | 7 | 2 |
10行目に戻って x[2] すなわち 5 と Pivot すなわち 6 を比べます。
Trueなので i を書き換えます。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 6 4 7 2 1 | 6 | 7 | |
| 3 |
10行目に戻って x[3] と Pivot を比べます。
Falseなのでループを抜けます。
13行目 Pivot と x[7] を比べます。
Falseなのでループを抜けます。
16行目はFalseなので17行目は実行しません。
19から21行目は三角交換です。
x[ i ] と x[ j ] を交換します。
書き換えなので表に書き込みます。
22行目、i に 1 を足します。
23行目、j から 1 を引きます。
書き換えなので表に書き込みます。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 |
6 | ||
| 3 5 1 4 7 2 6 | 4 | 6 |
10行目に戻って x[4] と Pivot を比べます。
Trueなので i を書き換えます。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 |
6 | ||
| 3 5 1 4 7 2 6 | 6 | ||
| 5 |
10行目に戻って x[5] と Pivotを比べます。
Falseなのでループを抜けます。
13行目 Pivot と x[6] を比べます。
Falseなのでループを抜けます。
16行目はFalseなので17行目は実行しません。
19から21行目は三角交換です。
x[ i ] と x[ j ] を交換します。
書き換えなので表に書き込みます。
22行目 i に 1 を足します。
23行目 j から 1 を引きます。
書き換えなので表に書き込みます。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 |
6 | ||
| 3 5 1 4 |
|||
| 3 5 1 4 2 7 6 | 6 | 5 |
10行目に戻って x[6] と Pivot を比べます。
Falseなのでループを抜けます。
13行目 Pivot と x[5] を比べます。
Falseなのでループを抜けます。
16行目はtrueなので17行目でループからbreakします。
25行目 i と k を比べます。
Falseなので26行目は実行しません。
28行目 k と j を比べます。
Trueなので29行目を実行します。
Last が 5 になりました。
２回目の初期値
| Top | Last |
|---|---|
| 1 | 5 |
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 3 5 1 4 2 7 6 | 1 | 1 | 5 |
よって設問1の「a」は「ア」です。
２回目
内側のループの１回目でできる表はこうなります。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 1 | |||
| 1 5 3 4 2 7 6 | 2 | 2 |
さてここが問題の部分です。
さっきと同じであとはループをBreakするだけだろうと思い込み、トレースを省略してしまうと誤回答してしまいます。
プログラムには無駄な行は一行もないので、省略できる処理はありません。全部やりきる覚悟が必要です。
では処理を見てみましょう。
10行目に戻って x[2] と Pivot を比べます。
Falseなのでループを抜けます。
13行目 Pivot と x[2] を比べます。
True!! なので ｊ を書き換えます。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 1 | |||
| 1 5 3 4 2 7 6 | 2 | ||
| 1 |
13行目に戻って Pivot と x[1] を比べます。
Falseなのでループを抜けます。
16行目はtrueなので17行目でループからbreakします。
25行目 i と k を比べます。
Trueなので26行目を実行します。
28行目 k と j を比べます。
Falseなので29行目は実行しません。
Top が 2 になりました。
３回目の初期値
| Top | Last |
|---|---|
| 2 | 5 |
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 1 5 3 4 2 7 6 | 3 | 2 | 5 |
よって設問1の「b」は「ウ」です。
設問はこれで終了ですが、処理を続けます。
３回目
10行目 x[2] と Pivot を比べます。
Falseなのでループを抜けます。
13行目 Pivot と x[5] を比べます。
Falseなのでループを抜けます。
16行目はFalseなので17行目は実行しません。
19から21行目は三角交換です。
x[i] と x[j] を交換します。
22行目、i に 1 を足す。
23行目、ｊ から 1 を引く。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 1 |
3 | ||
| 1 2 3 4 5 7 6 | 3 | 3 | 4 |
10行目 x[3] と Pivot を比べます。
Falseなのでループを抜けます。
13行目 Pivot と x[4] を比べます。
Trueなので ｊ から 1 を引く。
| x[1 2 3 4 5 6 7] | Pivot | i | j |
|---|---|---|---|
| 1 |
3 | ||
| 1 2 3 4 5 7 6 | 3 | 3 | |
| 3 |
13行目 Pivot と x[3] を比べます。
Falseなのでループを抜けます。
16行目はtrueなので17行目でループからbreakします。
25行目 i と k を比べます。
Trueなので26行目を実行します。
28行目 k と j を比べます。
Trueなので29行目を実行します。
Top が 4 、Last が 2 になりました。
４回目の初期値
| Top | Last |
|---|---|
| 4 | 2 |
5行目の Top＜Last がFalseなのでLoopを抜けます。
32行目 x[k] をreturnします。
x[k] は「3」なので、7個のデータの中で3番目に小さい値は「3」です。
ホームに戻るボタン↓
