次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x, y)はxをyで割った余りを返す。
- aとbの最小公倍数
- aとbの最大公約数
- aとbの小さい方に最も近い素数
- aをbで割った商
解答
イ
解説
このアルゴリズムは、最大公約数を求めるアルゴリズムであり、ユークリッド互助法と言います。
例えば、a=12、b=8 の場合で試行してみると
初期設定：x=30、b=18
ループ1周目：t=12、x=18、y=12
ループ2周目：t=6、x=12、y=6
ループ3周目：t=0、x=6、y=0
となり、最大公約数が4であることがわかります。
参考情報
分野・分類
| 分野 | テクノロジ系 |
| 大分類 | 基礎理論 |
| 中分類 | アルゴリズムとプログラミング |
| 小分類 | アルゴリズム |
出題歴
- AP 平成29年度春期 問6
