応用情報技術者試験 応用情報技術者試験 令和2年度 午前 問47: 次の流れ図において， ①→②→③→⑤→②→③→④→②→⑥ の順に実行させるために，①において m と n に与えるべき初期値 a と b の関係はどれか。ここで

問題本文

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

選択肢

• ア.a = 2b
• イ.2a = b
• ウ.2a = 3b
• エ.3a = 2b

正解

エ. 3a = 2b

解説

この流れ図は、m と n が等しくなるまで大きい方から小さい方を引き続ける、減算によるユークリッドの互除法(互減算法)である。②は m=n なら⑥へ・異なれば③へ、③は mn なら④(m←m−n)・m<n なら⑤(n←n−m)へ進む。指定された実行順を1ステップずつ追い、最後に m=n となる条件を立式すると正解が定まる。初期値 m=a, n=b から順にたどると③で<を通る(⑤実行)ので a<b、次の③でを通る(④実行)ので不等式が定まり、最後の②で m=n となる関係 3a=2b が導けるため、エが正解である。

選択肢ごとの解説

• ア.a=2b では ab となり、最初の③で mn(分岐=④)へ進んでしまい、指定された③→⑤(<分岐)の順序と矛盾するので誤り。
• イ.2a=b すなわち b=2a で m=a,n=2a を代入すると、1回目の⑤後に m=a,n=a となり2回目の②で即終了(⑥)してしまい、その後の③→④の手順が現れないので誤り。
• ウ.2a=3b すなわち a=1.5b で代入すると ab となり、最初の③が分岐(④)になってしまい、指定の③→⑤(<分岐)と矛盾するので誤り。
• エ.3a=2b では a<b(1回目の③が<分岐=⑤で n←b−a)かつ 2ab(2回目の③が分岐=④で m←a−(b−a)=2a−b)となり、その後 m=2a−b と n=b−a が等しく(2a−b=b−a すなわち3a=2b)なって②で⑥へ進むため、指定の実行順と完全に一致し正しい。