基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成24年 秋期 基本情報技術者 午前 問02
問02   最大公約数の計算

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

[手順]

(1) 2 → i
(2) xi-2 を xi-1 で割った剰余 → xi
(3) xi =0 ならば xi-1 を最大公約数として終了する。
(4) i+1 → i として (2) に戻る。

ア 3       イ 4       ウ 6       エ 7
解答←クリックすると正解が表示されます

解説

 ユークリッドの互除法による最大公約数を求める問題である。

 (2) の計算は、以下のようになる。ここで%は、剰余を求める演算である。

  1. 175 % 77 = 21
  2. 77 % 21 = 14
  3. 21 % 14 = 7
  4. 14 % 7 = 0
 よって、手順 (2) は4回実行する。

[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]