团体程序设计天梯赛-练习集 L1-009 N个数求和 (20分)

╰半夏微凉° 2023-10-11 14:46 85阅读 0赞

### L1-009 N个数求和 (20分) ###

本题的要求很简单，就是求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

##### 求解本题的思路如下： #####

除了第一个分数以外，每次输入的时候，都化简一次。  
先用两个分数相加的形式：**a/b+c/d=(a\*d+b\*c)/(b\*d)**，进行相加，然后用辗转相除算法求出最大公约数进行化简。  
最后需要强调的是，输出格式的三种情况：

*  当结果的分母部分为1，直接输出分子
 *  当结果的分母大于分子，需考虑只有整数和整数分数都。存在的两种情况。
 *  当结果的分子小于分母，直接输出。

#include<cstdio>
    
    int n;
    int a, b, c, d;
    
    int gcd(int a, int b){
        
    	if(b==0)
    		return a;
    	return gcd(b, a%b);
    }
    
    int main(){
        
    	while(scanf("%d", &n)!=EOF){
        
    		scanf("%d/%d", &a, &b);
    		
    		for(int i = 1; i < n; i ++){
        
    			scanf("%d/%d", &c, &d);
    			a = a*d + c*b;
    			b = b*d;
    			
    			int v = gcd(a, b);//求出最大公约数
    			
    			//每次都化简
    			a = a/v; // a为分子
    			b = b/v; // b为分母
    		}
    		if(b==1){
         //分母为1的情况
    			printf("%d\n", a);
    		}
    
    		else if(a>b){
        //既有整数，又有分数
    			int ans_1 = a/b;//整数部分
    			int ans_2 = a%b;//分数部分
    			
    			if(ans_2 == 0){
        
                    printf("%d\n", ans_1);
    			}else{
        
    				printf("%d %d/%d\n", ans_1, ans_2, b);
    			}
    		}
    
    		else{
        //只有分数
    			printf("%d/%d\n",a, b);
    		}
    	}
    	return 0;
    }