問題プレビューID: 3c673cf1基本情報技術者試験 午前免除試験 2018年1月28日

問 3
基本情報技術者試験 午前免除試験 2018年1月28日

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

〔手順〕

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

正解は「イ」です。

ユークリッドの互除法の手順を x0=175x_0 = 175,x1=77x_1 = 77 で順に追います。

  • i=2i = 2:175175 を 7777 で割った剰余は 175−77×2=21175 - 77 \times 2 = 21 なので x2=21x_2 = 21(1 回目)
  • i=3i = 3:7777 を 2121 で割った剰余は 77−21×3=1477 - 21 \times 3 = 14 なので x3=14x_3 = 14(2 回目)
  • i=4i = 4:2121 を 1414 で割った剰余は 21−14×1=721 - 14 \times 1 = 7 なので x4=7x_4 = 7(3 回目)
  • i=5i = 5:1414 を 77 で割った剰余は 00 なので x5=0x_5 = 0(4 回目)となり,手順 (3) で終了する。

したがって,手順 (2) は 4 回実行されます。

  • ア: 3 回では剰余が 0 になる手順まで到達しません。
  • イ: 上記のとおり 4 回で正しい値です。
  • ウ: 6 回は実行しません。
  • エ: 7 回は実行しません。

関連問題

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