C++求解有关分数的题目

写在前面：
关于分数型的题目求解，我觉得晴神在《算法笔记》上写得很好 真的是简单易懂（吹爆晴神 因为我是晴神的小迷弟?）。《算法笔记》里分数是用结构体存储的，然后有一系列的自定义函数：分数的加减乘除以及化简和输出。我觉得只需要在理解的基础上对晴神的这套模板加以记忆，对以后求解有关分数的题目是很有帮助的。

晴神的《算法笔记》电子版链接：https://pan.baidu.com/s/1NV5g1fb1iwM2aglFyO7N-Q 提取码：ycat。最好还是买纸质版的哦，京东和淘宝均有卖的，我是直接在机械工业出版社买的：https://item.jd.com/11973614.html。

分数模板：

struct Fraction    //分数用一个结构体来存储
{
    int up;    //分子
    int down;  //分母
};

int gcd(int a, int b)    //用辗转相除法来递归求最大公约数
{
    return !b ? a : gcd(b, a%b);
    //上面这一行等价于下面这段代码
    // if(b == 0)
    // {
    //     return a;
    // }
    // else 
    // {
    //     return gcd(b, a%b);   
    // }
}

Fraction reduction(Fraction result)   //分数的化简
{
    if(result.down < 0)  //若分母为负数,则令分子和分母都变为相反数
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0)  //若分子为0,则令分母为1
    {
        result.down = 1; 
    }
    else    //若分子不为0,则进行约分
    {
        int d = gcd(abs(result.up), abs(result.down));    //分子、分母的最大公约数为d
        //约去最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction add(Fraction f1, Fraction f2)   //分数的加法
{
    Fraction result;
    result.up = f1.up*f2.down + f1.down*f2.up;   //分数和的分子
    result.down = f1.down*f2.down;    //分数和的分母
    return reduction(result);   //将分数和化简后,返回结果分数
}

Fraction minus(Fraction f1, Fraction f2)   //分数的减法 
{
    Fraction result;
    result.up = f1.up*f2.down - f1.down*f2.up;   //分数差的分子
    result.down = f1.down*f2.down;    //分数差的分母
    return reduction(result);    //将分数差化简后,返回结果分数
}

Fraction multiply(Fraction f1, Fraction f2)    //分数的乘法
{
    Fraction result; 
    result.up = f1.up*f2.up;    //分数积的分子
    result.down = f1.down*f2.down;    //分数积的分母
    return reduction(result);    //将分数积化简后,返回结果分数
}

Fraction divide(Fraction f1, Fraction f2)    //分数的除法
{
    Fraction result;
    result.up = f1.up*f2.down;     //分数商的分子
    result.down = f1.down*f2.up;   //分数商的分母
    return reduction(result);      //将分数商化简后,返回结果分数
}

void showResult(Fraction result)    //输出分数
{
    result = reduction(result);     //化简分数
    if(result.down == 1)    //整数
    {
        printf("%d\n", result.up);
    }
    else if(abs(result.up) > abs(result.down))   //假分数
    {
        printf("%d %d/%d\n", result.up/result.down, abs(result.up)%result.down, result.down);
    }
    else    //真分数
    {
        printf("%d/%d\n", result.up, result.down);
    }
}

就拿之前HBU训练营中出现的那道“有理数的均值”为例吧。
题目描述：
本题要求编写程序，计算N个有理数的平均值。
输入格式：
输入第一行给出正整数N（≤100）；第二行中按照a1/b1 a2/b2 …的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。
输出格式：
在一行中按照a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。
输入样例1：
4
1/2 1/6 3/6 -5/10
输出样例1：
1/6
输入样例2：
2
4/3 2/3
输出样例2：
1

解题思路：
先判断是不是第一次输入，如果是第一次输入就把本次输入的分数赋值给sum，否则调用自定义函数add来对输入的分数进行累加。然后用分数总和sum除以分数个数N来求平均值，这里可以直接把N写成一个分母为1、分子为N的分数。最后化简输出结果即可。晴神??！

AC代码：

#include <bits/stdc++.h>
using namespace std;

struct Fraction    //分数用一个结构体来存储
{
    int up;    //分子
    int down;  //分母
};

int gcd(int a, int b)    //用辗转相除法来递归求最大公约数
{
    return !b ? a : gcd(b, a%b);
}

Fraction reduction(Fraction result)   //分数的化简
{
    if(result.down < 0)  //若分母为负数,则令分子和分母都变为相反数
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0)  //若分子为0,则令分母为1
    {
        result.down = 1; 
    }
    else    //若分子不为0,则进行约分
    {
        int d = gcd(abs(result.up), abs(result.down));    //分子、分母的最大公约数为d
        //约去最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction add(Fraction f1, Fraction f2)   //分数的加法
{
    Fraction result;
    result.up = f1.up*f2.down + f1.down*f2.up;   //分数和的分子
    result.down = f1.down*f2.down;    //分数和的分母
    return reduction(result);   //将分数和化简后,返回结果分数
}

Fraction divide(Fraction f1, Fraction f2)    //分数的除法
{
    Fraction result;
    result.up = f1.up*f2.down;     //分数商的分子
    result.down = f1.down*f2.up;   //分数商的分母
    return reduction(result);      //将分数商化简后,返回结果分数
}

void showResult(Fraction result)    //输出分数
{
    result = reduction(result);     //化简分数
    if(result.down == 1)    //整数
    {
        printf("%d\n", result.up);
    }
    else if(abs(result.up) > abs(result.down))   //假分数
    {
        printf("%d %d/%d\n", result.up/result.down, abs(result.up)%result.down, result.down);
    }
    else    //真分数
    {
        printf("%d/%d\n", result.up, result.down);
    }
}

int main()
{
    int N;
    cin >> N;
    Fraction sum;   //分数总和
    bool isVirgin = true;    //判断是不是第一次
    for(int i = 0; i < N; i++)
    {
        Fraction temp;
        scanf("%d/%d",&temp.up,&temp.down);
        if(isVirgin)    //若是第一次
        {
            sum.up = temp.up;
            sum.down = temp.down;
            isVirgin = false;
        }
        else
        {
            sum = add(sum,temp);
        }
    }
    Fraction f;
    f.up = N;
    f.down = 1;
    showResult(reduction(divide(sum,f)));
    return 0;
}