C++:
辗转相除法:
每次算最小公倍数和最大公约数都是用的常规思路,本身是不会有错的,但是当数据很大时,就会出现错误,时间复杂度过高
辗转相除法,又称欧几里德算法(Euclidean Algorithm),是求两个数的最大公约数(greatest common divisor)的一种方法。用较大的数除以较小的数,再以除数和余数反复做除法运算,当余数为0时,取当前算式除数为最大公约数
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
例:求38与18的最大公约数
30 / 18 = 1 余 12
18 / 12 = 1 余 6
12 / 6 = 2 余 0
当a<b时其实也是一样的,只不过多了一步
18 / 30 = 0 余 18
30 / 18 = 1 余 12
18 / 12 = 1 余 6
12 / 6 = 2 余 0
格式化输入:
一开始尝试了很多方法,包括头文件,转换成流,分割字符串,但是都很复杂,因为涉及到字符串到字符到整型的转换
本题的输入有两种简单巧妙的方法:
1.采用string里的getchar()略过每个数后面的字符(斜杠或者空格)
int N;
cin>>N;
int number[N*2];
for(int i=0; i<N*2; i++){
cin>>number[i];
getchar();
}
2.cin.ignore()忽视两个整数之间的斜杠,而cin是不会读入空格的
for (int i = 0; i < N; i++)
{
cin >> numerators[i];
cin.ignore(); // 忽略分数中的斜杠
cin >> denominators[i];
}
注意点:
测试点三主要是考察边界,当数字很大时的情况,有两种可能是通过不了测试的
1.先全部通分相加,再约分(数据溢出)
2.没有使用long long int型
输出时注意分类讨论
本题代码
#include <iostream>
#include <vector>
using namespace std;
// 返回两个数的最大公约数
long long int gcd(long long int a,long long int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 返回两个数的最小公倍数
long long int lcm(long long int a,long long int b) {
return a * b / gcd(a, b);
}
/*
//注释掉的为常规思路,但是当数字很大时,时间复杂度过高
// 返回两个数的最大公约数
long long int gcd(long long int a,long long int b) {
int k=1;
for(int i=2;i<=(a<b?a:b);i++){
while(a%i==0 && b%i==0){
a/=i;
b/=i;
k*=i;
}//注意是循环不是判断
}
return k;
}
// 返回两个数的最小公倍数
long long int lcm(long long int a,long long int b) {
return a*b/gcd(a,b);
}
*/
int main() {
int N;
cin >> N;
if(N==0)
{
cout<<0;
return 0;
}
//两个动态数组
vector<int> numerators(N), denominators(N);
//格式化读入数据
for (int i = 0; i < N; i++)
{
cin >> numerators[i];
cin.ignore(); // 忽略分数中的斜杠
cin >> denominators[i];
}
// 初始化和的分子和分母为第一个分数
long long int sum_numerator = numerators[0];
long long int sum_denominator = denominators[0];
for (int i = 1; i < N; i++)
{
// 通分
long long int common_denominator = lcm(sum_denominator, denominators[i]);
sum_numerator = sum_numerator * (common_denominator / sum_denominator) + numerators[i] * (common_denominator / denominators[i]);
sum_denominator = common_denominator;
// 约分
long long int common_factor = gcd(sum_numerator, sum_denominator);
sum_numerator /= common_factor;
sum_denominator /= common_factor;
}
// 输出结果分类讨论
if (sum_denominator == 1 || sum_numerator == 0)
{
cout << sum_numerator;
}
else
{
//提出整数部分,使分子小于分母
if(sum_numerator/sum_denominator!=0)
{
cout<<sum_numerator/sum_denominator<<' ';
}
sum_numerator %= sum_denominator;
if(sum_numerator)
{
cout << sum_numerator << '/' << sum_denominator;
}
}
return 0;
}
Python:
注意点:
1.split分割字符串默认得到列表,所以要转换为整型
2.计算默认为浮点型,输出也要转换
# n个数相加
# 输入
# 5
# 2/5 4/15 1/30 -2/60 8/3
# 输出
# 3 1/3
# 最大公约数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 最小公倍数
def lcm(a, b):
return a * b / gcd(a, b)
N = int(input())
lst = list(map(str,input().split(' ')))
# ['2/5', '4/15', '1/30', '-2/60', '8/3']
lst2=[]
for i in lst:
lst2.append(i.split('/')) # ['2', '5']
sum_a, sum_b = int(lst2[0][0]), int(lst2[0][1])
for i in range(1, N):
# 通分
b_common = lcm(sum_b, int(lst2[i][1]))
sum_a = sum_a * (b_common / sum_b) + int(lst2[i][0]) * (b_common / int(lst2[i][1]))
sum_b = b_common
# 约分
the_common = gcd(sum_a, sum_b)
sum_a /= the_common
sum_b /= the_common
if sum_a == 0 or sum_b == 1:
print(int(sum_a))
else:
if sum_a // sum_b > 0:
print(int(sum_a // sum_b),end=' ')
sum_a = sum_a % sum_b
if sum_a != 0:
print(f"{int(sum_a)}/{int(sum_b)}")