最大公約数（互除法）　問題09

じっくりレベル：入門　／　このアルゴリズムの解説を読む

練習モードは行番号つきで順に解く形式、本番形式は公開問題と同じ体裁の1問です。

関数 gcd は、二つの正の整数 a と b の最大公約数を返す。

次のプログラムを gcd(84, 49) で呼び出す。

〔プログラム〕

1	○整数型: gcd(整数型: a, 整数型: b)
2	整数型: r
3	while (b ≠ 0)
4	r ← ［　ａ　］
5	a ← b
6	b ← r
7	endwhile
8	return a

ヒント1：トレース表の枠を見る

この列で表を作り、文を1つ実行するたびに1行足していきます。

#	行	したこと	a	b	r

ヒント2：最初の4ステップを見る

続きを同じ要領で書いていきます。太字は、その文で値が変わった変数です。

#	行	したこと	a	b	r
1	2	宣言	84	49	未設定
2	3	条件判定（真）	84	49	未設定
3	4	代入	84	49	35
4	5	代入	49	49	35

設問1

gcd(84, 49) を呼び出すと戻り値は 7 になる。プログラム中の［　ａ　］に入れる正しい答えはどれか。

解答群ア　a ＋ b イ　a － b ウ　b ÷ a の商エ　a mod b

正解：エ　a mod b

それぞれの選択肢を空欄に入れて、実際に動かした結果は次のとおりです。
「a ＋ b」→ 繰返しが終わらない
「a － b」→ 繰返しが終わらない
「b ÷ a の商」→ 戻り値は 49
「a mod b」→ 戻り値は 7（正解）

設問2

4行目を3回目に実行した直後の、変数 r の値はどれか。

解答群ア　0 イ　7 ウ　14 エ　35

正解：イ　7

4行目は全部で4回実行されます。
実行した直後の r は、順に 35 → 14 → 7 → 0 です。
3回目の直後なので、答えは 7 です。

設問3

4行目が実行される回数はどれか。

解答群ア　1 イ　3 ウ　4 エ　5

正解：ウ　4

4行目が実行されるのは、3行目の条件が真になったときだけです。
3行目の条件は5回評価され、真になるのは4回です。したがって 4行目は4回実行されます。

本番形式

問　次の記述中の［　ａ　］に入れる正しい答えを，解答群の中から選べ。

関数 gcd は，二つの正の整数 a と b の最大公約数を返す。

関数 gcd を gcd(84, 49) として呼び出すと，戻り値は［　ａ　］となる。

〔プログラム〕

○整数型: gcd(整数型: a, 整数型: b)

整数型: r

while (b ≠ 0)

r ← a mod b

a ← b

b ← r

endwhile

return a

解答群

正解：エ　7

戻り値になる a は、84 → 49 → 35 → 14 → 7 と変わります。
8行目で返す時点の値 7 が答えです。

解説

余り r を求め、a に b を、b に r を入れ直すことを、b が 0 になるまで繰り返します。 b が 0 になったときの a が最大公約数で、ここでは 7 です。

行番号つきのプログラム

1	○整数型: gcd(整数型: a, 整数型: b)
2	整数型: r
3	while (b ≠ 0)
4	r ← a mod b
5	a ← b
6	b ← r
7	endwhile
8	return a

トレース表（全ステップ）

太字は、その文で値が変わった変数です。設問が指している行は黄色、その回は濃い黄色、変数は青い列で示します。

#	行	したこと	a	b	r
1	2	宣言	84	49	未設定
2	3	条件判定（真）	84	49	未設定
3	4	代入	84	49	35
4	5	代入	49	49	35
5	6	代入	49	35	35
6	3	条件判定（真）	49	35	35
7	4	代入	49	35	14
8	5	代入	35	35	14
9	6	代入	35	14	14
10	3	条件判定（真）	35	14	14
11	4	代入	35	14	7
12	5	代入	14	14	7
13	6	代入	14	7	7
14	3	条件判定（真）	14	7	7
15	4	代入	14	7	0
16	5	代入	7	7	0
17	6	代入	7	0	0
18	3	条件判定（偽）	7	0	0
19	8	戻る（7）	7	0	0