問題プレビューID: 5d1f526d基本情報技術者試験 午前免除試験 2020年6月14日

問 4
基本情報技術者試験 午前免除試験 2020年6月14日

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

〔手順〕 (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 として手順を実行する。

  • i=2i=2:x2=175÷77x_2 = 175 \div 77 の剰余 =21= 21
  • i=3i=3:x3=77÷21x_3 = 77 \div 21 の剰余 =14= 14
  • i=4i=4:x4=21÷14x_4 = 21 \div 14 の剰余 =7= 7
  • i=5i=5:x5=14÷7x_5 = 14 \div 7 の剰余 =0= 0 → x4=7x_4 = 7 を最大公約数として終了

手順 (2) は i=2,3,4,5i = 2, 3, 4, 5 の 4 回実行される。

  • ア: 剰余が 0 になった回だけを数えた場合などで誤りである。
  • ウ・エ: 手順の実行回数を多く数えすぎている。

関連問題

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