数学-分数化简

典型例题（在《C++程序设计思想与方法》的P260有介绍）

输入为两行，每行代表一个分数，每行两个正整数，

输出一行，为相加的结果，输出形式为真分数。

Input

1 2
1 3

Output

5/6

---

#include <iostream>
#include <algorithm>

using namespace std;

class Fraction
{
friend ostream & operator<<(ostream & os, const Fraction & obj);
friend istream & operator>>(istream & is, Fraction & obj);

private:
    int num, den;
public:
    Fraction(): num(0), den(1) {}
    Fraction(int x, int y): num(x), den(y) {};
    ~Fraction() = default;

    Fraction operator+(Fraction & obj) 
    {
        Fraction res;
        res.num = num * obj.den + den * obj.num;
        res.den = den * obj.den;
        reductFraction(res);

        return res;
    }

    void reductFraction(Fraction & obj)
    {
        int tmp = min(obj.num, obj.den);

        for ( ; tmp > 1; --tmp) {
            if (obj.num % tmp == 0 && obj.den % tmp == 0) {
                obj.num /= tmp;
                obj.den /= tmp;
                break;
            }
        }
    }
};

istream & operator>>(istream & is, Fraction & obj)
{
    is >> obj.num >> obj.den;
    return is;
}

ostream & operator<<(ostream & os, const Fraction & obj)
{
    if (obj.num == obj.den) os << 1;
    else os << obj.num << "/" << obj.den;
    return os;
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Fraction number1, number2;
    cin >> number1;
    cin >> number2;
    cout << (number1 + number2) << endl;

    return 0;
}

核心代码是32-38行，这里选取分子和分母中的较小者，从高往低筛选，只要有一个满足条件就可以认为化简完毕，因为假如此时没有化简完毕，则意味着余下的数还存在公因数，则意味着并不是由高往低搜索的。

利用GCD进行分数化简

分数化简其实就是求分子和分母的最大公约数，上面的搜索方法速度较慢。

典型题目：

• POJ 1580 （分数化简 + 字符串）