分野別過去問題テクノロジ系　アルゴリズム No.23

アルゴリズム(全101問中23問目)

次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x，y)はxをyで割った余りを返す。

出典：平成29年春期　問 6

正解　イ問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

解説

aとbに適用な値を代入してアルゴリズムをトレースし、結果を選択肢の記述を比較することで答えを導きます。ここではa＝20，b＝8とします。

x ← 20
y ← 8
//ループ開始
t ← mod(20, 8) //t=4
x ← 8
y ← 4
t ← mod(8, 4) //t=0
x ← 4
y ← 0
//ループ終了
//処理終了
x=4

a=20、b=8なので、結果xはaとbの最大公約数になっています。その他の選択肢の記述にはどれも当てはまらないため「イ」が正解とわかります。

このアルゴリズムは「ユークリッドの互除法」と呼ばれ、2つの自然数の最大公約数を求める手法の一つです。