《機械》〈情報伝送及び処理〉[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[5]}=2 \ \),\( \ \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 \ \)