ユークリッド互除法の流れ図における実行経路と初期値関係

正解は「エ」です。 本問の流れ図は、2 つの正の整数 $a$ と $b$ の最大公約数を減算によって求めるユークリッドの互除法です。 指定された実行経路 ①→②→③→⑤→②→③→④→②→⑥ に沿って、$m$ と $n$ の値の変化をトレースします。 【各ステップのトレース】 1. 初期処理 ①: $m = a$、$n = b$ を代入します。 2. 1 回目のループ(②→③→⑤): ②で $m = n$ を判定:偽(等しくない)となり ③ へ進む。 ③で $m > n$ を判定:⑤に進んでいるため判定は「No(偽)」、すなわち $m < n$ です。 初期値より $a < b$ が成り立ちます。 ⑤を実行:$n \leftarrow n - m$ より、更新後の値は $n = b - a$、$m = a$ となります。 3. 2 回目のループ(②→③→④): ②で $m = n$ を判定:偽となり ③ へ進む。 ③で $m > n$ を判定:④に進んでいるため判定は「Yes(真)」、すなわち $m > n$ です。 現在の値より $a > b - a \iff 2a > b$ が成り立ちます。 ④を実行:$m \leftarrow m - n$ より、更新後の値は $m = a - (b - a) = 2a - b$、$n = b - a$ となります。 4. 終了処理(②→⑥): ②で $m = n$ を判定:⑥に進んで終了しているため判定は「Yes(真)」、すなわち $m = n$ です。 $2a - b = b - a$ $3a = 2b$ したがって、初期値の関係は「$3a = 2b$」となります。 実行した処理 m n 判定 ① m←a, n←b 4 6 ② → ③ 4 6 m≠n、m<n なので⑤ ⑤ n←n−m 4 2 ② → ③ 4 2 m≠n、m>n なので④ ④ m←m−n 2 2 ② → ⑥ 2 2 m=n なので印字して終了 例えば $3a=2b$ を満たす a=4, b=6 で流れ図をたどると、指定どおり ⑤ → ④ → ⑥ の順に進みます。

次の流れ図において,①→②→③→⑤→②→③→④→②→⑥ の順に実行させるために,①において mm と nn に与えるべき初期値 aa と bb の関係はどれか。ここで,aa,bb はともに正の整数とする。

問題画像
出典令和2年度 10月 応用情報技術者試験 午前 問47
ア
a=2ba = 2b
イ
2a=b2a = b
ウ
2a=3b2a = 3b
エ
3a=2b3a = 2b