第13問 最大公約数（ユークリッドの互除法）
ユークリッドの互除法では、2つの数が等しくなるまで「大きいほうから小さいほうを引く」操作を繰り返し、最後に残った値が最大公約数になります。2つの数 a=252, b=105 の最大公約数を求めて表示しよう。
難易度：★★★★★（5／難しい）。共通テスト「情報I」で使われるDNCL（共通テスト用プログラム表記）の穴埋め問題です。JavaScriptを有効にすると、このページでプログラムを組み立てて実行しながら解けます。
プログラム
a = 252
b = 105
a != b の間繰り返す:
もし a ［A］ b ならば:
a = a ［B］ b
そうでなければ:
b = b - a
表示する("最大公約数は" + a)
空欄 ［A］・［B］ に当てはまるものを、次の選択肢から選びます。
選択肢
ヒント
「2つが等しくない間」繰り返し、「a のほうが大きいとき」だけ a から b を引く、と考えよう。最後に残った値が最大公約数です
解答
よくある間違い
- ［A］
< ［B］- … a<b のときに a から b を引くと a がマイナスになってしまいます。大きいほう(a>bのとき)から引きましょう
- ［A］
> ［B］+ … 足し算では値がどんどん増えて等しくならず、繰り返しが終わりません。引き算で小さくしていきます
- ［A］
== ［B］- … a==b だと while の条件(a!=b)と矛盾し、この if は決して成り立ちません。大小を比べる > を使いましょう
ほかの問題