《機械》〈情報伝送及び処理〉[R2:問18]数値を並べ替えるプログラムのフローチャートに関する論説問題

【問題】

【難易度】★★★★★（難しい）

図は\( \ \mathrm {n} \ \)個の配列の数値を大きい順（降順）に並べ替えるプログラムのフローチャートである。次の(a)及び(b)の問に答えよ。

(a)　図中の（ア）～（ウ）に当てはまる処理の組合せとして，正しいものを次の(1)～(5)のうちから一つ選べ。

\[
\begin{array}{cccc}
& （ア） & （イ） & （ウ） \\
\hline
(1) & 　\mathrm {a[i]}＞\mathrm {a[j]}　 & 　\mathrm {a[j]}←\mathrm {a[i]}　 & 　\mathrm {a[i]}←\mathrm {m}　 \\
\hline
(2) & 　\mathrm {a[i]}＞\mathrm {a[j]}　 & 　\mathrm {a[i]}←\mathrm {a[j]}　 & 　\mathrm {a[j]}←\mathrm {m}　 \\
\hline
(3) & 　\mathrm {a[i]}＜\mathrm {a[j]}　 & 　\mathrm {a[j]}←\mathrm {a[i]}　 & 　\mathrm {a[i]}←\mathrm {m}　 \\
\hline
(4) & 　\mathrm {a[i]}＜\mathrm {a[j]}　 & 　\mathrm {a[j]}←\mathrm {a[i]}　 & 　\mathrm {a[j]}←\mathrm {m}　 \\
\hline
(5) & 　\mathrm {a[i]}＜\mathrm {a[j]}　 & 　\mathrm {a[i]}←\mathrm {a[j]}　 & 　\mathrm {a[j]}←\mathrm {m}　 \\
\hline
\end{array}
\]

(b)　このプログラム実行時の読込み処理において，\( \ \mathrm {n}=5 \ \)とし，\( \ \mathrm {a[1]}=3 \ \)，\( \ \mathrm {a[2]}=1 \ \)，\( \ \mathrm {a[3]}=2 \ \)，\( \ \mathrm {a[4]}=5 \ \)，\( \ \mathrm {a[5]}=4 \ \)とする。フローチャート中の\( \ \mathrm {X} \ \)で示される部分の処理は何回行われるか。正しいものを次の(1)～(5)のうちから一つ選べ。

　(1)　\( \ 3 \ \)　　(2)　\( \ 5 \ \)　　(3)　\( \ 7 \ \)　　(4)　\( \ 8 \ \)　　(5)　\( \ 10 \ \)

【ワンポイント解説】

コンピュータ内で行われるプログラムに関する問題ですが，まともに解くと非常に時間がかかる問題です。
分野も特殊であることから，一般の電験受験生だとまず選択しない問題と言えると思います。
ただし，平成29年問18にほぼ同じアルゴリズムの問題が出題されているので，過去問を抑えている方であれば，ある程度類推できる問題となるかもしれません。

【解答】

(a)解答：(5)
(ア)
\( \ \mathrm {a[i]} \ \)と\( \ \mathrm {a[j]} \ \)の大きさを比較して，\( \ \mathrm {YES} \ \)の場合は入れ替えて，\( \ \mathrm {NO} \ \)の場合は入れ替えないという操作です。
したがって，本問において降順に並べるということなので，\( \ \mathrm {a[i]} ＜ \mathrm {a[j]} \ \)の時入れ替える必要があるので，\( \ \mathrm {a[i]} ＜ \mathrm {a[j]} \ \)となります。

(イ)
\( \ \mathrm {a[i]} \ \)を一旦\( \ \mathrm {m} \ \)にした後，\( \ \mathrm {a[j]} \ \)を\( \ \mathrm {a[i]} \ \)にする必要があるので，\( \ \mathrm {a[i]}←\mathrm {a[j]} \ \)となります。

(ウ)
最終的に\( \ \mathrm {a[i]} \ \)と\( \ \mathrm {a[j]} \ \)を入れ替える必要があるので，\( \ \mathrm {m} \ \)に移した元々の\( \ \mathrm {a[i]} \ \)を\( \ \mathrm {a[j]} \ \)とする必要があります。したがって，\( \ \mathrm {a[j]}←\mathrm {m} \ \)となります。

(b)解答：(3)
下記プログラムの赤字の通り，\( \ \mathrm {X} \ \)の回数は7回です。

図1のように各プロセスに番号をつけ，アルゴリズムに沿って解いていきます。
①\( \ \mathrm {n} \ \)を「読込み」します。⇒\( \ \mathrm {n}=5 \ \)
②\( \ \mathrm {a}[1] \ ～ \ \mathrm {a}[\mathrm {n}] \ \)を「読込み」します。⇒\( \ \mathrm {a}[1]=3 \ \)，\( \ \mathrm {a}[2]=1 \ \)，\( \ \mathrm {a}[3]=2 \ \)，\( \ \mathrm {a}[4]=5 \ \)，\( \ \mathrm {a}[5]=4 \ \)
③\( \ \mathrm {i} \ \)を\( \ 1 \ \)とします。⇒\( \ \mathrm {i}=1 \ \)
④\( \ \mathrm {j} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {j}=2 \ \)
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[1]=3＞\mathrm {a}[2]=1 \ \)なので\( \ \mathrm {NO} \ \)へ
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=3 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=3＜\mathrm {n}=5 \ \)なので\( \ \mathrm {NO} \ \)へ
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[1]=3＞\mathrm {a}[3]=2 \ \)なので\( \ \mathrm {NO} \ \)へ
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=4 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=4＜\mathrm {n}=5 \ \)なので\( \ \mathrm {NO} \ \)へ
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[1]=3＜\mathrm {a}[4]=5 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[1]=5 \ \)，\( \ \mathrm {a}[4]=3 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=5 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=5＝\mathrm {n}=5 \ \)なので\( \ \mathrm {NO} \ \)へ
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[1]=5＞\mathrm {a}[5]=4 \ \)なので\( \ \mathrm {NO} \ \)へ
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=6 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=6＞\mathrm {n}=5 \ \)なので\( \ \mathrm {YES} \ \)へ
⑨\( \ \mathrm {i} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {i}=2 \ \)
⑩\( \ \mathrm {i}＞\mathrm {n}-1 \ \)かどうかを確認します。⇒\( \ \mathrm {i}=2＜\mathrm {n}-1=4 \ \)なので\( \ \mathrm {NO} \ \)へ
④\( \ \mathrm {j}\)を\( \ \mathrm {i}+1\)とします。⇒\( \ \mathrm {j}=3 \ \)
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[2]=1＜\mathrm {a}[3]=2 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[2]=2 \ \)，\( \ \mathrm {a}[3]=1 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=4 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=4＜\mathrm {n}=5 \ \)なので\( \ \mathrm {NO} \ \)へ
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\ \mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[2]=2＜\mathrm {a}[4]=3 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[2]=3 \ \)，\( \ \mathrm {a}[4]=2 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=5 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=5＝\mathrm {n}=5 \ \)なので\( \ \mathrm {NO} \ \)へ
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[2]=3＜\mathrm {a}[5]=4 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[2]=4 \ \)，\( \ \mathrm {a}[5]=3 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=6 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=6＞\mathrm {n}=5 \ \)なので\( \ \mathrm {YES} \ \)へ
⑨\( \ \mathrm {i} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {i}=3 \ \)
⑩\( \ \mathrm {i}＞\mathrm {n}-1 \ \)かどうかを確認します。⇒\( \ \mathrm {i}=3＜\mathrm {n}-1=4 \ \)なので\( \ \mathrm {NO} \ \)へ
④\( \ \mathrm {j} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {j}=4 \ \)
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[3]=1＜\mathrm {a}[4]=2 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[3]=2 \ \)，\( \ \mathrm {a}[4]=1 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=5 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=5＝\mathrm {n}=5 \ \)なので\( \ \mathrm {NO} \ \)へ
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[3]=2＜\mathrm {a}[5]=3 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[3]=3 \ \)，\( \ \mathrm {a}[5]=2 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=6 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=6＞\mathrm {n}=5 \ \)なので\( \ \mathrm {YES} \ \)へ
⑨\( \ \mathrm {i} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {i}=4 \ \)
⑩\( \ \mathrm {i}＞\mathrm {n}-1 \ \)かどうかを確認します。⇒\( \ \mathrm {i}=4＝\mathrm {n}-1=4 \ \)なので\( \ \mathrm {NO} \ \)へ
④\( \ \mathrm {j} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {j}=5 \ \)
⑤\( \ \mathrm {a}[\mathrm {i}]＜\mathrm {a}[\mathrm {j}] \ \)かどうかを確認します。⇒\( \ \mathrm {a}[4]=1＜\mathrm {a}[5]=2 \ \)なので\( \ \mathrm {YES} \ \)へ
⑥\( \ \mathrm {m} \ \)を\( \ \mathrm {a}[\mathrm {i}] \ \)として\( \ \mathrm {a}[\mathrm {i}] \ \)を\( \ \mathrm {a}[\mathrm {j}] \ \)として\( \ \mathrm {a}[\mathrm {j}] \ \)を\( \ \mathrm {m} \ \)とします。⇒\( \ \mathrm {a}[4]=2 \ \)，\( \ \mathrm {a}[5]=1 \ \)
⑦\( \ \mathrm {j} \ \)を\( \ \mathrm {j}+1 \ \)とします。⇒\( \ \mathrm {j}=6 \ \)
⑧\( \ \mathrm {j}＞\mathrm {n} \ \)かどうかを確認します。⇒\( \ \mathrm {j}=6＞\mathrm {n}=5 \ \)なので\( \ \mathrm {YES} \ \)へ
⑨\( \ \mathrm {i} \ \)を\( \ \mathrm {i}+1 \ \)とします。⇒\( \ \mathrm {i}=5 \ \)
⑩\( \ \mathrm {i}＞\mathrm {n}-1 \ \)かどうかを確認します。⇒\( \ \mathrm {i}=5＞\mathrm {n}-1=4 \ \)なので\( \ \mathrm {YES} \ \)へ
⑪\( \ \mathrm {a}[1]～\mathrm {a}[\mathrm {n}] \ \)を「出力」します。⇒\( \ \mathrm {a}[1]=5 \ \)，\( \ \mathrm {a}[2]=4 \ \)，\( \ \mathrm {a}[3]=3 \ \)，\( \ \mathrm {a}[4]=2 \ \)，\( \ \mathrm {a}[5]=1 \ \)