平成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) の計算は、以下のようになる。ここで%は、剰余を求める演算である。
- 175 % 77 = 21
- 77 % 21 = 14
- 21 % 14 = 7
- 14 % 7 = 0
よって、手順 (2) は4回実行する。
|
[←前の問題]
[次の問題→]
[問題一覧表]
[分野別]
[キーワード索引]
[基本情報技術者試験TOP
]
©2004-2023
|
|
|