ユークリッドの互除法による約分プログラム

問題
次の分数は約分できますか。できるのであれば、約分してもとっとも簡単な分数で表しなさい
\[ \frac{10033}{12877} \]

ユークリッドやなーって感じの問題が数学検定１級の練習問題で出てきた
そういえば
ユーグリットの互除法は、プログラムだと再起関数の例題でよく見かけるが、実際組んだことなかったので
プログラムでこの問題を解いてみることにする

ユークリッドの互除法とは

自然数$a$、$b$に対し、$a$を$b$で割ったあまりを$r$とおくと、下記等式が成り立つ \[ gcm(a,b)=gcm(b,r) \] ※$gcm(n1,n2)$とは$n1$と$n2$の最大公約数を意味する

これで何で最大公約数が簡単に求まるのか。実際に本問題の最大公約数を求めてみる

$gcm(12877,10033)=gcm(10033,2844)$	$(\because12877\div10033 = 1\times 10033 + 2844)$
$gcm(10033,2844)=gcm(2844,1501)$	$(\because10033\div2844 = 3\times 2844 + 1501) $
$gcm(2844,1501)=gcm(1501,1343)$	$(\because2844\div1501 = 1\times 1501 + 1343) $
$gcm(1501,1343)=gcm(1343,158)$	$(\because1501\div1343 = 1\times 1343 + 158) $
$gcm(1343,158)=gcm(158,79)$	$(\because1343\div158 = 8\times 158 + 79) $
$gcm(158,79)\ne gcm(79,0)$	$(\because158\div79 = 2\times 79 + 0) $

※最後が$\ne$なのは「0」は自然数に含まれないためイコールにならない

繰り返すごとに数字が小さくなっているのがわかる
これは割ったあまりを次の最大公約数を求めるために使うから、一般的な割り算の考え方(割られる数＞割る数＞あまり)より
繰り返すたびに数字が小さくなっていく

実装

再帰関数が使えるプログラム言語なら超簡単。2つの引数の最大公約数を求める関数はこんな感じ

/**
 * 2つの引数の最大公約数(gcm)をユーグリットの互除法で求める.
 * @param n1 対象の数字１
 * @param n2 対象の数字２
 * @return ret 最大公約数
 */
int gcm(int n1, int n2) {
    int ret = n1 % n2;
    return (ret == 0) ? n2 : gcm(n2, ret);
}

この関数を使って本問題を解くと

/**
 * 約分問題を解くプログラム
 * gcm.cpp
 */
#include<iostream>
#include<cmath>

/** 分子. */
#define NUMERATOR 10033
/** 分母. */
#define DENOMINATOR 12877

int gcm(int, int); // 最大公約数を求める関数(内容省略)

int main(){
    int numerator   = NUMERATOR;   // 分子
    int denominator = DENOMINATOR; // 分母
    int gcm_num = gcm(numerator, denominator); // 最大公約数

    if(gcm_num == 1) {
        // 約分できない場合
        // 最大公約数「1」は互いに素の関係だから約分できない
        std::cout << " 約分できません " << std::endl;

    } else {
        // 約分できる場合
        // 約分する
        numerator   /= gcm_num;
        denominator /= gcm_num;

        // 分母、分子間の線の長さを計算(対数を使って桁数取得)
        int line = (int)log10(fmax(numerator, denominator)) + 1;

        // 解表示
        std::cout << numerator << std::endl;
        for(int i = 0; i < line; i++) std::cout << "-";
        std::cout << std::endl << denominator << std::endl;
    }
    return 0;
}

実行結果

$ g++ gcm.cpp
$ ./a.out
127
---
163

約分できることがわかった
ハイライトの箇所(31,32行目)はちょっと特殊な計算で線の長さを求めてる(対数による桁数計算方法)
これについては本問題と関係ないし、また後日説明しようかな

後日説明 ⇒ 数字の桁数を取得する方法