基本情報技術者試験 平成31年度 春期 午前 問7
流れ図の考え方、ユークリッドの互除法、についての問題。
--------------------------
平成31年度 春期 午前 問7
次の流れ図は、2 数 A, B の最大公約数を求めるユークリッドの互除法を、引き算の繰り返しによって計算するものである。A が 876、B が 204 のとき、何回の比較で処理は終了するか。
ア 4
イ 9
ウ 10
エ 11
--------------------------
解説
たびたび登場の汚い手書き。
求めるものは L と S の比較が何回実行されているか（ひし形に L : S と書かれている部分を何回通るか）となる。
流れ図がどの様な動きをするか細かく見てみる。
まず最初の四角では L ← A、S ← B とある。
これは変数 L に A の値（876）を代入し、変数 S に B の値（204）を代入する。
次のひし形で L と S を比較する。
最初は L=876、S=204 で L > S なので、左に進んで L ← (L-S) の四角にいく。
L-S = 876-204 = 672 なので、L ← 672 となり L の値が更新される。
その後は再びひし形で L と S を比較することになる。
比較で L < S となった場合は右に進んで S ← (S-L) の四角に行く（大きい方の値が更新されていく）。
これを繰り返して、ひし形の比較で L = S となったら終了となる。
この手の問題は変数の変化を書き出してしまうのがミスもなく早いことが多い。
ということで以下の通りに書いてみる。
L の値 , S の値 , 比較回数（ひし形部分の実行回数）
876 , 204 , 0 ※開始直後の状態。
672 , 204 , 1 ※ 1 回比較した後に L=672、S=204 となる。
468 , 204 , 2
264 , 204 , 3
60 , 204 , 4
60 , 144 , 5 ※ 5 回目の比較で初めて L < S で S が更新される。
60 , 84 , 6
60 , 24 , 7
36 , 24 , 8
12 , 24 , 9
12 , 12 , 10 ※ 10 回比較した後に L=12、S=12 となる。
ここで答えを10としてウを選ぶとミスとなる。
10 回目の比較をした後の処理で S が 24 から 12 となるので、11 回目の比較で L=S となり終了する。なので正解は選択肢エ。
876 と 204 の最大公約数は 12 ということになる。
ユークリッドの互除法は引き算ではなく割り算の余りを利用する方法もある。
1. 大きい値（L=864）を小さい値（S=204）で割り算し、余り（60）を求める。
2. 大きい値を計算した余りの値で更新する（L=60 とする）。
3. 1. と 2. を繰り返して、余りが 0 となるときの値が最大公約数になる。
問題と同じ数字で繰り返しを具体的に書いてみると以下になる。
876 ÷ 204 = 4 余り 60
204 ÷ 60 = 3 余り 24
60 ÷ 24 = 2 余り 12
24 ÷ 12 = 2 余り 0
余りが 0 となった時の割る方の値 12 が最大公約数となる。
別のやり方に見えるけど、本質は全く同じ。
"876 から 204 を引き続けると 4 回引けて残りが 60 になる" と
"876 ÷ 204 が 4 余り 60 になる" とは同じこと。
引き算の方が計算回数多い（カウントミス増えそう）から問題に採用したのだろうか。
前後の問題はこちら。
