河北大学程序设计训练营

[TOC]

2-4 N个数求和 (30分)

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

思路：

利用结构体 ，分子分母分别相加，进行约分化简，最后根据题目格式输出。

注意点

  • 相加过程中可能使分子或分母超过int型表示范围，因此保险起见，直接用long long来存储好喽。这种情况尤其体现在分数的乘法除法过程中。
  • 约分化简主要利用的是欧几里得算法求最大公约数。
    1
    2
    3
    4
    5
    int gcd(int a, int b)
    {
        if( b == 0) return a;
        else return gcd( b, a % b);
    }
    更简洁的写法，两个写法喜欢哪个用哪个。
    1
    2
    3
    4
    int Gcd(int a, int b)
    {
        return !b ? a : Gcd(b, a % b);
    }
  • 格式输出时注意输出格式，符号是跟在分数部分的。之后无非就是整数，真分数，假分数的处理。真假根据abs(r.up) > r.down 代码句进行区分。

题解代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
int gcd(int a, int b)  //求解最大公约数
{
    if( b == 0) return a;
    else return gcd( b, a % b);
}
//分数表示
struct Fraction  //分数
{
    int up, down; //分子,分母
};
Fraction reduction(Fraction result) //分数化简
{
    if(result.down < 0)  
    {
        result.up = - result.up;
        result.down = - result.down;
    }
    if(result.up == 0)
    {
        result.down = 1;
    }
    else
    {
        int d = gcd(abs(result.up), abs(result.down));
        if(d)
        {
            result.up /= d;
            result.down /= d;
        }
    }
    return result;
}
//分数的输出
void showResult(Fraction r)
{
    r = reduction(r);
    if(r.down == 1) cout << r.up;
    else if(abs(r.up) > r.down) //假分数
    {
        cout << abs(r.up) / abs(r.down) << " " << abs(r.up) % r.down << "/" << r.down;
    }
    else //真分数
    {
        cout << r.up << "/" << r.down;
    }
}
int main()
{
    int n;
    cin >> n;
    long long fz = 0, fm = 1, z, m; 
    while(n--)
    {
        scanf("%d/%d", &z, &m);
        fz = fz * m + z * fm; //注意fz fm顺序
        fm = fm * m;
    }
    Fraction result;  //分数初始化
    result.up = fz;
    result.down = fm;
    Fraction r = reduction(result);  // 约分
    showResult(r); //结果输出
    return 0;
}

关于分数处理知识点的补充
分数的表示

1
2
3
4
struct Fraction  //分数
{
    int up, down; //分子,分母
};

分数的化简

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Fraction reduction(Fraction result)
{
    if(result.down < 0) //分母为负数，令分子分母都变成相反数
    {
        result.up = - result.up;
        result.down = - result.down;
    }
    if(result.up == 0) // 如果分子是0
    {
        result.down = 1; 
    }
    else  //分母不为0，进行约分
    {
        int d = gcd(abs(result.up), abs(result.down));
        if(d)
        {
            result.up /= d;
            result.down /= d;
        }
    }
    return result;
}

分数的输出

1
2
3
4
5
6
7
8
9
10
11
12
13
void showResult(Fraction r)
{
    r = reduction(r);   //第一约分后得到的分数
    if(r.down == 1) cout << r.up; //整数
    else if(abs(r.up) > r.down) //假分数
    {
        cout << abs(r.up) / abs(r.down) << " " << abs(r.up) % r.down << "/" << r.down;
    }
    else //真分数
    {
        cout << r.up << "/" << r.down;
    }
}

这些格式化的东西，多熟练一下，下次拿过来就可以用。