平成21年 春期 ITパスポート 問72

図1のように二つの正の数値A1、A2を読み取り、二つの数値B1、B2を出力するボックスがある。
B1にはA2と同じ数値を出力し、B2にはA1をA2で割った余りを出力する。
図2のようにボックスを2個つないだ場合、A1=15、A2=6のとき後方のボックスのB1に出力される数値は幾らか。

 ア  0  イ  3  ウ  6  エ  15


答え イ


解説
A1=15、A2=6を入力とした時、図2の前方のボックスの出力B1、B2を求める、『A2→B1』なのでB1=6、『A1/A2の余り→B2』なのでB2=3になる。
さらに、この出力が後方のボックスの入力になるのでA1=B1=6、A2=B2=3で出力を求めるとB1=3、B2=0(イ)になる。

B2=0となったときのB1の値は、最初の入力値A1、A2の最大公約数になります。(ユークリッドの互除法)


キーワード
・ユークリッドの互除法

キーワードの解説
  • ユークリッドの互除法
    2つの自然数(整数)の最大公約数を求める手法。
    2つの数(自然数、整数)aとb(a ≥ b)について、aのbによる剰余をrとすると、aとbの最大公約数はbとrの最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。

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

戻る 一覧へ 次へ