L1-009. N个数求和

最新推荐文章于 2025-04-02 20:38:19 发布

ChenyutingZJU

最新推荐文章于 2025-04-02 20:38:19 发布

阅读量177

点赞数

分类专栏：天梯赛练习题

本文链接：https://blog.csdn.net/chenyutingdaima/article/details/79685004

版权

天梯赛练习题专栏收录该内容

86 篇文章

订阅专栏

本文介绍了一种算法，用于解决N个以分数形式给出的有理数求和问题，并确保输出结果是最简形式的有理数。通过定义结构体表示分数，实现了求最大公约数、分数化简、分数加法等功能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

L1-009. N个数求和
本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数“分子/分母”的形式给出的，你输出的和也必须是有理数的形式。

输入格式：

输入第一行给出一个正整数N（<=100）。随后一行按格式“a1/b1 a2/b2 …”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出格式：

输出上述数字和的最简形式 —— 即将结果写成“整数部分分数部分”，其中分数部分写成“分子/分母”，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1：
5
2/5 4/15 1/30 -2/60 8/3
输出样例1：
3 1/3
输入样例2：
2
4/3 2/3
输出样例2：
2
输入样例3：
3
1/3 -1/6 1/8
输出样例3：
7/24

解题思路：
用结构体来表示分数，需要写出若干个函数：求最大公约数、分数化简、分数加法、分数输出。注意在执行加法后和进行输出前都要把分数化简。注意函数的返回类型为node型。

#include<cstdio> 
#include<algorithm>
using namespace std;
typedef long long ll;
int gcd(ll a,ll b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
struct node{
    ll up,down;
};
node reduction(node a){
    if(a.down<0){
        a.up =-a.up ;
        a.down =-a.down ;
    }
    if(a.up ==0)
        a.down =1;
    else{
        int d=gcd(a.up ,a.down );
        a.up /=d;
        a.down /=d; 
    }
    return a;
}
node add(node a,node b){
    node c;
    c.up =a.up*b.down +a.down *b.up ;
    c.down =a.down *b.down ;
    return reduction(c);
}
void show(node a){
    a=reduction(a);
    if(a.down ==1) printf("%lld",a.up );
    else if(abs(a.up)>a.down ){
        printf("%lld %lld/%lld",a.up/a.down ,abs(a.up)%a.down ,a.down );
    }else{
        printf("%lld/%lld",a.up ,a.down );
    }
}
int main(){
    int n;
    node ans,temp;
    ans.up =0;
    ans.down =1;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld/%lld",&temp.up ,&temp.down );
        ans=add(ans,temp);
    }
    show(ans);
    return 0;
}