アルゴリズム (全101問中23問目)
No.23
次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x，y)はxをyで割った余りを返す。
出典：平成29年春期 問6
- aとbの最小公倍数
- aとbの最大公約数
- aとbの小さい方に最も近い素数
- aをbで割った商
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
aとbに適用な値を代入してアルゴリズムをトレースし、結果を選択肢の記述を比較することで答えを導きます。ここではa＝20，b＝8とします。
このアルゴリズムは「ユークリッドの互除法」と呼ばれ、2つの自然数の最大公約数を求める手法の一つです。
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の最大公約数になっています。その他の選択肢の記述にはどれも当てはまらないため「イ」が正解とわかります。y ← 8
//ループ開始
t ← mod(20, 8) //t=4
x ← 8
y ← 4
t ← mod(8, 4) //t=0
x ← 4
y ← 0
//ループ終了
//処理終了
x=4
このアルゴリズムは「ユークリッドの互除法」と呼ばれ、2つの自然数の最大公約数を求める手法の一つです。