ITパスポート|アルゴリズムとプログラミング 問8
図 1 のように二つの正の数値 A1、A2 を読み取り、二つの数値 B1、B2 を出力するボックスがある。B1 には A2 と同じ数値を出力し、B2 には A1 を A2 で割った余りを出力する。図 2 のようにこのボックスを 2 個つないだ場合、A1=15、A2=6 のとき後方のボックスの B1 に出力される数値は幾らか。
図1:A1、A2 → [A2→B1、A1/A2の余り→B2] → B1、B2
図2:15、6 → [ボックス] → [ボックス] → B1、B2正解:イ
解説
前のボックスの出力 B1、B2 が、後ろのボックスの入力 A1、A2 になります。
- 前のボックス
- B1 = 6、B2 = 15 ÷ 6 の余り = 3
- 後ろのボックス
- A1 = 6、A2 = 3 なので、B1 = 3、B2 = 6 ÷ 3 の余り = 0
- ア 後ろのボックスの B2 の値です。
- イ 正解。
- ウ 前のボックスの B1 の値です。
もう一歩深く
前のボックスでは、A1 = 15、A2 = 6 なので、B1 = 6、B2 = 15 ÷ 6 の余り = 3 です。後ろのボックスでは、A1 = 6、A2 = 3 なので、B1 = 3、B2 = 6 ÷ 3 の余り = 0 です。このボックスを余りが 0 になるまでつなぐと、最後の B1 が 15 と 6 の最大公約数(3)になります。これはユークリッドの互除法という計算の方法です。
出典:平成21年度春期 ITパスポート試験 公開問題 問72(読点「,」を「、」に改変)