応用情報技術者 2017年 春期 午前2 問06

流れ図の処理で終了時の$x$に格納されているものは何か【午前2 解説】

要点まとめ

• 結論：終了時の$x$には$a$と$b$の最大公約数（GCD）が格納されている。
• 根拠：流れ図はユークリッドの互除法を実装しており、$x$と$y$に余りを繰り返し代入しているため。
• 差がつくポイント：$mod(x,y)$の意味とループ条件「$y=0$」の役割を正確に理解し、最大公約数の求め方を把握すること。

正解の理由

1. $t\leftarrow mod(x,y)$（$x$を$y$で割った余りを$t$に代入）
2. $x\leftarrow y$
3. $y\leftarrow t$

よくある誤解

• $mod(x,y)$の余りを単なる割り算の結果と誤解し、最大公約数の意味を取り違えることがあります。
• ループの終了条件「$y=0$」を見落とし、処理が何を求めているか理解できない場合があります。

解法ステップ

1. 流れ図の初期設定で$x=a$、$y=b$とすることを確認する。
2. ループの条件「$y=0$」を理解し、$y$が0になるまで処理を繰り返すことを把握する。
3. ループ内で$t=mod(x,y)$を計算し、$x$に$y$を、$y$に$t$を代入する処理を追う。
4. この処理がユークリッドの互除法であることを認識する。
5. ループ終了時の$x$が最大公約数であることを結論づける。

選択肢別の誤答解説

• ア: 最小公倍数は最大公約数とは異なり、互除法の処理では求められません。
• イ: 最大公約数はユークリッドの互除法の結果であり正解です。
• ウ: 小さい方に最も近い素数はこの処理とは無関係で、素数判定もしていません。
• エ: 商は割り算の結果であり、余りを使うこの処理とは異なります。

補足コラム

FAQ