首页 > > 程序设计 > C/C++ >

暴力+辗转相除法——N个数求和

2020-03-24 16:02:54来源：博客园阅读 ()

暴力+辗转相除法——N个数求和从题目“分子/分母”的输入形式可以看出我们不能采用scanf和cin直接输输入值而要采用字符输入再转换为数值计算过程中判断好符号暴力通分直接加减即可防止通分过程超出长整型范围最好每一步结果都约分我最开始暴力约分来着发现会超时就用欧几里得算法了不麻烦也不会超时输出时注意题目要求的形式想仔细一点每种条件怎么输出即可

题目来源

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

https://pintia.cn/problem-sets/994805046380707840/problems/994805133597065216

题目描述

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

输入样例3：

3
1/3 -1/6 1/8

输出样例3：

7/24

思路

从题目“分子/分母”的输入形式可以看出我们不能采用scanf和cin直接输输入值而要采用字符输入再转换为数值

计算过程中判断好符号暴力通分直接加减即可

防止通分过程超出长整型范围最好每一步结果都约分

我最开始暴力约分来着发现会超时就用欧几里得算法了不麻烦也不会超时

输出时注意题目要求的形式想仔细一点每种条件怎么输出即可

代码

 1 #include <cstdio>
 2 using namespace std;
 3 int n,o=1,oo; char x=1; //o-结果是否为非负数 oo-当前输入的有理数是否为非负数
 4 long long p,q,f=0,g=1,c;
 5 inline long long read(); //快读 由于分子分母间有‘/’分隔且分母一定是正数 标准快读模板即可完成
 6 inline int yue(long long a,long long b);//求a和b的最大公约数
 7 int main()
 8 {
 9 　　scanf("%d",&n); 
10 　　for(int i=1;i<=n;i++)
11 　　{
12 　　　　while(!(x>=48&&x<=57)&&x!='-')
13 　　　　　　x=getchar();
14 　　　　if(x=='-') oo=0;
15 　　　　else    oo=1; //判断当前输入的有理数是否为非负数
16　　　　 p=read();
17 　　　　q=read(); //以“|p/q|”形式读入当前有理数
18 　　　　p*=g;
19 　　　　f*=q;
20 　　　　g*=q; //暴力通分 本题数据范围内没有超出长整型
21 　　　　if((o&&oo)||(!o&&!oo)) //如果结果和当前输入有理数同号 只要分子绝对值部分相加即可
22 　　　　　　f+=p;
23 　　　　else if(o&&!oo) //如果结果为正 当前输入有理数为负 则需要比较结果与当前输入有理数的大小来确定此次运算后结果的符号 
24 　　　　{
25 　　　　　　if(f>=p) //当前结果大于当前输入有理数的绝对值 结果仍为正数 以下同理 
26 　　　　　　　　f-=p;
27 　　　　　　else
28 　　　　　　　　o=0,f=p-f;
29 　　　　}
30 　　　　else if(!o&&oo)
31 　　　　{
32 　　　　　　if(f>=p)
33 　　　　　　　　o=1,f-=p;
34 　　　　　　else
35 　　　　　　　　f=p-f;
36 　　　　}
37 　　　　int u=yue(f,g); //u为f和g的最大公约数
38 　　　　f/=u;
39 　　　　g/=u; //约分
40 　　}
41 　　if(o==0) printf("-"); //如果结果是负数 输出负号
42　　 if(f==0)    printf("0"); //如果结果是0 输出0
43 　　else if(f%g==0)    printf("%lld",f/g); //如果结果可以约分为整数
44 　　else if(g%f==0) printf("1/%lld",g/f);//如果结果可以约分为“1/x”形式
45 　　else if(f>g) //如果结果的分子大于分母 即结果为假分数 需要转化为带分数
46 　　{
47 　　　　printf("%lld ",f/g); //整数部分
48 　　　　f%=g;
49　　　　 printf("%lld/%lld",f,g); //分数部分
50 　　}
51 　　else
52　　　　 printf("%lld/%lld",f,g); //如果结果为真分数
53 　　return 0;
54 }
55 inline int yue(long long a,long long b) //欧几里得算法 亲测暴力约分会超时
56 {
57 　　if(a>b) c=a,a=b,b=c; 
58 　　while(a!=0) //
59 　　{
60 　　　　while(b>=a) //标准%运算比较慢 直接减
61 　　　　　　b-=a;
62 　　　　c=a,a=b,b=c;
63 　　}
64 　　return b;
65 }
66 inline long long read()
67 {
68 　　long long s=0;
69 　　while(!(x>=48&&x<=57))
70 　　　　x=getchar();
71 　　while(x>=48&&x<=57)
72 　　　　s*=10,s+=x-48,x=getchar();
73 　　return s;
74 }