c014 - 10035 - Primary Arithmetic
題目描述
題目要求計算兩個正整數相加時產生的進位次數。輸入為兩組正整數，直到輸入為兩個 0 時結束。輸出為進位的次數，根據進位次數的不同，輸出格式也會有所不同。
解題思路
此題的核心是模擬小學加法的過程，逐位進行相加，並記錄進位次數。由於輸入的數字是字串形式，需要將字串轉換為數字進行計算。為了方便計算，需要先將兩個數字補零，使它們的長度相同。然後，從最低位開始，逐位相加，如果相加的結果大於等於 10，則產生一次進位，並將進位值加到下一位的計算中。
複雜度分析
- 時間複雜度: O(N)，其中 N 是輸入數字的長度。因為需要遍歷字串的每個位元進行相加。
- 空間複雜度: O(N)，主要用於儲存補零後的字串。
程式碼
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main (){
string a;
string b;
string d;
int ans=0;
int c=0;
int e=0;
while(cin >> a >> b){
for(int i=0;i<abs(a.length()-b.length());i++){
d.push_back('0');
if(a.length()>b.length()){
d=d+b;
b=d;
}
else{
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 << " carry operations." << endl;
}
if(ans==1){
cout << ans << " carry operation." << endl;
}
if(ans==0){
cout << "No carry operation." << endl;
}
ans=0;
}
}