首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++求解有关分数的题目

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

作者头像
喜欢ctrl的cxk
发布2019-11-08 10:37:19
3940
发布2019-11-08 10:37:19
举报
文章被收录于专栏:Don的成长史Don的成长史

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接: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:

1

解题思路:

先判断是不是第一次输入,如果是第一次输入就把本次输入的分数赋值给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 条评论
热度
最新
推荐阅读
目录
  • 写在前面:
  • 分数模板:
  • 题目描述:
  • 输入格式:
  • 输出格式:
  • 输入样例1:
  • 输出样例1:
  • 输入样例2:
  • 输出样例2:
  • 解题思路:
  • AC代码:
  • 关于授权:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档