e941 - pB. 分數式運算
題目描述
題目要求讀取一個包含多個分數加減運算的字串，並計算出最終的結果，以最簡分數的形式輸出。輸入包含正分數，也可能包含負分數，分數之間由加號或減號相隔。
解題思路
程式首先讀取分數和運算符號，儲存在 a 陣列中。然後，迭代地將分數加總或減去，並在每次運算後進行簡化。簡化分數的過程是找到分子和分母的最大公因數，然後將分子和分母除以該公因數。最後，輸出簡化後的結果。
程式使用一個結構 f 來表示分數，包含分子 s 和分母 m。spfy 函數用於簡化分數，add 函數用於執行加法運算。主函數負責讀取輸入、執行運算和輸出結果。
複雜度分析
- 時間複雜度: O(N * K)，其中 N 是分數的數量，K 是簡化分數時的最大公因數計算的複雜度。簡化分數的過程，最壞情況下需要迭代到 1000，因此 K 可以視為 O(1000)，整體時間複雜度可以近似為 O(N)。
- 空間複雜度: O(N)，因為程式使用一個大小為 101 的陣列
a來儲存分數。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
struct f{
int s,m;
};
int n;
char tr,d;
f a[101];
f spfy(f x){
if(x.s==0)x.m=1;
for(int i=2;i<=1000&&i<=abs(x.m)&&i<=abs(x.s);++i){
while(x.m&&x.s&&x.m%i==0&&x.s%i==0){
x.m/=i;
x.s/=i;
}
}
return x;
}
f add(f x,f y){
if(y.s==0)return x;
x.s *= y.m;
x.s += y.s*x.m;
x.m *= y.m;
return x;
}
int main(){
cin >> a[n].s >> d >> a[n].m;
++n;
while(cin >> tr){
cin >> a[n].s >> d >> a[n].m;
if(tr=='-')
a[n].s*=-1;
++n;
}
for(int i=0;i<n;++i){
a[i+1]=add(a[i],a[i+1]);
a[i+1]=spfy(a[i+1]);
}
cout << a[n].s << '/' << a[n].m ;
}