アルゴリズム (全79問中50問目)

No.50

次の流れ図は,2数 A,Bの最大公約数を求めるユークリッドの互除法を,引き算の繰返しによって計算するものである。 Aが876,Bが204のとき,何回の比較で処理は終了するか。
15.gif/image-size:319×247
  • 4
  • 9
  • 10
  • 11
  • [出題歴]
  • 基本情報技術者 H15秋期 問15
  • 基本情報技術者 H31春期 問7

分類

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

正解

解説

問題文の流れ図を比較回数に注目しながらトレース(追跡)していくと次のようになります。
  1. (開始時にL←876,S←204で初期化)
    876>204 … L←876−204=672
  2. 672>204 … L←672−204=468
  3. 468>204 … L←468−204=264
  4. 264>204 … L←264−204=60
  5. 60<204 … S←204−60=144
  6. 60<144 … S←144−60=84
  7. 60<84 … S←84−60=24
  8. 60>24 … L←60−24=36
  9. 36>24 … L←36−24=12
  10. 12<24 … S←24−12=12
  11. 12=12 … A,B,Lの出力
処理終了までの比較回数は上記のように11回です。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop