《機械》〈情報伝送及び処理〉[H29:問18]アルゴリズムに関する論説問題

【問題】

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

図のフローチャートで表されるアルゴリズムについて，次の(a)及び(b)の問に答えよ。変数は全て整数型とする。
このアルゴリズム実行時の読込み処理において，\( \ \mathrm {n}=5 \ \)とし，\( \ \mathrm {a}[1]=2 \ \)，\( \ \mathrm {a}[2]=3 \ \)，\( \ \mathrm {a}[3]=8 \ \)，\( \ \mathrm {a}[4]=6 \ \)，\( \ \mathrm {a}[5]=5 \ \)とする。

(a)　図のフローチャートで表されるアルゴリズムの機能を考えて，出力される\( \ \mathrm {a}[5] \ \)の値を求めよ。その値として正しいものを次の(1)～(5)のうちから一つ選べ。

　(1)　\( \ 2 \ \)　　(2)　\( \ 3 \ \)　　(3)　\( \ 5 \ \)　　(4)　\( \ 6 \ \)　　(5)　\( \ 8 \ \)

(b)　フローチャート中の\( \ \mathrm {X} \ \)で示される部分の処理は何回行われるか。正しいものを次の(1)～(5)のうちから一つ選べ。

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

【ワンポイント解説】

アルゴリズムの問題でパズルゲームを解いているような問題です。ただし，問題を解くのにかなりの時間を要する上，ケアレスミスも発生しやすい問題なので，９０分しかない試験時間でこの問題は選択しない方が良いと思います。

【解答】

(a)解答：(5)
下記プログラムの青字の通り，出力される\( \ \mathrm {a}[5] \ \)は\( \ 8 \ \)となります。

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

図1のように各プロセスに番号をつけ，アルゴリズムに沿って解いていきます。
①\( \ \mathrm {n} \ \)を「読込み」します。⇒\( \ \mathrm {n}=5 \ \)
②\( \ \mathrm {a}[1] \ ～ \ \mathrm {a}[\mathrm {n}] \ \)を「読込み」します。⇒\( \ \mathrm {a}[1]=2 \ \)，\( \ \mathrm {a}[2]=3 \ \)，\( \ \mathrm {a}[3]=8 \ \)，\( \ \mathrm {a}[4]=6 \ \)，\( \ \mathrm {a}[5]=5 \ \)
③\( \ \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]=2＜\mathrm {a}[2]=3 \ \)なので\( \ \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]=2＜\mathrm {a}[3]=8 \ \)なので\( \ \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]=2＜\mathrm {a}[4]=6 \ \)なので\( \ \mathrm {NO} \ \)へ
⑦\( \ \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]=2＜\mathrm {a}[5]=5 \ \)なので\( \ \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]=3＜\mathrm {a}[3]=8 \ \)なので\( \ \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}[2]=3＜\mathrm {a}[4]=6 \ \)なので\( \ \mathrm {NO} \ \)へ
⑦\( \ \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]=5 \ \)なので\( \ \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}=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]=8＞\mathrm {a}[4]=6 \ \)なので\( \ \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]=6 \ \)，\( \ \mathrm {a}[4]=8 \ \)
⑦\( \ \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]=6＞\mathrm {a}[5]=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}[3]=5 \ \)，\( \ \mathrm {a}[5]=6 \ \)
⑦\( \ \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]=8＞\mathrm {a}[5]=6 \ \)なので\( \ \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]=6 \ \)，\( \ \mathrm {a}[5]=8 \ \)
⑦\( \ \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]=2 \ \)，\( \ \mathrm {a}[2]=3 \ \)，\( \ \mathrm {a}[3]=5 \ \)，\( \ \mathrm {a}[4]=6 \ \)，\( \ \mathrm {a}[5]=8 \ \)