図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の最大公約数になります。(ユークリッドの互除法)
【キーワード】
・ユークリッドの互除法