目前小说网站排名深圳网站制作哪家便宜
目录
⭐题目描述⭐
⭐分析
⭐程序代码
运行结果
⭐文案分享⭐
⭐题目描述⭐
本题的要求很简单，就是求
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
⭐分析
我们可以用两个变量sum和num来计算分子和分母的变化，一开始我们将sum的值赋为0，num的值赋为1，然后字母a为输入分数的分子，b为分母，以样例测试一为例：
5 2/5 4/15 1/30 -2/60 8/3算法描述为：
for(int i=0;i<N;i++){scanf("%d/%d",&a,&b);sum*=b;sum+=num*a;num*=b;int s=num_GY(num,sum);//寻找num和sum的最大公约数sum=sum/s;//将分子和分母最简化num=num/s;}
sum=0 a num=1 b sum=0*5=0
sum=0+1*2=2
2 num=1*5=5 5 sum=2/1=2 sum和num的最大公约数为1 num=5/1=5 sum和num的最大公约数为1 sum=2*15=30
sum=30+5*4=50
4 num=5*15=75 15 sum=50/25=2 sum和num的最大公约数为25 num=75/25=3 sum和num的最大公约数为25 sum=2*30=60
sum=60+3*1=63
1 num=3*30=90 30 sum=63/9=7 sum和num的最大公约数为9 num=90/9=10 sum和num的最大公约数为9 sum=7*60=420
sum=420+10*(-2)=400
-2 num=10*60=600 60 sum=400/200=2 sum和num的最大公约数为200 num=600/200=3 sum和num的最大公约数为200 sum=2*3=6
sum=6+3*8=30
8 num=3*3=9 3 sum=30/3=10 sum和num的最大公约数为3 num=9/3=3 sum和num的最大公约数为3
求两个数的最大公约数，我们可以用辗转相除法，这样我们的程序的时间复杂度是O(n)，如果我们在写算法题的过程中遇到超时问题，请先检查我们的算法是否有循环套循环的过程，如果有，请想办法去掉一层循环来降低我们的算法时间复杂度。
辗转相除法的算法描述：
int num_GY(int num,int sum){//寻找分子分母的最大公约数int min=num<sum?num:sum;//找出两个数的最小值int max=num>sum?num:sum;//找出两个数的最大值int t;while(min!=0){//利用辗转相除法计算最大公约数t=max%min;max=min;min=t;}return max; }举例：
我们可以任意找两个数，比如63和90，我们来用辗转相除法求最大公约数。
首先我们先判断出这两个数的最大值和最小值。
int min=num<sum?num:sum;//找出两个数的最小值 int max=num>sum?num:sum;//找出两个数的最大值
循环 t max=90 min=63 第一次循环（min!=0) t=90%63=27 max=63 min=27 第二次循环（min!=0) t=63%27=9 max=27 min=9 第三次循环（min!=0) t=27%9=0 max=9 min=0 第四次循环（min==0) 退出循环 返回max=9 结束
⭐程序代码
#include<stdio.h>
int num_GY(int num,int sum){//寻找分子分母的最大公约数int min=num<sum?num:sum;//找出两个数的最小值int max=num>sum?num:sum;int t;while(min!=0){//利用辗转相除法计算最大公约数t=max%min;max=min;min=t;}return max;
}
int main(){int N;scanf("%d",&N);int a,b;int sum=0,num=1;//sum为分子和，num为分母和for(int i=0;i<N;i++){scanf("%d/%d",&a,&b);sum*=b;sum+=num*a;num*=b;int s=num_GY(num,sum);sum=sum/s;//将分子和分母最简化num=num/s;}if(sum%num==0)//当分子是分母的倍数时printf("%d",sum/num);else if(sum<num)//当分子小于分母时printf("%d/%d",sum,num);else//当分子大于分母时printf("%d %d/%d",sum/num,sum%num,num);return 0;
}💖运行结果💖
⭐文案分享⭐
永远相信美好的事情即将发生。--------2023.12.2💖