20200612-01 PAT　甲级试题 01 Rational Sum

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

## 一、解析 ##

#### 1.1 核心算法 ####

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

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

> 计算完毕之后，需要考虑一下几种情况  
> 1 分子是否为负数 需要输出　-  
> 2 是否整除　需要输出　整数  
> 3 是否 分子 > 分母　需要化简，整数与分式之间留出一个空格  
> 4 分子分母是否是最简模式，即除去公约数

## 推荐课程 ##

尹成老师带你学算法

数据结构核心原理与算法应用

[Link 1]: https://blog.csdn.net/qq_31828515/article/details/51812154