本题的要求很简单,就是求n个数字的和。麻烦的是,这些数字是以有理数分子/分母的形式给出的,你输出的和也必须是有理数的形式。 输入格式: 输入第一行给出一个正整数n(≤100)。随后一行按格式a1/b1 a2/b2 ...给出n个有理数。题目保证所有分子和分母都在长整型范围内。另外,负数的符号一定出现在分子前面。 输出格式: 输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分,其中分数部分写成分子/分母,要求分子小于分母,且它们没有公因子。如果结果的整数部分为0,则只输出分数部分。
时间: 2023-05-31 20:19:05 浏览: 271
### 回答1:
这道题的要求是求n个有理数的和,并将结果输出为最简形式。输入中给出了n个有理数的分子和分母,保证所有数字都在长整型范围内,负数的符号出现在分子前面。输出中需要将整数部分和分数部分分开输出,分数部分要求分子小于分母,且没有公因子。如果结果的整数部分为0,则只输出分数部分。
### 回答2:
题目分析:
此题求有理数之和,输入格式是以分数给出的,算法需要将分数化简,求出分子和分母,再将这些分数相加。最后对结果进行化简,化简的思路就是求分子和分母的最大公约数,用它们除以最大公约数即可。
解题思路:
可以将分数处理成同分母的形式,然后分别加起来,再化简分数即可。
我们可以用两两求解的方式来处理这些分数,设 $sum = \dfrac{a}{b}$,$a$ 为分子,$b$ 为分母。
每输入一个分数时,设这个分数为 $\dfrac{x}{y}$,$x$ 为新输入的分子,$y$ 为新输入的分母。那么整理 $sum + \dfrac{x}{y}$,计算过程为 $sum = \dfrac{a}{b}$,则
$$
sum + \dfrac{x}{y} = \dfrac{a}{b} + \dfrac{x}{y} = \dfrac{a \cdot y + x \cdot b}{b \cdot y}
$$
以此类推,直到所有输入分数都处理完毕。最后化简分数的过程为:求出分子与分母的最大公约数 $gcd$,用分子与分母分别除以 $gcd$。
代码实现:
### 回答3:
题目的要求很简单,就是要求我们计算输入的n个有理数的和,并输出最简分数形式的结果。
首先需要将输入的有理数相加,这需要先将每一个有理数的分母通分,然后将它们的分子相加,最后将得到的和分母化简即可。
具体操作如下:
1. 读入n
2. 读入n个有理数,将它们分别表示成分子和分母两个long long类型的变量
3. 将所有输入的有理数的分母求最小公倍数,得到通分的分母
4. 将每个分子乘以通分的分母/原分母,然后相加,得到分子的和
5. 将得到的分子分母同时除以它们的最大公约数,得到最简分数
下面给出具体代码实现:
```
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
long long gcd(long long a, long long b)
{
return (b == 0) ? a : gcd(b, a % b);
}
int main()
{
int n;
scanf("%d", &n);
long long lcm = 1; // 通分的分母
for (int i = 0; i < n; i++)
{
long long a, b;
scanf("%lld/%lld", &a, &b);
// 求最小公倍数
lcm = lcm / gcd(lcm, b) * b;
// 将每个分子乘以通分的分母/原分母
a *= lcm / b;
// 相加得到分子的和
lcm = gcd(lcm, a) * (lcm / gcd(lcm, a)) + abs(a);
}
// 求最简分数
long long GCD = gcd(lcm, abs(lcm)); // 分子分母的最大公约数
lcm /= GCD;
long long numerator = lcm < 0 ? -lcm : lcm;
long long denominator = gcd(lcm, abs(lcm));
if (numerator >= denominator)
{
printf("%lld", numerator / denominator);
numerator %= denominator;
if (numerator != 0)
{
printf(" ");
}
}
if (numerator != 0)
{
printf("%lld/%lld", numerator, denominator);
}
if (numerator == 0)
{
printf("0");
}
return 0;
}
```
时间复杂度:假设输入的每个有理数的分母都在long long的取值范围之内,则通分的分母最大为n!*10^18,求最小公倍数的时间复杂度为O(n^2 * log(n * 10^18)),而求最大公约数和带符号取余数的时间复杂度是常数级别的,因此总的时间复杂度为O(n^2 * log(n * 10^18))。
空间复杂度:除了读入的n和每个数字的分子和分母,其他的变量都是常数级别的,因此总的空间复杂度为O(n)。
阅读全文