基本情報技術者令和4年免除 問7

問7

与えられた正の整数x0,x1(x0>x1)の最大公約数を,次の手順で求める。x0=175,x1=77の場合,手順(2)は何回実行するか。ここで,"A→B"は,AをBに代入することを表す。

〔手順〕
  • 2→i
  • xi-2をxi-1で,割った剰余→xi
  • xi=0ならばxi-1を最大公約数として終了する。
  • i+1→i として(2)に戻る。
  • 3
  • 4
  • 6
  • 7
  • [出典]
  • 午前免除試験 R4-6月 問5
  • 基本情報技術者 H24 問2と同題

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

問題文の手順に従って処理をトレースしていきます。
  1. x0=175、x1=77
  2. (1) 2 → i //i=2
  3. (2) 1回目
    x0÷x1=175÷77=2 余り 21
    21 → x2 //x2=21
  4. (3) x2は0ではないので処理続行
  5. (4) i+1=2+1 → i //i=3
  6. (2) 2回目
    x1÷x2=77÷21=3 余り 14
    14 → x3 //x3=14
  7. (3) x3は0ではないので処理続行
  8. (4) i+1=3+1 → i //i=4
  9. (2) 3回目
    x2÷x3=21÷14=1 余り 7
    7 → x4 //x4=7
  10. (3) x4は0ではないので処理続行
  11. (4) i+1=4+1→i //i=5
  12. (2) 4回目
    x3÷x4=14÷7=2
    0 → x5 //x5=0
  13. (3) x5は0なので処理終了
    最大公約数=x4=7
したがって手順(2)が実行される回数は4回です。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop