問 題
図は、二つの自然数 a,b(a ≧ b) の最大公約数を求めるユークリッドの互除法のフローチャートである。ユークリッドの互除法は、次の考え方に基づくものである。
自然数 p,q (p ≧ q) について
・p が q で割り切れるとき、p と q の最大公約数は、q に等しい。
・p を q で割った余りが r のとき、p と q の最大公約数は、q と r の最大公約数に等しい。
図の ㋐、㋑ に当てはまるものの組合せとして最も妥当なのはどれか。
正解．5
解 説
入力の一例として、a = 21, b = 14 を入力します。最大公約数である 7 が出力されるように選択肢を検討します。
(M,N,L) = (21,14,7)y
(M,N,L) = (21,14,-7)nn
ここでもし ㋐ が M ← M + N だと、M が大きくなります。チャートの戻る場所を考えても、入力として 別の数値（この例でいえば 21 + 14 = 35）を代入したような流れになってしまうため、明らかに誤りと考えられます。
また、㋑ ですが、最終的に出力するのが N なので、N ← L だと、このままでは負の数になってしまいおかしい印象です。よって、N ← N + L が適切と思われます。
㋐ が M ← N、㋑ N ← N + L として、具体的に確認してみると
(M,N,L) =（14,7,-7）
(M,N,L) =（14,7,7）y
(M,N,L) =（14,7,0）ny → 7 を出力 となり、妥当と考えられます。
以上より、正解は 5 です。
コメント