平成24年 秋期 基本情報技術者 午前 問2
与えられた正の整数x0、x1(x0>x1)の最大公約数を、次の手順で求める。
x0 = 175、x1= 77の場合、手順(2)は何回実行するか。
ここで、“A →B ”は、A をB に代入することを表す。
[手順]
| (1) |
2→i |
| (2) |
xi -2をxi -1で、割った剰余→xi |
| (3) |
xi = Oならばxi -1を最大公約数として終了する。 |
| (4) |
i + 1→i として(2)に戻る。 |
|
答え イ
【解説】
手順にそって計算すると
- x0 = 175、x1= 77なので、x2= 21
- x1 = 77、x2= 21なので、x3= 14
- x2 = 21、x3= 14なので、x4= 7
- x3 = 14、x4= 7なので、x5= 10
したがって、最大公約数は7になり、手順(2)は
4回(イ)実行した。
【キーワード】
・ユークリッドの互除法
【キーワードの解説】
- ユークリッドの互除法
2つの自然数(整数)の最大公約数を求める手法。
2つの数(自然数、整数)aとb(a ≥ b)について、aのbによる剰余をrとすると、aとbの最大公約数はbとrの最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。
戻る
一覧へ
次へ