b538 - 分數運算-2
題目描述
題目要求實作分數的四則運算（加、減、乘、除），並將結果化簡為最簡分數。輸入為兩個分數 a/b 和 c/d，以及一個運算符號。輸出為運算結果，若結果為整數則輸出整數，否則輸出最簡分數 p/q。
解題思路
程式碼首先讀取兩個分數 a/b 和 c/d，以及運算符號。根據運算符號執行相應的運算。加法和減法需要通分，乘法和除法則直接計算分子和分母。計算完結果後，程式碼會判斷結果是否為負數，並處理負號。接著，程式碼會判斷分子是否為 0，如果是則輸出 0。如果分子和分母相等，則輸出 1。否則，程式碼會計算分子和分母的最大公約數（GCD），並用 GCD 化簡分數。最後，程式碼會根據結果是整數還是分數，輸出相應的格式。
複雜度分析
- 時間複雜度: O(log(min(a,b)))，主要來自於 GCD 的計算。在最壞情況下，GCD 的時間複雜度為 log(min(a, b))。其餘運算都是常數時間。
- 空間複雜度: O(1)，程式碼只使用了常數個變數。
程式碼
#include <iostream>
using namespace std;
int gcd(int m,int n){
if(m%n==0)
return n;
return gcd(n,m%n);
}
int main(){
int a,b,c,d;
char x;
while(cin >> a >> b >> c >> d >> x){
if(x=='+'){
a*=d;
c*=b;
b*=d;
a+=c;
}
else if(x=='-'){
a*=d;
c*=b;
b*=d;
a-=c;
}
else if(x=='*'){
a*=c;
b*=d;
}
else if(x=='/'){
a*=d;
b*=c;
}
bool ans=0;
if(a*b<0)
ans=1;
if(a<0)
a*=-1;
if(b<0)
b*=-1;
if(a==0)
printf("0\n");
else if(a==b)
printf("1\n");
else if(a>b){
if(ans==1)printf("-");
if(a%b==0)
printf("%d\n",a/b);
else{
int ans=gcd(a,b);
printf("%d/%d\n",a/ans,b/ans);
}
}
else{
if(ans==1)printf("-");
if(b%a==0)
printf("1/%d\n",b/a);
else{
int ans=gcd(b,a);
printf("%d/%d\n",a/ans,b/ans);
}
}
}
}