c830 - 第一題：小數加法
題目描述
題目要求實作一個小數加法程式，輸入兩個小數（以字串形式表示），輸出它們的和，結果也以字串形式表示。小數部分可能長度不一，需要進行補零操作。加法結果以 7 為底數表示。
解題思路
程式首先讀取兩個小數字串。然後，將字串轉換為 7 進數的整數表示。對於小數部分，程式會將小數點後面的數字視為 7 的負冪。接著，將兩個 7 進數的整數相加。最後，將結果轉換回 7 進數的字串表示，並在適當的位置插入小數點。程式處理了小數點不存在的情況，並在必要時補零。
複雜度分析
- 時間複雜度: O(max(len(a), len(b)))，其中 len(a) 和 len(b) 分別是輸入字串 a 和 b 的長度。這是因為程式需要遍歷字串以進行轉換和加法。
- 空間複雜度: O(max(len(a), len(b)))，因為程式需要儲存轉換後的 7 進數整數和結果字串，其大小與輸入字串的長度成正比。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
string a,b;
while(cin >> a >> b){
int al=a.length(),bl=b.length(),ai=0,bi=0;
int xa=0,ya=0,xb=0,yb=0;
while(a[ai]!='.'&&ai<al){
xa*=7;
xa+=a[ai]-48;
ai++;
}
while(b[bi]!='.'&&bi<bl){
xb*=7;
xb+=b[bi]-48;
bi++;
}
xa+=xb;
if(a[ai]=='.'){
ai++;
}
else{
a+='.0';
al++;
ai++;
}
if(b[bi]=='.'){
bi++;
}
else{
b+='.0';
bl++;
bi++;
}
string ad,bd;
while(ai<al){
ad+=a[ai];
ai++;
}
while(bi<bl){
bd+=b[bi];
bi++;
}
int adl=ad.length(),bdl=bd.length();
while(adl>bdl){
bd+='0';
bdl++;
}
while(bdl>adl){
ad+='0';
adl++;
}
for(int i=adl-1;i>0;i--){
if(ad[i]+bd[i]-96>6){
ad[i-1]++;
ad[i]-=7;
}
ad[i]+=bd[i]-48;
}
if(ad[0]+bd[0]-96>6){
ad[0]-=7;
ad[0]+=bd[0]-48;
xa++;
}
else{
ad[0]+=bd[0]-48;
}
string ans;
if(xa==0)cout << 0;
while(xa>0){
ans+=xa%7+48;
xa/=7;
}
for(int j=ans.length()-1;j>=0;j--){
cout << ans[j];
}
for(int j=0;j<ad.length();j++){
if(ad[j]!='0'){
cout << '.' << ad;
break;
}
}
cout << "\n";
}
}