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

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

出典:平成31年春期 問 7

  • 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