C言語でN個の分数の積を既約分数として求める方法

N個の分数について、それぞれの分子(num)と分母(den)が与えられたとき、それら全ての積を計算し、結果を既約分数(約分された形)で出力することが課題です。

例えば、「4/5」と「3/4」という2つの分数の場合、1つ目の分数の分子に2つ目の分数の分子を掛け、1つ目の分数の分母に2つ目の分数の分母を掛けることで積を求めます。このとき最終的な結果は「12/20」になりますが、これは約分できるため、出力は「3/5」となります。本記事では、この問題を解くプログラムをC言語で作成していきます。

入力

fraction f[3] = {{1,2},
{2,1},
{5,6}}

出力

5/6

説明 − 1/2 × 2/1 × 5/6 = 10/12 となり、これを約分すると 5/6 になります。

入力

fraction f[2] = {{2, 3},
{1,4}}

出力

1/6

説明 − 2/3 × 1/4 = 2/12 となり、これは 1/6 と約分できます。

問題を解くためのアプローチ

この問題を解くには、まずすべての分子と分母の積を計算し、その結果を別々の変数 prod_num(最終的な分子)と prod_den(最終的な分母)に格納します。

次に、結果を既約分数にする必要があります。そのためには、prod_num と prod_den の最大公約数(GCD)をユークリッドの互除法で求め、両者をそれぞれのGCDで割ります。こうすることで、これ以上約分できない最もシンプルな分数形式が得られます。

アルゴリズム

開始
以下の要素を持つ構造体 fraction を宣言する
    1. num(分子)、2. den(分母)
関数 int GCD(int a, int b) 内
    ステップ1→ もし a == 0 ならば、
        b を返す
    ステップ2→ GCD(b % a, a) を返す
関数 int product(int n, fraction f[]) 内
    ステップ1→ prod_num = 1、prod_den = 1 を初期化
    ステップ2→ ループ For i = 0; i < n; i++
        prod_num = prod_num * f[i].num
        prod_den = prod_den * f[i].den
    ステップ3→ gcd = GCD(prod_num, prod_den) を宣言・初期化
    ステップ4→ prod_num = prod_num / gcd
    ステップ5→ prod_den = prod_den / gcd
    ステップ6→ prod_num と prod_den を出力
関数 int main() 内
    ステップ1→ 構造体 fraction f[3] = {
        {1,2},
        {2,1},
        {5,6}} を宣言
    ステップ2→ n を sizeof(f)/sizeof(f[0]) として宣言・初期化
    ステップ3→ product(n, f) を呼び出す
終了

実装例(C言語)

#include <stdio.h>
struct fraction{
    int num;
    int den;
};
// a と b の最大公約数(GCD)を返す関数
int GCD(int a, int b){
    if (a == 0)
       return b;
    return GCD(b % a, a);
}
// 結果を出力する関数
int product(int n, fraction f[]){
    int prod_num = 1, prod_den = 1;
    // N個すべての分子と分母の積を求める
    for (int i = 0; i < n; i++) {
        prod_num *= f[i].num;
        prod_den *= f[i].den;
    }
    // 新しい分子と分母のGCDを求める
    int gcd = GCD(prod_num, prod_den);
    // 既約分数の形にする
    prod_num /= gcd;
    prod_den /= gcd;
    printf("%d/%d\n", prod_num, prod_den);
    return 0;
}
int main(){
    struct fraction f[3] = {
        {1,2},
        {2,1},
        {5,6}};
    int n = sizeof(f)/sizeof(f[0]);
    product(n, f);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます −

5/6

補足：実装時の注意点

分数の個数Nが多くなると、分子と分母の積は急激に大きくなり、int 型ではオーバーフローする可能性があります。そのような場合は、long long 型を使用するか、各ステップでこまめにGCDによる約分を行うことで、数値の肥大化を防ぐことができます。