20200612-01 PAT　甲级试题 01 Rational Sum-蒲公英云

20200612-01 PAT　甲级试题 01 Rational Sum

怼烎@ 2023-02-17 05:04 116阅读 0赞

一、解析

1.1 核心算法

从题目来看，核心就是计算最大公因数，通过资料可知有两种方式能够计算出结果

方式一：辗转相除法 (欧几里德算法)
方式二：更相减损法 (《九章算术》的一种求最大公约数的算法)
方式三：辗转相减法 (尼考曼彻斯法)
这里由比较详细的图文解说，如果不是很清楚可以查看一下

1.2 实现

这里选择比较熟悉的辗转相除

int find_com(int a, int b) {
    int max;
    while(b) {
        max = a % b;
        a = b;
        b = max;
    }
    return a;
}
//这样只要　a % b 余数为零则说明整除，说明找到了最大公约数，具体用笔进行验算
//两个求和A/B a/b 上下同乘得到
// A/B => A * (b * B / c) / (B * b /c)
// a/b => a * (b * B / c) / (B * b /c)
//　新式子　= ((A * b / c) + (a * B /c)) / (B * b /c)

二、源码

#include <cstdio>
#include <cmath>
using namespace std;
int find_com(int a, int b){ 
    int max;
    while(b){ 
        max = a % b;
        a = b;
        b = max;
    }
    return a;
}
int find_min(int a, int b) { 
    auto max = find_com(a, b);
    return a * b / max;
}
int main(){ 
    auto n { 0};
    scanf("%d", &n);
    auto a { 0}, b { 0};
    auto A { 0}, B { 0};
    auto product { 0};
    scanf("%d/%d", &A, &B);
    // 辗转相除法
    for(int i = 1; i != n; ++i){ 
        scanf("%d/%d", &a, &b);
        product = find_min(B, b);
        A *= product / B;
        a *= product / b;
        B = product;
        A += a;
    }
    //　是否为负数
    if (A < 0) { 
        printf("-");
        A = abs(A);　//-A 也行
       }
    // 能否整除
    if (A % B == 0) { 
        printf("%d", A/B);
    } else { 
        if (auto s = A / B)
            printf("%d ", s);
        if (A %= B) { 
            product = find_com(A, B);
            printf("%d/%d", A/product, B/product);
        }
    }
    return 0;
}