캐리를 전파하지 않고 두 숫자의 더하기?

여기서 우리는 두 개의 n자리 숫자를 더하지만 캐리가 전파되지 않는 한 가지 문제를 볼 것입니다. 예제를 통해 이 개념을 이해할 수 있습니다. −

따라서 여기에 숫자만 추가되고 답변이 배치되는 것을 볼 수 있습니다. 여기에 한 가지 트릭이 있습니다. 오른쪽에서 왼쪽으로 숫자를 스캔해야 합니다. 따라서 3+2 =6의 합이 먼저 계산되지만 끝에 배치됩니다. 그래서 우리는 중간 결과를 저장하기 위해 스택을 사용할 것입니다.

알고리즘

noPropagateCarry(a, b)

begin
   size = max of length of a and length of b
   for i in range i to size, do
      al := last digit of a
      bl := last digit of b
      push (al + bl) into stack
      a := a / 10
      b := b /10
   done
   pop and print the elements from stack
end

예시

#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
int length(int n){
   return log10(n) + 1;
}
void noPropagateCarry(int a, int b){
   int size = max(length(a), length(b));
   stack<int> stk;
   for(int i = 0; i <size; i++){
      int al = a % 10; //last digit of a
      int bl = b % 10; //last digit of b
      stk.push(al + bl);
      a = a / 10; b = b/10;
   }
   while(!stk.empty()){
      cout << stk.top();
      stk.pop();
   }
}
main() {
   int a = 7583, b = 9642;
   cout << "Result: ";
   noPropagateCarry(a, b);
}

출력

Result: 1611125