平成15年秋期試験問題 午前問15

次の流れ図は,2数 A,Bの最大公約数を求めるユークリッドの互除法を,引き算の繰返しによって計算するものである。 Aが876,Bが204のとき,何回の比較で処理は終了するか。
15.png

  • 4
  • 9
  • 10
  • 11
正解 問題へ
分野 :テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
問題文の流れ図を比較回数に注目しながらトレース(追跡)していくと次のようになります。
  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回です。

この問題の出題歴


Pagetop