创客社招新测试算法组题解

题目

输入n个分数并对他们求和，并用最简形式表示。若最终结果的分母为1，则直接用整数表示。

如：5/6、10/3均是最简形式，而3/6需要化简为1/2, 3/1需要化简为3。

输入：每行一个分数，用"p/q"的形式表示，不含空格，p，q均不超过10。在输入的最后一行用end结束

输出：输出只有一行，即最终结果的最简形式。若为分数，用"p/q"的形式表示。

样例输入 1/2 1/3 end

样例输出 5/6

分析

本题主要考查了循环的使用和欧几里得算法（辗转相除法）。对于使用C++解题的同学来说，处理输入数据可能也有一定难度（不过OI选手应该能很容易想到）

具体来说，我们可以把程序分成几部分解决。

首先，在输入数据的处理上，我们可以输入一个字符串，然后转换成 int类型。比如说这样：

int n=0,inp[100][2];
string a;
while(cin>>a){
	if(a=="end") break;
	inp[n][0]=a[0]-'0',inp[n][1]=a[2]-'0'; 
	n++; //n为分数数量 
}

这样做的缺点比较明显，如果输入的p或者q刚好是10，那我们还需要进一步修改，比较复杂。为此，我们可以使用下列做法：

while(scanf("%d/%d",&inp[n][0],&inp[n][1])){
	n++;
}

学习过信息学竞赛的同学们应该有所了解，这样写的话既能一直读入数据，而且当读入数据不是 int型的时候就会停止读入（例如题目中的 end）。

接着，我们来讨论下核心代码。（敲黑板！！！）

思路很容易想到，先把分数通分相加，等计算出最终结果之后，我们再对最终结果进行约分。约分找最大公约数的时候我们可以用到一个非常常用的算法——欧几里得算法（辗转相除法）。你可以手写一个 gcd函数，也可以用C++内置的 __gcd()函数，头文件是 <algorithm>（或者用万能头）。

最后，输出之前特判一下分母为1的情况即可。

参考代码

#include <bits/stdc++.h> //万能头文件
using namespace std;
int inp[100][2]; //存储输入数据的数组
int gcd(int x,int y){
	if(x%y==0) return y;
	else return gcd(y,x%y);
} //当然你也可以用自带的__gcd(x,y)函数  
int main(){
	int n=0;
	while(scanf("%d/%d",&inp[n][0],&inp[n][1])){
		n++;
	}
	int fenzi=inp[0][0],fenmu=inp[0][1];
	for(int i=1;i<n;i++){ 
		fenzi=fenzi*inp[i][1]+inp[i][0]*fenmu;
		fenmu*=inp[i][1];//通分 
	}
	int tmp=gcd(fenmu,fenzi);
	fenmu/=tmp,fenzi/=tmp;
	if(fenmu!=1)
		cout<<fenzi<<"/"<<fenmu;
	else 
		cout<<fenzi;
	return 0;
}

其实这个代码还有一个缺点：inp数组的大小取决于输入分数的个数，如果输入的分数很多很多，要定义一个足够大的数组，比较占用空间。

那这个问题怎么解决呢？聪明的你或许已经想到，我们可以只关心正在输入的分数和下一个输入的分数，没有必要保存每一个分数。这种思路在数据多的时候相当实用，大大降低了空间复杂度。

思维提高

1. 试着写一份不必保存输入的每个分数的改进代码
2. 有能力的同学可以挑战下 P1572 计算分数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)