技術士第一次試験｜無料Web版
技術士 基礎科目 令和5年度 Ⅰ－２－２｜問題と解説
問題 Ⅰ－２－２
自然数A，Bに対して、AをBで割った商をQ、余りをRとすると、AとBの公約数がBとRの公約数でもあり、逆にBとRの公約数はAとBの公約数である。
ユークリッドの互除法は、このことを余りが0になるまで繰り返すことによって、AとBの最大公約数を求める手法である。
このアルゴリズムを次のような流れ図で表した。
流れ図中の、ア〜ウに入る式又は記号の組合せとして、最も適切なものはどれか。
1 ア：R ＝ 0 イ：R ≠ 0 ウ：A
2 ア：R ≠ 0 イ：R ＝ 0 ウ：A
3 ア：R ＝ 0 イ：R ≠ 0 ウ：B
4 ア：R ≠ 0 イ：R ＝ 0 ウ：B
5 ア：R ≠ 0 イ：R ＝ 0 ウ：R
問題図表
正解と解説
正解：4
解説図の更新が最大公約数を変えないことを確認し、反復条件と最後に出力する変数を決める。
1．余りが残る間の更新を読む
A＝QB＋Rより、A,Bの公約数とB,Rの公約数は同じ。R≠0なら A←B、B←Rと更新して続けるため、アはR≠0である。
2．余り0での変数を確認する
R＝0ならAはBで割り切れ、gcd(A,B)＝Bになる。図はこの時点で更新せず右へ進むので、イはR＝0、ウはBである。
ア：R≠0、イ：R＝0、ウ：B。0になった余りRではなく、そのときの除数Bを出力する。
問題・正答の出典：公益社団法人 日本技術士会（公式の過去問題・公式正答）
掲載している解説は日本技術士会の公式解説ではありません。