問題プレビューID: 06945713基本情報技術者試験 午前免除試験 2015年7月26日

問 7
基本情報技術者試験 午前免除試験 2015年7月26日

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

解説

正解は「エ」です。

A=876A = 876 を LL,B=204B = 204 を SS に代入し,LL と SS を比較しながら,大きい方から小さい方を引き続けます。

  1. 876 : 204 → L>SL > S,L=876−204=672L = 876 - 204 = 672
  2. 672 : 204 → L>SL > S,L=672−204=468L = 672 - 204 = 468
  3. 468 : 204 → L>SL > S,L=468−204=264L = 468 - 204 = 264
  4. 264 : 204 → L>SL > S,L=264−204=60L = 264 - 204 = 60
  5. 60 : 204 → L<SL < S,S=204−60=144S = 204 - 60 = 144
  6. 60 : 144 → L<SL < S,S=144−60=84S = 144 - 60 = 84
  7. 60 : 84 → L<SL < S,S=84−60=24S = 84 - 60 = 24
  8. 60 : 24 → L>SL > S,L=60−24=36L = 60 - 24 = 36
  9. 36 : 24 → L>SL > S,L=36−24=12L = 36 - 24 = 12
  10. 12 : 24 → L<SL < S,S=24−12=12S = 24 - 12 = 12
  11. 12 : 12 → L=SL = S,比較が終了し,最大公約数 12 を出力して処理を終了する。

したがって,比較の回数は 11 回であり,「エ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています