今日は12/24…そう、約分して1/2にできる日ですね！
彼女から「12/24はどうする?」ってメールが来たから
「約分して1/2にした方がいい」って返信したら音信不通になった
(よく使われるコピペ)
というわけで、こどもパソコン IchigoJamで約分を実装してみました。
※IchigoJamはjig.jpの登録商標です。
約分のアルゴリズム
約分は、分母と分子をそれぞれ両方の数を割り切る最大の整数(最大公約数)で割ることで実現できます。
最大公約数は、ユークリッドの互除法を用いて求めることができます。
これは、正の整数$a$と$b$の最大公約数を$gcd(a, b)$、$a$を$b$で割った余りを$a\mod b$と書くことにすると、
$a\mod b \neq 0$のとき$gcd(a, b) = gcd(b, a\mod b)$となることを利用し、
「$a\mod b \neq 0$である間、$(a, b)$を$(b, a\mod b)$で置き換えることを繰り返す」というアルゴリズムです。
$a\mod b = 0$となったときは、$a$が$b$で割り切れるということなので、最大公約数は$b$になります。
($b$は$b$で割り切れ、$b$より大きい整数では割り切れない)
以下、「$a\mod b \neq 0$のとき$gcd(a, b) = gcd(b, a\mod b)$となる」ことを示します。
$a, b$は、適当な正の整数$a', b', g$を用いて$a = ga', b = gb'$と表すことができます。
このとき、$a'=kb'+d$ ($k, d$は整数、$0 \leq k, 0 \leq d < b'$)とおくと、
$a = ga' = g(kb'+d) = gkb' + gd = k(gb') + gd = kb + gd$となり、
$a \mod b = gd$となることがわかります。 ($0 \leq d < b'$より、$0 \leq gd < gb' = b$)
したがって、$a \mod b$も$g$で割り切れる数となり、
「$a$も$b$も割り切る数は、必ず$a\mod b$も割り切る」ことがわかるので、
$gcd(a, b) \leq gcd(b, a\mod b)$となることがわかります。
逆に、$b = g'b', c = g'c' = a\mod b$ ($g'$は正の整数)とすると、
$a = k'b + c$ ($k'$は整数)と表すことができ、
$a = k'b + c = k'g'b' + g'c' = g'(k'b' + c')$となるので、$a$も$g'$で割り切れる数になります。
したがって、「$b$も$a\mod b$も割り切る数は、必ず$a$も割り切る」ことがわかるので、
$gcd(b, a\mod b) \leq gcd(a, b)$となることがわかります。
以上より、「$a\mod b \neq 0$のとき$gcd(a, b) = gcd(b, a\mod b)$となる」ことが示せました。
実装
10 ' ﾔｸﾌﾞﾝ
20 INPUT "ﾌﾞﾝｼ =",N
30 INPUT "ﾌﾞﾝﾎﾞ=",D
40 IF N<=0 OR D<=0 ?"ﾘｮｳﾎｳ ｾｲ ﾆ ｼﾃﾈ":GOTO 20
50 A=N:B=D
60 R=A%B
70 A=B
80 B=R
90 IF B>0 GOTO 60
100 ?N;"/";D;"=";N/A;
110 IF D/A>1 ?"/";D/A;
120 ?CHR$(10);
10行目は、FILES用のタイトルです。
20行目～40行目で、入力を受け付けています。なお、Nはnumerator (分子) を、Dはdenominator (分母) を表します。
50行目は、ユークリッドの互除法用にAとBを初期化しています。
60行目～90行目で、ユークリッドの互除法をしています。
100行目～120行目で、得られた最大公約数で分母と分子を割って約分をしています。
このとき、分母が1の時は分母を出力しないようにしています。
実行結果例
わざわざ動画にするほどではないと思ったので、動画は省略してテキストで実行結果例を示します。
RUN
ﾌﾞﾝｼ =12
ﾌﾞﾝﾎﾞ=24
12/24=1/2
OK
RUN
ﾌﾞﾝｼ =22
ﾌﾞﾝﾎﾞ=7
22/7=22/7
OK
RUN
ﾌﾞﾝｼ =480
ﾌﾞﾝﾎﾞ=640
480/640=3/4
OK
RUN
ﾌﾞﾝｼ =1280
ﾌﾞﾝﾎﾞ=720
1280/720=16/9
OK
RUN
ﾌﾞﾝｼ =256
ﾌﾞﾝﾎﾞ=16
256/16=16
OK
RUN
ﾌﾞﾝｼ =16
ﾌﾞﾝﾎﾞ=256
16/256=1/16
OK
結論
IchigoJamでユークリッドの互除法を実装し、約分をすることができました。
なお、12/24をどうするかは個人の自由です。
(中には会社に拘束されるなど、自由にできない人もいるかもしれませんが…)