d787 - 四、進位
題目描述
題目要求計算兩個大整數相加時，產生進位的次數。輸入包含多組測試資料，每組資料包含兩個大整數，以空格分隔。
解題思路
程式碼首先讀取測試資料組數 k。然後，在迴圈中讀取每組測試資料的兩個字串 a 和 b，代表兩個大整數。程式碼將較短的字串前面補零，使其長度與較長的字串相同。接著，程式碼從字串的最低位開始，模擬加法運算，並計算進位的次數。如果加法結果大於等於 10，則產生進位，進位次數加 1，並將進位值 e 設為 1。否則，進位值 e 設為 0。最後，程式碼輸出進位次數。如果兩個數都是0，則跳出迴圈。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串的最大長度。因為程式碼需要遍歷字串的每一位來進行加法運算。
- 空間複雜度: O(n)，其中 n 是字串的最大長度。因為程式碼需要使用額外的字串
d來儲存補零後的字串。
程式碼
#include <iostream>
#include <string>
using namespace std;
int main (){
string a;
string b;
string d;
int ans=0;
int c=0;
int e=0;
int k=0;
cin >> k;
while(cin >> a >> b){
if(a.length()>b.length()){
for(int i=0;i<a.length()-b.length();i++){
d.push_back('0');
}
d = d+b;
b=d;
}
else if(a.length()<b.length()){
for(int i=0;i<b.length()-a.length();i++){
d.push_back('0');
}
d = d+a;
a=d;
}
d.clear();
if(a=="0"&&b=="0"){
break;
}
for(int j=b.length()-1,i=a.length()-1;j>=0&&i>=0;j--){
c=a[i]-48+b[j]-48;
c+=e;
if(c<10){
e=0;
}
if(c>=10){
e=1;
ans++;
}
i--;
}
e=0;
if(ans>=1){
cout << ans << endl;
}
if(ans==0){
cout << 0 << endl;
}
ans=0;
}
}