平成29年春期試験問題 午前Ⅰ 問3

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

  • aとbの最小公倍数
  • aとbの最大公約数
  • aとbの小さい方に最も近い素数
  • aをbで割った商
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
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つの自然数の最大公約数を求める手法の一つです。

Pagetop