問題プレビューID: ae08c225基本情報技術者試験 午前免除試験 2022年6月12日

問 5
基本情報技術者試験 午前免除試験 2022年6月12日

与えられた正の整数 x0,x1x_0, x_1(x0>x1x_0 > x_1)の最大公約数を,次の手順で求める。x0=175x_0 = 175,x1=77x_1 = 77 の場合,手順 (2) は何回実行するか。ここで,"A ← B" は,B を A に代入することを表す。

〔手順〕

  1. i←2i \leftarrow 2
  2. xi←x_i \leftarrow "xi−2x_{i-2} を xi−1x_{i-1} で割った剰余"
  3. xi=0x_i = 0 ならば xi−1x_{i-1} を最大公約数として終了する。
  4. "i←i+1i \leftarrow i + 1" として (2) に戻る。
解説

正解は「イ」です。

x0=175x_0 = 175,x1=77x_1 = 77 として,手順 (2) の計算を順に進めます。

  1. i=2i = 2:x2=175 mod 77=21x_2 = 175 \bmod 77 = 21
  2. i=3i = 3:x3=77 mod 21=14x_3 = 77 \bmod 21 = 14
  3. i=4i = 4:x4=21 mod 14=7x_4 = 21 \bmod 14 = 7
  4. i=5i = 5:x5=14 mod 7=0x_5 = 14 \bmod 7 = 0 → 最大公約数は x4=7x_4 = 7 として終了

手順 (2) は i=2,3,4,5i = 2, 3, 4, 5 の 4 回実行されるので,「イ」が正解です。

  • ア・ウ・エ: 剰余計算の回数を数え誤った値です。

関連問題

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