g731 - 110北二2.分數計算學習器
題目描述
題目要求讀取多個分數的加法表達式，並將其化簡成最簡分數形式輸出。輸入包含多個分數，以 + 號分隔，最後輸出計算結果。
解題思路
這題的核心是處理分數的加法。程式首先讀取所有分數，然後依序將它們加總。在加總的過程中，需要將分數通分，也就是將所有分數的分母化為相同的數。為了避免數字過大，程式在加總後會計算分子和分母的最大公約數 (GCD)，並將分子和分母同時除以 GCD，以化簡分數。程式使用迴圈迭代處理每個分數，並逐步更新結果。
複雜度分析
- 時間複雜度: O(n * log(max_value))，其中 n 是輸入分數的數量，log(max_value) 是計算 GCD 的時間複雜度，max_value 是分子或分母的最大值。
- 空間複雜度: O(n)，用於儲存輸入的分數。
程式碼
#include <iostream>
using namespace std;
long long a[20000][2],n,tmp;
char d;
long long gcd(long long x,long long y){
while(x%y){
x%=y;
swap(x,y);
}
return y;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> a[n][0] >> d >> a[n][1];
++n;
while(cin >> d){
cin >> a[n][0] >> d >> a[n][1];
++n;
}
for(int i=0;i<n-1;++i){
cout << "=";
a[i][0]*=a[i+1][1];
a[i+1][0]*=a[i][1];
a[i+1][0]+=a[i][0];
a[i+1][1]*=a[i][1];
tmp=gcd(a[i+1][1],a[i+1][0]);
a[i+1][0]/=tmp;
a[i+1][1]/=tmp;
for(int j=i+1;j<n;++j){
cout << a[j][0] << "/" << a[j][1];
if(j<n-1){
cout << "+";
}
else{
cout << "\n";
}
}
}
}