C言語で解説：エジプト分数の貪欲法分解アルゴリズム実装

本記事では、C言語を使って、貪欲法でエジプト分数の形に分数を分解するアルゴリズムを実装する方法について説明します。

与えられた分数 $\frac{a}{b}$ を順次、単位分数 $\frac{1}{x}$ に分解し、分解結果の和が元の分数と一致するように処理します。

シンプルなコード例が含まれており、開発環境が整っていればすぐに試していただけます。

問題設定とエジプト分数の定義

エジプト分数の基本

エジプト分数とは、分子が常に1となる単位分数の和で任意の分数を表現する方法です。

たとえば、分数 $\frac{2}{3}$ は

$$\frac{2}{3}=\frac{1}{2}+\frac{1}{6}$$

のように表すことができます。

エジプト分数の考え方は、古代エジプトの数学で採用されていた分数の扱い方に由来しており、いくつかの歴史的な文献で確認することができます。

分数表現の条件と目的

エジプト分数を利用する場合、次の条件を満たす必要があります。

• 各分数は単位分数、すなわち分子が1の形であること
• 使用する分母はすべて異なる正の整数であること

この分解の目的は、与えられた任意の分数を単位分数の集合に分解することであり、分数の性質や分解アルゴリズムを理解するための演習として利用されます。

貪欲法による分解アルゴリズム

アルゴリズムの流れ

貪欲法は、分解対象の分数から常に最も大きい単位分数を抜き出すという方法です。

アルゴリズムの流れは以下の通りです。

1. 現在の分数を $\frac{a}{b}$ とする。
2. 次に使う単位分数の分母を $N=\lceil \frac{b}{a}\rceil$ として選定する。
3. 新たな分数は $\frac{a}{b}–\frac{1}{N}=\frac{aN–b}{bN}$ となる。
4. 更新された分数に対して同じ操作を繰り返し、分数が 0 になるまで処理を実施する。

単位分数の選定方法

選定の際は、現在の分数 $\frac{a}{b}$ に対して $N=\lceil \frac{b}{a}\rceil$ を算出します。

これにより、単位分数 $\frac{1}{N}$ が現在の分数以下であり、かつ可能な限り大きな値となるように選定されます。

分母の更新手順

単位分数が決定されたら、分解対象の分数からその単位分数を引きます。

すなわち、

$$\frac{a}{b}–\frac{1}{N}=\frac{aN–b}{bN}$$

となるため、新たな分子と分母をこの式に従って更新します。

反復処理の停止条件

反復処理は、更新後の分数が 0 になるか、残りの分数が既に単位分数で表せる場合に停止します。

具体的には分子が 1 となった場合は、その時点で単位分数として処理を終了することができます。

C言語での実装詳細

使用する変数とその役割

C言語で実装する際には、分数の分子と分母を管理するための変数を用います。

分解の途中経過を保持するために、整数型変数を利用するのが一般的です。

また、分解された単位分数の分母を格納する配列なども用いることができます。

分子・分母の管理方法

分子は変数 numerator、分母は変数 denominator として定義します。

反復処理においては、下記のように更新を行います。

• 初期値として入力された分数の分子・分母を設定する。
• 各ステップで、更新された新たな分子と分母を計算し、次のイテレーションに渡します。

単位分数の表現方法

単位分数は分子が 1 であるため、出力時には 1/denom の形で表現されます。

また、分解された単位分数の分母を配列 egyptian[] に格納することで、後で出力する際に順序を保持できます。

関数構成と処理の分割

分解処理関数の設計

分解処理は、egyptianFraction という専用の関数にまとめます。

関数は引数として分子と分母を受け取り、再帰またはループにより貪欲法を適用して、単位分数の分母を出力します。

以下にサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// egyptianFraction関数は、分数 numerator/denom をエジプト分数に分解して出力します。
void egyptianFraction(int numerator, int denom) {
    // 分解された単位分数の分母をすぐに出力
    while(numerator != 0) {
        // 分母の選定: ceil(denom / numerator)
        int x = (int)ceil((double)denom / numerator);
        // 単位分数を出力
        printf("1/%d ", x);
        // 新たな分数の分子と分母の更新
        // 新しい分子 => numerator * x - denom
        // 新しい分母 => denom * x
        numerator = numerator * x - denom;
        denom = denom * x;
    }
    printf("\n");
}
int main(void) {
    int numerator, denom;
    // 入力例: 2/3 を分解
    numerator = 2;
    denom = 3;
    printf("エジプト分数分解: %d/%d -> ", numerator, denom);
    egyptianFraction(numerator, denom);
    return 0;
}

入力の検証とエラーチェック

実装においては、以下の点に注意が必要です。

• 分母が 0 となるケースはないか確認する。
• ユーザからの入力を受け付ける際に、整数以外の値が入力されないようにする。
• 分数が既に単位分数であれば、処理を早期に終了できるように条件分岐を設ける。

コードの動作検証

実行例による動作確認

C言語で実装したコードは、標準出力に単位分数の列を出力します。

たとえば、上記サンプルコードでは、入力分数 $\frac{2}{3}$ を

$$\frac{2}{3}=\frac{1}{2}+\frac{1}{6}$$

のように分解した結果が出力されます。

標準出力の確認方法

プログラムをコンパイル後、実行すると次のような出力が期待されます。

エジプト分数分解: 2/3 -> 1/2 1/6

デバッグ時の注意点

境界条件への対応方法

デバッグ時は以下の点に注意する必要があります。

• 入力される分数で分子が分母以上の場合に、アルゴリズムが正しく動作するか確認する。
• 既に単位分数である場合(分子が 1 の場合)には、余計な処理が行われず正しく出力されるか確認する。
• 演算結果が大きな整数になる場合、オーバーフローに注意し、必要に応じてデータ型を調整する。

これらの項目を念頭に置いてデバッグおよびテストすることで、信頼性の高いエジプト分数の分解プログラムを作成できるようになります。

まとめ

この記事では、エジプト分数の基本から、与えられた分数を単位分数の和に変換する貪欲法の詳細な流れを解説しています。

特に、単位分数の選定方法、分母更新手順、反復処理の停止条件について説明した上、C言語での実装例を示しながら各変数の役割や関数の分割、入力検証のポイントについて解説しています。

読者は、基本理論と具体的なコーディング手法を体系的に理解することができます。