最大公約数（互除法）｜擬似言語のトレース解説と練習問題
関数 gcd は、二つの正の整数 a と b の最大公約数を返す。
プログラム
| 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 で割った余り」を求め、a に b を、b に余りを入れ直すことを、b が 0 になるまで繰り返します。b が 0 になったときの a が最大公約数です。
トレースのコツ
- 1回の繰返しで3つの代入が続きます。上から順に1行ずつ表に書きます。まとめて書くと、古い a と新しい a を取り違えます。
r ← a mod bの時点では、a と b はまだ前の値です。- 繰返しを続けるかどうかは、3つの代入が終わったあとの b で決まります。
よくある間違い
a ← bのあとでb ← rを計算するとき、b に新しい a を入れてしまう。r は先に求めてあるので、その値をそのまま入れます。- b が 0 になった回も本体を実行してしまう。while は先に条件を調べるので、b が 0 なら本体には入りません。
- 戻り値を b（つまり 0）と答える。返すのは a です。
例題：gcd(50, 7) を最後まで追う
上のプログラムを gcd(50, 7) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | a | b | r |
|---|---|---|---|---|---|
| 1 | 2 | 宣言 | 50 | 7 | 未設定 |
| 2 | 3 | 条件判定（真） | 50 | 7 | 未設定 |
| 3 | 4 | 代入 | 50 | 7 | 1 |
| 4 | 5 | 代入 | 7 | 7 | 1 |
| 5 | 6 | 代入 | 7 | 1 | 1 |
| 6 | 3 | 条件判定（真） | 7 | 1 | 1 |
| 7 | 4 | 代入 | 7 | 1 | 0 |
| 8 | 5 | 代入 | 1 | 1 | 0 |
| 9 | 6 | 代入 | 1 | 0 | 0 |
| 10 | 3 | 条件判定（偽） | 1 | 0 | 0 |
| 11 | 8 | 戻る（1） | 1 | 0 | 0 |
この例題で問われること
問 gcd(50, 7) を呼び出したときの戻り値はどれか。
答え 1
- 戻り値になる a は、50 → 7 → 1 と変わります。
- 8行目で返す時点の値 1 が答えです。
問 4行目を2回目に実行した直後の、変数 r の値はどれか。
答え 0
- 4行目は全部で2回実行されます。
- 実行した直後の r は、順に 1 → 0 です。
- 2回目の直後なので、答えは 0 です。
問 4行目が実行される回数はどれか。
答え 2
- 4行目が実行されるのは、3行目の条件が真になったときだけです。
- 3行目の条件は3回評価され、真になるのは2回です。したがって 4行目は2回実行されます。
練習問題 標準（5問）
本試験と同じくらいの量。レベル：入門
もっと解く（追加の10問）
練習問題 じっくり（10問）
長めのトレースで力をつける。レベル：入門
- 問題01 gcd(68, 35)
- 問題02 gcd(90, 39)
- 問題03 gcd(78, 56)
- 問題04 gcd(72, 54)
- 問題05 gcd(52, 28)
- 問題06 gcd(36, 30)
- 問題07 gcd(32, 24)
- 問題08 gcd(99, 54)
- 問題09 gcd(84, 49)
- 問題10 gcd(65, 20)
もっと解く（追加の20問）
- 問題11 gcd(87, 18)
- 問題12 gcd(24, 11)
- 問題13 gcd(36, 11)
- 問題14 gcd(74, 39)
- 問題15 gcd(73, 49)
- 問題16 gcd(87, 56)
- 問題17 gcd(89, 49)
- 問題18 gcd(99, 20)
- 問題19 gcd(50, 41)
- 問題20 gcd(46, 16)
- 問題21 gcd(90, 47)
- 問題22 gcd(86, 38)
- 問題23 gcd(64, 13)
- 問題24 gcd(79, 8)
- 問題25 gcd(72, 21)
- 問題26 gcd(78, 20)
- 問題27 gcd(90, 26)
- 問題28 gcd(66, 59)
- 問題29 gcd(95, 24)
- 問題30 gcd(79, 19)