応用情報技術者試験 応用情報技術者試験 平成29年度春期 午前 問6: 次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返

正解

イ. a と b の最大公約数

正答率 57.4%（774人中 444人が正解）

問題の解説

この流れ図は剰余（mod）を使ったユークリッドの互除法そのもので、最大公約数（GCD）を求めるアルゴリズムである。x←a、y←b から始め、yが0になるまで「t←mod(x,y)（余り）、x←y、y←t」を繰り返すと、最後にxに最大公約数が残る。よって正解はイ。具体例ではa=12,b=8のとき、mod(12,8)=4→(x,y)=(8,4)、mod(8,4)=0→(x,y)=(4,0)で終了し、x=4＝gcd(12,8)となる。

選択肢ごとの解説

• ア最小公倍数はこの手順では求まらない。互除法は剰余を用いて公約数を縮約していく処理で、結果は最大公約数である。誤り。
• イ正しい。yが0になった時点でxに残る値が最大公約数。これは剰余を使ったユークリッドの互除法の定義どおりの動作である。
• ウ素数を探す処理（割り切れるかの試し割りなど）は含まれておらず、素数とは無関係。誤り。
• エ商を求めるなら除算や減算回数の計数が必要だが、この流れ図は余りを次の割られる数に渡す互除法であり商は得られない。誤り。