主要内容 #

1. 最大公约数
2. 分数求和

1. 最大公约数 #

问题描述
给定两个正整数，求它们的最大公约数。
输入
一行，包含两个正整数（小于1000000000）
输出
一个正整数，即这两个正整数的最大公约数。
输入样例
6 9
输出样例
3

算法分析 #

最大公约数的算法原来还分为两种，一种是用非递归的算法，一种是递归的算法。
无论是通过递归还是非递归的方法，都是一种求两个数最大公约数的算法——辗转相除法。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。
例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 / 105 = 2余42，所以105和42的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。

参考程序 #

递归算法：

//最大公约数（递归算法）
int gcd( int x , int y){
    if( y == 0 )
	return x;
    else
	return gcd(y,x%y);
   }

从上面可以看出，递归算法极其简短，而下面的非递归算法相对则长一点。

//最大公约数（非递归算法）
int gcd( int x , int y){
	int max,min,temp;
	max = x > y ? x : y ;
	min = x < y ? x : y ;
	while( max % min ){
 
		temp = max % min;
		max = min;
		min = temp;
	}
	return min;
}
//最小公倍数
int lcm( int x , int y ){
	return x*y/gcd(x,y);
}

2. 分数求和 #

问题描述
输入n个分数并对他们求和，并用最简形式表示。所谓最简形式是指：分子分母的最大公约数为1；若最终结果的分母为1，则直接用整数表示。
如：5/6、10/3均是最简形式，而3/6需要化简为1/2,31需要化简为3。
分子和分母均不为0，也不为负数。
输入
第一行是一个整数n，表示分数个数，1≤n≤10；
接下来n行，每行一个分数，用”p/q”的形式表示，不含空格，p，q均不超过10。
输出
输出只有一行，即最终结果的最简形式。若为分数，用”p/q”的形式表示。
输入样例
2
1/2
1/3
输出样例
5/6

算法分析 #

此题求分母的和，我们可以对分子、分母分开求解，最后化简；
最终和的分母，为这些分母的最小公倍数min，所以我们定义一个求最大公约数的函数gcd，通过这些数的乘积sumb除以最大公约数max求得最小公倍数min；
可以参考：最大公约数
把通分后的分子和加起来，然后化简分子分母即可。

参考程序 #

#include < iostream >
using namespace std;

int a[15]; //分子
int b[15]; //分母
//求n个分母的最大公约数
int gcd(int a, int b) {
	return (b == 0 ? a : gcd(b, a % b));
}

int main() {
	int n;
	cin >> n;
	char c;
	int sumb = 1; //求前n个分母的乘积
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> c >> b[i];
		sumb *= b[i];
	}
	int max = 1; //保存n个分母的最大公约数
	//求前n个分母的最大公约数
	for (int i = 0; i < n; i++) {
		max = gcd(max, b[i]);
	}
	//求这n个分母的最小公倍数
	int min = sumb / max;
	int fz = 0, fm;
	//计算n个数的分子和
	for (int i = 0; i < n; i++) {
		fz += (a[i] * (min / b[i]));
	}
	fm = min; //分母就是所有分母的最小公倍数
	//化简
	//先求答案的分子分母的最大公约数
	int maxtemp = gcd(fz, fm);
	//化简分子分母
	fz /= maxtemp;
	fm /= maxtemp;
	if (fm == 1)
		cout << fz;
	else
		cout << fz << "/" << fm;
		cout << endl;
	return 0;
}