Bài toán cộng số lớn

Khi số có độ dài quá lớn chúng ta không thể diễn tả giá trị bằng kiểu int, double, long mà phải dùng mảng ký tự string.

Cần xây dựng thuật toán mô phỏng lại việc cộng 2 số nguyên. Khi cộng 2 chữ số cùng hệ số (thứ tự tính từ phải qua trái), nếu tổng vượt quá 10 cần phải có biến nhớ, gọi là carry.

Ảnh chụp 141 "Data Structure and Algorithm in C++" của Adam Drozdek

Thuật toán: Việc cộng diễn ra tuần tự từ các chữ số có hệ số thấp nhất cho đến hết. Tổng mỗi lần cộng sẽ đẩy vào stack, nếu có nhớ thì lưu vào biến

char* addBigNumber(char* n1, char* n2) {
    struct Stack* result = createStack(40);
    int top1 = strlen(n1); // Stack counter for string n1
    int top2 = strlen(n2); // Stack counter for string n2
    int carry = 0;

    while (top1 > 0 || top2 > 0) {
        top1 = top1 - 1;
        top2 = top2 - 1;
        int v1 = 0, v2 = 0;
        if (top1 >= 0) {
            v1 = n1[top1] - '0';
        }

        if (top2 >= 0) {
            v2 = n2[top2] - '0';
        }
        int temp = v1 + v2 + carry; //tổng của 2 chữ số đồng hạng hệ số

        carry = temp / 10; //nếu tổng hơn 10 thì nhớ sang cột bên cạnh
        temp = temp % 10;

        push(result, temp); //chồng kết quả lên stack 

    }

    char *string = malloc(result->top * sizeof(char));
    memset(string, 0, result->top);
    int i = 0;
    while (!isStackEmpty(result)) {
        int a;
        pop(result, &a);
        string[i] = a + '0';
        i++;
    }
    deleteStack(result);
    return string;

}

int main() {
    char* string = addBigNumber("23342324591", "324234234234323784");
    printf("%s\n", string);
    return 0;
}

Full Source code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

struct Stack {
    int top;
    int capacity;
    int *array;
};

struct Stack* createStack(int capacity) {
    struct Stack* s = malloc(sizeof(struct Stack));
    if (!s) {
        return NULL;
    }

    s->capacity = capacity;
    s->top = -1;
    s->array = (int*) malloc(s->capacity * sizeof(int));
    if (!s->array) {
        return NULL;
    }
    return s;
}

bool isStackEmpty(struct Stack* s) {
    return (s->top == -1);
}

bool isStackFull(struct Stack* s) {
    return (s->top == s->capacity -1);
}

bool push(struct Stack* s, int data) {
    if (isStackFull(s)) {
        printf("Stack is over flow\n");
        return false;
    } else {
        s->array[++s->top] = data;
        return true;
    }
}


bool pop(struct Stack*s, int* data) {
    if (isStackEmpty(s)) {
        printf("Stack is empty");
        return false;
    } else {
        *data = s->array[s->top--];
        return true;
    }
}

void deleteStack(struct Stack*s) {
    if (s) {
        if (s->array) {
            free(s->array);
        }
        free(s);
    }
}


char* addBigNumber(char* n1, char* n2) {
    struct Stack* result = createStack(40);
    int len1 = strlen(n1);
    int len2 = strlen(n2);
    int top1 = len1; // Stack counter for string n1
    int top2 = len2; // Stack counter for string n2
    int carry = 0;

    while (top1 > 0 || top2 > 0) {
        top1 = top1 - 1;
        top2 = top2 - 1;
        int v1 = 0, v2 = 0;
        if (top1 >= 0) {
            v1 = n1[top1] - '0';
        }

        if (top2 >= 0) {
            v2 = n2[top2] - '0';
        }
        int temp = v1 + v2 + carry;

        carry = temp / 10;
        temp = temp % 10;

        push(result, temp);

    }

    char *string = malloc(result->top * sizeof(char));
    memset(string, 0, result->top);
    int i = 0;
    while (!isStackEmpty(result)) {
        int a;
        pop(result, &a);
        string[i] = a + '0';
        i++;
    }
    deleteStack(result);
    return string;

}

int main() {
    char* string = addBigNumber("23342324591", "324234234234323784");
    printf("%s\n", string);
    return 0;
}