Длинное сложение

Question

Даны числа N, M, A, B, где N - длина числа A, M - длина числа B.

Требуется найти и вывести сумму чисел A и B.

Входные значения

Со стандартного устройства ввода в первой строке вводятся числа N (1 <= N <= 1000) - длина числа A и M (1 <= M <= 1000) — длина числа B.

Во второй строке вводится число A(1 <= A).

В третьей строке вводится число B(1 <= B).

Выходные значения

Требуется найти и вывести сумму чисел A и B. Выводить пробел в конце строки не нужно.

Пример входных данных

17 17

56356356456456456

87987987897897980

Пример выходных данных

144344344354354430

Answer 1

Учитывая небольшую длину (до 1000 цифр), я решил написать программу, которая складывает по-циферно (как в школьном алгоритме), в реальных библиотеках длинной арифметики складывают не по-циферно, а машинными словами (по 32 или 64 бита), для эффективности и скорости.

Благодаря по-циферному сложению не нужно даже переводить в двоичную форму числа, прямо символы и складываем.

Попробовать онлайн!

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>

#define MIN(X, Y) (((X) <= (Y)) ? (X) : (Y))
#define MAX(X, Y) (((X) >= (Y)) ? (X) : (Y))

int main() {
    int N = 0, M = 0;
    if (scanf("%d %d\n", &N, &M) != 2 || N < 1 || N > 1000 || M < 1 || M > 1000) {
        printf("Bad N, M!\n");
        return -1;
    }
    char A[1024], B[1024], C[1024];
    memset(C, 0, sizeof(C));
    int K = sizeof(C) - 1;
    fgets(A, N + 2, stdin);
    fgets(B, M + 2, stdin);
    if (strlen(A) != N + 1 || strlen(B) != M + 1) {
        printf("Bad nums lengths %d and %d!\n", ((int)strlen(A)) - 1, ((int)strlen(B)) - 1);
        return -1;
    }
    A[N] = 0;
    B[M] = 0;
    int carry = 0;
    for (int i = 1, hi = MAX(N, M) + 1; i <= hi; ++i) {
        int sum = (i <= N ? A[N - i] - '0' : 0) + (i <= M ? B[M - i] - '0' : 0) + carry;
        if (sum >= 10)  {
            carry = 1;
            sum -= 10;
        } else
            carry = 0;
        C[K - i] = (char)(sum + '0');
    }
    char const * pC = C;
    while (!*pC)
        ++pC;
    while (*(pC + 1) && *pC == '0')
        ++pC;
    printf("%s\n", pC);
    return 0;
}

Ввод:

17 17
56356356456456456
87987987897897980

Вывод:

144344344354354436

БЛОГ НА HUSL

Длинное сложение

Ответы (1 шт):