c034 - 00424 - Integer Inquiry
題目描述
題目要求實作一個能處理任意長度正整數加法的程式。輸入為多個正整數字串，直到輸入為 "0" 時結束，程式需計算並輸出所有輸入數字的和。由於整數長度可能超過標準資料型態的限制，因此需要使用字串來表示和操作這些數字。
解題思路
程式使用字串來模擬大數加法。主要邏輯如下：
- 讀取輸入字串，直到讀取到 "0" 為止。
- 每次讀取一個字串後，將其加到目前累計的結果字串上。
- 在加法過程中，需要處理進位。從字串的最低位開始，將對應位元的數字相加，如果結果大於 9，則將進位加到下一位。
- 在加法之前，需要確保兩個字串的長度相同。如果長度不同，則在較短的字串前面補 0。
- 加法完成後，檢查結果字串是否有進位，如果有，則在字串前面插入 "1"。
複雜度分析
- 時間複雜度: O(N*M)，其中 N 是輸入數字的個數，M 是最長數字的長度。因為每次加法需要遍歷字串的每個位元。
- 空間複雜度: O(M)，其中 M 是最長數字的長度。因為需要一個字串來儲存累計的結果。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
string a,b,tem;
bool p=false;
cin >> a >> b;
while(b!="0"){
if(a.length()<b.length()){
tem=a;
a=b;
b=tem;
}
else{
int k=b.length();
for(int i=0;i<a.length()-k;i++){
b.insert(0,"0");
}
}
if(a.length()==b.length()){
for(int i=0;i<a.length();i++){
a[i]+=b[i]-48;
}
cin >> b;
for(int i=1;i<a.length();i++){
for(int j=1;j<a.length();j++){
if(a[j]>=58){
a[j-1]++;
a[j]-=10;
}
}
}
if(a[0]>=58){
p=true;
a[0]-=10;
}
if(p==true){
a.insert(0,"1");
p=false;
}
}
}
cout << a << endl;
}