用java程序写L1-009 N个数求和 分数 20 作者 陈越 单位 浙江大学 本题的要求很简单,就是求N个数字的和。麻烦的是,这些数字是以有理数分子/分母的形式给出的,你输出的和也必须是有理数的形式。 输入格式: 输入第一行给出一个正整数N(≤100)。随后一行按格式a1/b1 a2/b2 ...给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外,负数的符号一定出现在分子前面。 输出格式: 输出上述数字和的最简形式 —— 即将结果写成整数部分 分数部分,其中分数部分写成分子/分母,要求分子小于分母,且它们没有公因子。如果结果的整数部分为0,则只输出分数部分。
时间: 2024-02-28 22:57:57 浏览: 25
以下是Java程序实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long ansFenzi = 0, ansFenmu = 1; // ansFenzi存储分子,ansFenmu存储分母,初始化为0/1
for (int i = 0; i < n; i++) {
String[] s = sc.next().split("/");
long fenzi = Long.parseLong(s[0]); // 分子
long fenmu = Long.parseLong(s[1]); // 分母
long gcd = gcd(fenzi, fenmu); // 求分子和分母的最大公约数
fenzi /= gcd;
fenmu /= gcd;
gcd = gcd(ansFenmu, fenmu); // 求ansFenmu和fenmu的最大公约数
ansFenzi = ansFenzi * (fenmu / gcd) + fenzi * (ansFenmu / gcd); // 通分后相加
ansFenmu *= fenmu / gcd; // 计算通分后的分母
gcd = gcd(ansFenzi, ansFenmu); // 求ansFenzi和ansFenmu的最大公约数
ansFenzi /= gcd;
ansFenmu /= gcd;
}
long zheng = ansFenzi / ansFenmu; // 计算整数部分
ansFenzi %= ansFenmu; // 计算分数部分的分子
if (zheng == 0 && ansFenzi == 0) { // 结果为0的情况
System.out.println("0");
} else if (zheng == 0) { // 结果没有整数部分的情况
System.out.println(ansFenzi + "/" + ansFenmu);
} else if (ansFenzi == 0) { // 结果没有分数部分的情况
System.out.println(zheng);
} else { // 结果既有整数部分又有分数部分的情况
System.out.println(zheng + " " + ansFenzi + "/" + ansFenmu);
}
}
// 求最大公约数
private static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
}
```
时间复杂度:$O(nlogmax)$,其中max表示分子和分母的最大值,logmax表示求最大公约数的时间复杂度。
空间复杂度:$O(1)$。