Cộng hai số không lan truyền nhớ (Carry)

Ở đây chúng ta sẽ xem một bài toán, nơi chúng ta sẽ cộng hai số n chữ số nhưng nhớ sẽ không được lan truyền. Chúng ta có thể hiểu khái niệm này qua một ví dụ:

Vì vậy chúng ta thấy ở đây chỉ có các chữ số được cộng và kết quả được đặt. Ở đây có một thủ thuật. Chúng ta phải quét các số từ phải sang trái. Vì vậy tổng 3+2 = 6 sẽ được tính trước, nhưng nó sẽ được đặt ở cuối. Vì vậy chúng ta sẽ dùng stack để lưu trữ kết quả trung gian.

Thuật toán

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

Ví dụ

#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);
}

Kết quả

Result: 1611125