アルゴリズム (全70問中24問目)

No.24

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

〔手順〕
  • 2→i
  • xi−2をxi−1で,割った剰余→xi
  • xi=Oならばxi−1を最大公約数として終了する。
  • i+1→i として(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-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop