基本情報技術者平成31年春期 午前問7

午前問7

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

分類

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

正解

解説

問題文の流れ図を比較回数に注目しながらトレース(追跡)していくと、次のようになります。
  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-2019 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop