การบวกสองจำนวนโดยไม่ส่งผ่าน Carry (No Carry Propagation)

ที่นี่เราจะดูปัญหา บวกสองจำนวน n หลัก แต่ไม่ส่งผ่าน carry สามารถเข้าใจได้จากตัวอย่าง

เห็นได้ว่าแค่บวกแต่ละหลักแยกกัน ไม่ส่ง carry ไปหลักถัดไป ทริกคือต้องอ่านตัวเลขจากขวาไปซ้าย ผลรวม 3+2=6 คำนวณก่อนแต่จะวางท้ายสุด จึงใช้ Stack เก็บผลลัพธ์ชั่วคราว

อัลกอริทึม

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

ตัวอย่างโค้ด (C++)

#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 stk;
    for (int i = 0; i < size; i++) {
        int al = a % 10;
        int bl = b % 10;
        stk.push(al + bl);
        a = a / 10; b = b / 10;
    }
    while (!stk.empty()) {
        cout << stk.top();
        stk.pop();
    }
}

int main() {
    int a = 7583, b = 9642;
    cout << "Result: ";
    noPropagateCarry(a, b);
}

ผลลัพธ์

Result: 1611125