C++求解有关分数的题目

喜欢ctrl的cxk

发布于 2019-11-08 10:37:19

4210

发布于 2019-11-08 10:37:19

文章被收录于专栏：Don的成长史

本文链接：https://blog.csdn.net/weixin_42449444/article/details/94907737

写在前面：

关于分数型的题目求解，我觉得晴神在《算法笔记》上写得很好真的是简单易懂（吹爆晴神因为我是晴神的小迷弟?）。《算法笔记》里分数是用结构体存储的，然后有一系列的自定义函数：分数的加减乘除以及化简和输出。我觉得只需要在理解的基础上对晴神的这套模板加以记忆，对以后求解有关分数的题目是很有帮助的。

分数模板：

这部分代码已经获得晴神授权了嗷。?

struct Fraction    //分数用一个结构体来存储
{
    int up;    //分子
    int down;  //分母
};

int gcd(int a, int b)    //用辗转相除法来递归求最大公约数
{
    return !b ? a : gcd(b, a%b);
    //上面这一行等价于下面这段代码
    // if(b == 0)
    // {
    //     return a;
    // }
    // else 
    // {
    //     return gcd(b, a%b);   
    // }
}

Fraction reduction(Fraction result)   //分数的化简
{
    if(result.down < 0)  //若分母为负数,则令分子和分母都变为相反数
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0)  //若分子为0,则令分母为1
    {
        result.down = 1; 
    }
    else    //若分子不为0,则进行约分
    {
        int d = gcd(abs(result.up), abs(result.down));    //分子、分母的最大公约数为d
        //约去最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction add(Fraction f1, Fraction f2)   //分数的加法
{
    Fraction result;
    result.up = f1.up*f2.down + f1.down*f2.up;   //分数和的分子
    result.down = f1.down*f2.down;    //分数和的分母
    return reduction(result);   //将分数和化简后,返回结果分数
}

Fraction minus(Fraction f1, Fraction f2)   //分数的减法 
{
    Fraction result;
    result.up = f1.up*f2.down - f1.down*f2.up;   //分数差的分子
    result.down = f1.down*f2.down;    //分数差的分母
    return reduction(result);    //将分数差化简后,返回结果分数
}

Fraction multiply(Fraction f1, Fraction f2)    //分数的乘法
{
    Fraction result; 
    result.up = f1.up*f2.up;    //分数积的分子
    result.down = f1.down*f2.down;    //分数积的分母
    return reduction(result);    //将分数积化简后,返回结果分数
}

Fraction divide(Fraction f1, Fraction f2)    //分数的除法
{
    Fraction result;
    result.up = f1.up*f2.down;     //分数商的分子
    result.down = f1.down*f2.up;   //分数商的分母
    return reduction(result);      //将分数商化简后,返回结果分数
}

void showResult(Fraction result)    //输出分数
{
    result = reduction(result);     //化简分数
    if(result.down == 1)    //整数
    {
        printf("%d\n", result.up);
    }
    else if(abs(result.up) > abs(result.down))   //假分数
    {
        printf("%d %d/%d\n", result.up/result.down, abs(result.up)%result.down, result.down);
    }
    else    //真分数
    {
        printf("%d/%d\n", result.up, result.down);
    }
}

就拿HBU训练营中出现的那道“有理数的均值”为例吧。

题目描述：

本题要求编写程序，计算N个有理数的平均值。

输入格式：

输入第一行给出正整数N（≤100）；第二行中按照a1/b1 a2/b2 …的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。

输出格式：

在一行中按照a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

输入样例1：

4
1/2 1/6 3/6 -5/10

输出样例1：

1/6

输入样例2：

2
4/3 2/3

输出样例2：

解题思路：

先判断是不是第一次输入，如果是第一次输入就把本次输入的分数赋值给sum，否则调用自定义函数add来对输入的分数进行累加。然后用分数总和sum除以分数个数N来求平均值，这里可以直接把N写成一个分母为1、分子为N的分数。最后化简输出结果即可。晴神??！

AC代码：

#include <bits/stdc++.h>
using namespace std;

struct Fraction    //分数用一个结构体来存储
{
    int up;    //分子
    int down;  //分母
};

int gcd(int a, int b)    //用辗转相除法来递归求最大公约数
{
    return !b ? a : gcd(b, a%b);
}

Fraction reduction(Fraction result)   //分数的化简
{
    if(result.down < 0)  //若分母为负数,则令分子和分母都变为相反数
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if(result.up == 0)  //若分子为0,则令分母为1
    {
        result.down = 1; 
    }
    else    //若分子不为0,则进行约分
    {
        int d = gcd(abs(result.up), abs(result.down));    //分子、分母的最大公约数为d
        //约去最大公约数
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction add(Fraction f1, Fraction f2)   //分数的加法
{
    Fraction result;
    result.up = f1.up*f2.down + f1.down*f2.up;   //分数和的分子
    result.down = f1.down*f2.down;    //分数和的分母
    return reduction(result);   //将分数和化简后,返回结果分数
}

Fraction divide(Fraction f1, Fraction f2)    //分数的除法
{
    Fraction result;
    result.up = f1.up*f2.down;     //分数商的分子
    result.down = f1.down*f2.up;   //分数商的分母
    return reduction(result);      //将分数商化简后,返回结果分数
}

void showResult(Fraction result)    //输出分数
{
    result = reduction(result);     //化简分数
    if(result.down == 1)    //整数
    {
        printf("%d\n", result.up);
    }
    else if(abs(result.up) > abs(result.down))   //假分数
    {
        printf("%d %d/%d\n", result.up/result.down, abs(result.up)%result.down, result.down);
    }
    else    //真分数
    {
        printf("%d/%d\n", result.up, result.down);
    }
}

int main()
{
    int N;
    cin >> N;
    Fraction sum;   //分数总和
    bool isVirgin = true;    //判断是不是第一次
    for(int i = 0; i < N; i++)
    {
        Fraction temp;
        scanf("%d/%d",&temp.up,&temp.down);
        if(isVirgin)    //若是第一次
        {
            sum.up = temp.up;
            sum.down = temp.down;
            isVirgin = false;
        }
        else
        {
            sum = add(sum,temp);
        }
    }
    Fraction f;
    f.up = N;
    f.down = 1;
    showResult(reduction(divide(sum,f)));
    return 0;
}

关于授权：

版权意识我还是有的嗷，所以我在发布这篇博客之前还问了一下晴神：能否在博客上引用他在《算法笔记》上写过的关于分数的代码。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/07/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度