基本情報技術者試験 過去問解説
ユークリッドの互除法とは？基本情報技術者試験 平成31年度 春期 午前 問7を解説
基本情報技術者試験 平成31年度 春期 午前 問7は、ユークリッドの互除法に関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
次の流れ図は，2 数 A, B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。A が 876, B が 204 のとき，何回の比較で処理は終了するか。
この問題の出題ポイント
- ユークリッドの互除法の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- 関連タグ: 数学、数値計算。
選択肢
- ア4
- イ9
- ウ10
- エ11正解
正解
エ: 11
解説
L=876, S=204 から大きい方から小さい方を引く操作を繰り返す。876→672→468→264→60 (4回, L>Sのループ)、次に S を減らす: 204→144→84→24 (3回, L<Sのループ)、再びL>S: 60→36→12 (2回)、再びL<S: 24→12 (1回)、L=S=12で=判定で終了 (1回)。比較回数の合計は 4+3+2+1+1 = 11。エが正解。
解き方の整理
ユークリッドの互除法の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連問題
前後の問題
平成31年度 春期 午前 の関連する問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。