平成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)に戻る。

　ア 　3 　イ 　4 　ウ 　6 　エ 　7

答え　イ

【解説】
手順にそって計算すると

  • 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の最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。

もっと、「ユークリッドの互除法」について調べてみよう。

戻る 一覧へ 次へ