算法实战(六)

题目来源(PAT题目)

7-33 有理数加法

题目

本题要求编写程序，计算两个有理数的和。

输入格式：
输入在一行中按照a1/b1 a2/b2的格式给出两个分数形式的有理数，其中分子和分母全是整形范围内的正整数。

输出格式：
在一行中按照a/b的格式输出两个有理数的和。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

题解

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int gcd(int a,int b);
int lcm(int a,int b);

int main() {
    int temp,numerator1, denominator1, numerator2, denominator2,common,common1;
    scanf("%d/%d %d/%d", &numerator1, &denominator1, &numerator2, &denominator2);

    if (denominator1 != denominator2) { // 分母如果不相同，说明需要求最大公倍数
        common = lcm(denominator1, denominator2); // 求的最大公倍数
        if (common == denominator2) { // 进行通分
            temp = common / denominator1;
            numerator1 *= temp;
            denominator1 *= temp;
        }
        else if(common==denominator1){
            temp = common / denominator2;
            numerator2 *= temp;
            denominator2 *= temp;
        }
        else {
            temp = common / denominator1;
            numerator1 *= temp;
            denominator1 *= temp;
            temp = common / denominator2;
            numerator2 *= temp;
            denominator2 *= temp;
        }
        // 继续约分
        common1 = gcd(numerator1 + numerator2, common);
        if (common != 1) { // 进行约分
            if (common / common1 == 1)
                printf("%d", (numerator1+numerator2) / common1);
            else 
                printf("%d/%d", (numerator1+numerator2) / common1, common / common1);
        }
        
    }
    else { // 分母相同，不需要约分
        common = gcd(numerator1 + numerator2, denominator1);
        if (common != 1) {   // 需要约分
            if ((numerator1 + numerator2) / denominator1)
                printf("%d", (numerator1 + numerator2) / denominator1);
            else
                printf("%d/%d", (numerator1 + numerator2) / common, denominator1 / common);
        }
        
    }

    return 0;
}

// 求的最大公约数
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// 最小公倍数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

总结

该题目最重要的就是最大公约数、最小公倍数两个函数。