平成21年度 春期 ITパスポート試験 問72 解説 処理ボックスの計算

この問題は、入力値がボックスを通るたびにルールに従って変換されるという一連の流れを、順を追って計算することで解くことができます。

1つ目のボックス：$A1=15, A2=6$ を入力します。 $B1 = A2 = 6$ $B2 = 15 \pmod 6 = 3$

2つ目のボックス：1つ目の出力 $B1, B2$ がそのまま入力されます。つまり、$A1=6, A2=3$ を入力します。 $B1 = A2 = 3$ $B2 = 6 \pmod 3 = 0$

したがって、後方のボックスの $B1$ は $3$ となります。

ボックスが示すアルゴリズムの正体

この問題のボックスは、実は数学で習う「ユークリッドの互除法」の1ステップを表現しています。ユークリッドの互除法とは、2つの整数の最大公約数を求めるための効率的な手法です。

問題のルールを整理するとこうなります。

• $B1$ には入力された2番目の値（$A2$）をそのまま渡す
• $B2$ には $A1$ を $A2$ で割った余りを渡す

この操作を繰り返すと、最後には余りが $0$ になります。余りが $0$ になったときの $B1$ の値が、元の2つの数値（この場合は15と6）の最大公約数となります。今回のケースでは、2つ目のボックスで $B2$（余り）が $0$ になったため、その時の $B1$ である $3$ が最大公約数であることがわかります。

順を追った処理の考え方

試験会場では、図に直接数値を書き込みながら進めるのが最も確実です。

1. 最初のボックスの左端に $15$ と $6$ を書く。
2. ボックス内の指示通りに計算する。$B1$ はそのまま $6$ を右へ、下側の出口 $B2$ には $15$ を $6$ で割った余りである $3$ を出す。
3. 2つ目のボックスの左端に、前のボックスから受け取った $6$ と $3$ を書き込む。
4. 再び同様の計算を行う。$B1$ は $3$ となり、下の $B2$ は $0$ となる。
5. 問題が求めているのは「後方のボックスの $B1$」なので、その値である $3$ を選択肢から選ぶ。

このように、複雑そうな仕組みであっても、1つずつ「入力」と「出力」の関係を丁寧にトレース（追跡）していくのが、アルゴリズム関連の問題を解くコツです。

なぜこの知識が重要なのか

コンピュータプログラムにおいて、複雑な処理は小さな処理の組み合わせでできています。この問題のように、ある処理の結果が次の処理への入力となる「パイプライン」的な考え方は、データ処理や自動化の基本です。

また、ユークリッドの互除法のようなアルゴリズムは、単なる数学の知識ではなく、コンピュータが非常に少ない手順で答えを導き出すための「効率的な設計」の例です。ITパスポートでは、直接プログラミングをすることはありませんが、こうした「手順を組み立てて答えを出す」という論理的思考は、システム設計や業務フローを理解する上で非常に重要な基礎能力となります。

参考リンク

• ITパスポート試験対策サイト：アルゴリズムとプログラム
• 【競技プログラミング】ユークリッドの互除法を使って遊んでみよう
• 数学におけるユークリッドの互除法の定義