分数は、分子と分母の最大公約数で約分することによって、既約分数に表すことができる。
最大公約数を求める方法としてユークリッドの互除法がある。
これをスクラッチで再帰呼び出しを用いてプログラムしてみよう。
1 ユークリッドの互除法
自然数 a と b の最大公約数を d とすると、
a = u d, b = v d
と表され、u と v の公約数は 1 である。
a を b で割ったときの商を q、余りを r (0 ≦ r < b) とする。
a = q b + r
r = 0 のとき、a = q b であるので、
a と b の最大公約数は b である。
つまり、b は a と b の公約数であり、
b より大きい公約数は存在しない。
r ≠ 0 のとき、a = q b + r を変形すると
余り r は最大公約数 d の倍数になる。
a = u d = q v d + r
r = u d - q v d = (u - q v) d
したがって、d は b と r の公約数である。
以下、d が b と r の最大公約数であることの証明。
もし、d より大きい b と r の公約数 d' があったとする。
b = s d', r = t d', d' > d
したがって、
a = q b + r = q s d' + t d' = (q s + v) d'
と表され、d' は a の b 公約数になる。
d は a と b の最大公約数であるので、
d' が d より大きい公約数であることは矛盾。
したがって、d は b と r の最大公約数である。
以上から、
a を b で割り、a = q b + r とし、
r = 0 のとき、b が a と b の最大公約数、
r ≠ 0 のとき、b と r の最大公約数が a と b の最大公約数
であることがわかった。
例を見てみよう。
a=15, b=10 とする。
15 と 10 の最大公約数は 15=1x10+5 より
10 と 5 の最大公約数 である。
10 と 5 の最大公約数は 10=2x5+0 より 5 である。
したがって、15 と 10 の最大公約数は 5 である。
ユークリッドの互除法は、余りが 0 になるまで、
以下のように割り算を繰り返す方法。
a₁ = q₁ a₂ + a₃
a₂ = q₂ a₃ + a₄
...
2. ユークリッドの互除法で最大公約数を求めるスクラッチのプログラム
変数 a と変数 b に値を入れ、この定義 gcd を呼び出すと、
変数 d に a と b の最大公約数が得られる。
これを再帰呼び出しという。
3. このユークリッドの互除法を用いて分数の約分の練習問題を生成するプログラム
reduction を https://scratch.mit.edu/projects/491417958/ 置いてある。
0 件のコメント:
コメントを投稿