前処理
S[ ] の初期値は NULL
N は 5
K は 3
これらの値を入れてプログラム「Init」を走らせます。
Lの初期値が 1 で N になるまで繰り返します。
L が 1 で K 以下なので S[1] に 1 をいれます。
L が 2 で K 以下なので S[2] に 1 をいれます。
L が 3 で K 以下なので S[3] に 1 をいれます。
L が 4 で K より大きいので S[4] に 0 をいれます。
L が 5 で K より大きいので S[5] に 0 をいれます。
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 1 | 1 | 5 | 3 |
| 1 1 | 2 | ||
| 1 1 1 | 3 | ||
| 1 1 1 0 | 4 | ||
| 1 1 1 0 0 | 5 |
プログラム「Init」は 配列S の最初の N個 の数値のうち K個 に 1 をいれ、残りに 0 をいれるプログラムです。
ループ1回目
プログラム「Init」が 0 を返してくるので、これを R の初期値としています。
ここから、 R が 0 の間、プログラム「Next」を呼び続けます。
初期値は
Sが「1 1 1 0 0」、L が 1 、C が 0 です。
S[1] が 1 、S[1+1] が 1 なので判定の下の処理をします。
C に 1 を足します。
L に 1 を足してループします。
S[2] が 1 、S[2+1] が 1 なので判定の下の処理をします。
C に 1 を足します。
L に 1 を足してループします。
S[3] が 1 、S[3+1] が 0 なので判定の上の処理をします。
S[3] に 0 、S[3+1] に 1 をいれます。
これはいれかえるということです。
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 1 1 1 0 0 | 1 | 0 |
| 2 | 1 | |
| 3 | 2 | |
| 1 1 0 1 0 |
そして「S[ ]」と「L-1」と「C」をいれてプログラム「Init」を走らせます。
このとき「L-1」はいれかえた数列よりも前の数列の数、 「C」はいれかえた数列よりも前の数列のうち、 1 である数のことです。
この場合、3番目と4番目をいれかえたので、「L-1」は 2 、
1番目と2番目の数値は両方とも 1 なので「C」は 2 です。
プログラム「Init」では「L-1」は「N」、「C」は「K」と名前が変わります。
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 1 1 0 1 0 | 2 | 2 | |
| 1 1 0 1 0 | 1 | ||
| 1 1 0 1 0 | 2 |
この場合 Sは 変化しませんでした。
ループ2回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 1 1 0 1 0 | 1 | 0 |
| 2 | 1 | |
| 1 0 1 1 0 |
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 1 0 1 1 0 | 1 | 1 | |
| 1 0 1 1 0 | 1 |
ループ3回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 1 0 1 1 0 | 1 | 0 |
| 0 1 1 1 0 |
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 0 1 1 1 0 | 0 | 0 |
ループ4回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 0 1 1 1 0 | 1 | 0 |
| 2 | ||
| 3 | 1 | |
| 4 | 2 | |
| 0 1 1 0 1 |
4番目と5番目をいれかえたので、「L-1」は 3 、「C」は 2 なので プログラム「init」によって配列Ｓが変化します。
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 0 1 1 0 1 | 3 | 2 | |
| 1 1 1 0 1 | 1 | ||
| 1 1 1 0 1 | 2 | ||
| 1 1 0 0 1 | 3 |
ループ5回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 1 1 0 0 1 | 1 | 0 |
| 2 | 1 | |
| 1 0 1 0 1 |
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 1 0 1 0 1 | 1 | 1 | |
| 1 0 1 0 1 | 1 |
ループ6回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 1 0 1 0 1 | 1 | 0 |
| 0 1 1 0 1 |
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 0 1 1 0 1 | 0 | 0 |
ループ7回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 0 1 1 0 1 | 1 | 0 |
| 2 | ||
| 3 | 1 | |
| 0 1 0 1 1 |
3番目と4番目をいれかえたので、「L-1」は 2 、「C」は 1 なので プログラム「init」によって配列Ｓが変化します。
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 0 1 0 1 1 | 2 | 1 | |
| 1 1 0 1 1 | 1 | ||
| 1 0 0 1 1 | 2 |
ループ8回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 1 0 0 1 1 | 1 | 0 |
| 0 1 0 1 1 |
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 0 1 0 1 1 | 0 | 0 |
ループ9回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 0 1 0 1 1 | 1 | 0 |
| 2 | ||
| 0 0 1 1 1 |
| S[1 2 3 4 5] | L | N | K |
|---|---|---|---|
| 0 0 1 1 1 | 1 | 0 |
ループ10回目
| S[1 2 3 4 5] | L | C |
|---|---|---|
| 0 0 1 1 1 | 1 | 0 |
| 2 | ||
| 3 | ||
| 4 | 1 | |
| 5 | 2 | |
| 6 | 3 |
L が N より大きくなったのでループを抜け R を return します。
このとき R は -1 です。
後処理
主プログラムに戻ったとき R が -1 なのでループを抜けプログラムを終了します。
設問の答
空欄「a」は「ア」です。
「イ」は、初期値を Dump する前に上書きしてしまうので間違いです。
「ウ」は、一見これでも正解に見えますが、S「0 0 1 1 1」がプログラム「Init」から帰ってきたときと、プログラム「Init」に送り損ねたときとを合わせて 2 回 Dump してしまうので間違いです。
「エ」も、S「0 0 1 1 1」を 2 回 Dump してしまうので間違いです。
空欄「b」は「エ」です。
空欄「c」は「エ」です。
空欄「d」は「ア」です。
「Nの値」の範囲は「L-1」で、「いれかえた数列よりも前の数列の数」のことですから最小は 0 、 最大は 3 です。
空欄「e」は「イ」です。
「Kの値」の範囲は「C」で、いれかえた数列には 1 が 必ず 1個 含まれているので最大でも残り 2個、最小は 0 です。
空欄「f」は「ア」です。
空欄「g」は「イ」です。
ホームに戻るボタン↓
