Добавление двух строк из цифр рекурсивно в C

Question

Для этой проблемы я должен сначала взять две строки, используя fgets. Затем мне нужно проверить, состоит ли строка целиком из цифр, что делает ее числом. Я смог выполнить эту часть рекурсивно, но следующей задачей является то, что строки являются числами, мне также нужно суммировать их рекурсивно. Так, например, выход программы может выглядеть примерно так:

Первый номер> 9023905350290349

Второй номер> 90283056923840923840239480239480234

сумма 90283056923840923849263385589770583

Опять же, мне нужно сделать это рекурсивно, поэтому я думал, что могу идти по потоку цифр и добавлять их вместе, но я не уверен, как писать эту программу рекурсивно. Кроме того, поскольку вход в форме символов, я также должен был бы преобразовать его в целое число, которое, я полагаю, могу сделать, преобразовывая отдельные символы в целое значение ASCII, а затем вычитая 48 от него. Любая помощь будет оценена по достоинству. Благодаря!

Answer 1

ОБНОВЛЕНИЕ: комментарий ниже дал мне понять, что я, очевидно, неправильно понял вопрос. Разумеется, мое предыдущее решение не работало бы с огромными числами, как в вопросе OP. Соответственно, я обновил свой ответ как подход «справа налево». Единственная проблема заключается в том, что результирующая строка может иметь ведущий нуль ...

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

void add_helper(const char *s1, const char *s2, int s1_pos, int s2_pos, 
       char *result, int pos, int carry) { 
    int d1 = 0; 
    int d2 = 0; 

    if (s1_pos >= 0) { 
     d1 = s1[s1_pos] - '0'; 
     s1_pos--; 
    } 

    if (s2_pos >= 0) { 
     d2 = s2[s2_pos] - '0'; 
     s2_pos--; 
    } 

    int d = d1 + d2 + carry; 
    carry = d > 9 ? 1 : 0; 

    result[pos] = '0' + (d % 10); 
    pos--; 

    if (s1_pos >= 0 || s2_pos >= 0) 
     add_helper(s1, s2, s1_pos, s2_pos, result, pos, carry); 
    else if (pos >= 0) 
     result[pos] = '0' + carry; 
} 

char *add_recurse(const char *s1, const char *s2) { 
    size_t s1_len = strlen(s1); 
    size_t s2_len = strlen(s2); 

    size_t result_len = (s1_len > s2_len ? s1_len : s2_len) + 1; 
    char *result = calloc(result_len, 1); 

    add_helper(s1, s2, s1_len-1, s2_len-1, result, result_len - 1, 0); 

    return result; 
} 


int main(int argc, char **argv) 
{ 
    char *num_str1 = "9023905350290349"; 
    char *num_str2 = "90283056923840923840239480239480234"; 


    printf("sum is %s\n", add_recurse(num_str1, num_str2)); 
} 

Обратите внимание, что нет никакой обработки вообще ошибки и я полагаю, предпосылки, что входные строки являются допустимыми строками, состоящие только из цифр, которые вы сказали, что вы уже проверили его.

ADDED ПОЛИСТНОЙ версия (для Жан-Батист Юнес, который рассматривает использование «STRLEN» мало-мальски обмане ...):

int add_helper2(const char *s1, const char *s2, int acc1, int acc2, 
       int *s1_pos, int *s2_pos, int *pos, char **result) { 

    int carry = 0; 
    int d1 = 0; 
    int d2 = 0; 

    if (s1[acc1] || s2[acc2]) { 
     int t1 = (s1[acc1] != 0); 
     int t2 = (s2[acc2] != 0); 
     carry = add_helper2(s1, s2, acc1+t1, acc2+t2, s1_pos, 
          s2_pos, pos, result); 
    } else { 
     size_t result_len = (acc1 > acc2 ? acc1 : acc2) + 1; 
     *result = calloc(result_len, 1); 
     *s1_pos = acc1 - 1; 
     *s2_pos = acc2 - 1; 
     *pos = result_len - 1; 

     return 0; 
    } 

    if (*s1_pos >= 0) { 
     d1 = s1[*s1_pos] - '0'; 
     *s1_pos -= 1; 
    } 

    if (*s2_pos >= 0) { 
     d2 = s2[*s2_pos] - '0'; 
     *s2_pos -= 1; 
    } 

    int d = d1 + d2 + carry; 
    carry = d > 9 ? 1 : 0; 

    (*result)[*pos] = '0' + (d % 10); 
    *pos -= 1; 

    return carry; 
} 


char *add_recurse2(const char *s1, const char *s2) { 
    char *result; 
    int s1_pos, s2_pos, pos; 

    int carry = add_helper2(s1, s2, 0, 0, &s1_pos, &s2_pos, &pos, &result); 
    result[0] = '0' + carry; 

    return result; 
} 

Answer 2

Поскольку Если думаете, что это домашнее задание, я только показать псевдокод ,

def str_sum(a,b): 
    index_a = len(a) 
    index_b = len(b) 
    res_len = max(len(a), len(b)) 
    result = calloc(res_len+2, 1) 
    if not result: 
     raise OutOfMemory() 
    index_a -=1 
    index_b -= 1 
    acc = 0 
    res_index = 0 
    while (index_a >=0) or (index_b >= 0): 
     chr_a = '0' 
     chr_b = '0' 
     if(index_a >=0): 
      chr_a = a[index_a] 
     if(index_b >=0): 
      chr_b = b[index_b] 
     temp = acc + ord(chr_a) - ord('0') + ord(chr_b) - ord('0') 
     result[res_index] = chr((temp % 10) + ord('0')) 
     acc = temp/10 
     index_a -=1 
     index_b -= 1 
     res_index += 1 
    inplace_rewind(result) 
    return ''.join(result) 


    print str_sum('9023905350290349', '90283056923840923840239480239480234') 

Answer 3

Вы на правильном пути. Ваш рекурсивный подход к проверке того, является ли ввод числом, выглядит примерно так: правильно? Обратите внимание, что вы можете пойти и вычесть '0' от персонажа, не утруждая себя преобразованием в 48 себя.

int number_length(char *s, int pos) { 
    int d; 
    if (s[pos] == '\0') { 
    return pos; 
    } 
    d = s[pos] - '0'; 
    if (d < 0 || d > 9) { 
    return -1; 
    } 
    return number_length(s, pos+1); 
} 

выше функция возвращает -1, если входной является недействительным, а длина номера в противном случае. Мы можем использовать длину входных чисел, когда мы начинаем процесс рекурсивного сложения.

Куда должна начинаться рекурсия? Когда мы добавляем пару чисел, удобно начинать с наименее значимых цифр.

Если мы имеем пару char * переменных a и b указывающей на номера, и если мы знаем, что a содержит a_length цифры и b содержит b_length цифры, то:

• Наименьший значащий разряд a находится на a_length-1.

• Наименее значащая цифра b находится на b_length-1.

Мы не знаем заранее, как долго результат будет, так что давайте строить цифры в int * массива, начиная с позиции 0. Это означает, что мы будем иметь результат цифры в обратном порядке , так что мы будем печатать их, начиная с конца и вернуться к 0.

ядро ​​вычислений заключается в следующем:

• Учитывая позицию a_pos в a и b_pos в b, а также цифру переноса carry, вычислите сумму цифр в a и b вместе с цифрой переноса.

• Обновить цифру переноса.

• Добавить результат в массив результатов и обновить длину массива.

В C, мы можем выразить вычисление следующим образом:

d = a[a_pos--] + b[b_pos--] - 2*'0' + carry; 
    carry = (d >= 10 ? 1 : 0); 
    result[result_pos++] = d%10; 

a[a_pos--] + b[b_pos--] Выражение становится недействительным сразу a_pos или b_pos стал отрицательным. Другими словами, мы должны иметь дело с ситуациями, когда у нас закончились цифры в одном или обоих числах. Мы должны позаботиться о:

• случаев Рукоятки, где мы уже обработаны наиболее значительную цифру a, но не b или b, но не a.

• Когда мы достигли конца как a, так и b, не забудьте проверить цифру переноса: если она равна 1, добавьте ее к результату и увеличьте длину результата.

Ниже приводится полная реализация в ANSI C.

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

#define BUFFER_SIZE 8192 

char a[BUFFER_SIZE], b[BUFFER_SIZE]; 
int result[BUFFER_SIZE]; 

int number_length(char *s, int pos) { 
    int d; 
    if (s[pos] == '\0') { 
    return pos; 
    } 
    d = s[pos] - '0'; 
    if (d < 0 || d > 9) { 
    return -1; 
    } 
    return number_length(s, pos+1); 
} 

int add(char *a, int a_pos, char *b, int b_pos, 
    int *result, int result_pos, int carry) { 
    int d; 
    if (a_pos < 0 && b_pos < 0) { 
    if (carry == 1) { 
     result[result_pos++] = 1; 
    } 
    return result_pos; 
    } 
    if (a_pos < 0) { 
    result[result_pos++] = b[b_pos--] - '0' + carry; 
    carry = 0; 
    } else if (b_pos < 0) { 
    result[result_pos++] = a[a_pos--] - '0' + carry; 
    carry = 0; 
    } else { 
    d = a[a_pos--] + b[b_pos--] - 2*'0' + carry; 
    carry = (d >= 10 ? 1 : 0); 
    result[result_pos++] = d%10; 
    } 
    return add(a, a_pos, b, b_pos, result, result_pos, carry); 
} 

int main() { 
    int a_length, b_length, i, result_length; 
    printf("First number > "); 
    scanf("%s", a); 
    if ((a_length = number_length(a, 0)) == -1) { 
    printf("%s is not a number.\n", a); 
    return 0; 
    } 
    printf("Second number > "); 
    scanf("%s", b); 
    if ((b_length = number_length(b, 0)) == -1) { 
    printf("%s is not a number.\n", b); 
    return 0; 
    } 
    result_length = add(a, a_length-1, b, b_length-1, result, 0, 0); 
    for (i = result_length-1; i >= 0; --i) { 
    printf("%d", result[i]); 
    } 
    printf("\n"); 
    return 0; 
} 

Answer 4

Сделать это в одном рекурсивном спуске не так легко, но это может сделать это:

char n1[] = "9023905350290349"; 
char n2[] = "90283056923840923840239480239480234"; 
char n3[1000]; 

char addchar(char c,char d,int r) { 
    return ((c-'0')+(d-'0')+r)%10 + '0'; 
} 
int overflow(char c,char d,int r) { 
    return ((c-'0')+(d-'0')+r)/10; 
} 

int d; 

int add(int i) { 
    if (d==0 && n1[i]!=0 && n2[i]!=0) { 
    int r= add(i+1); 
    if (d<0) { 
     n3[i+1] = addchar((i+d<0)?'0':n1[i+d],n2[i],r); 
     r = overflow((i+d<0)?'0':n1[i+d],n2[i],r); 
    } 
    if (d>0) { 
     n3[i+1] = addchar(n1[i],(i-d<0)?'0':n2[i-d],r); 
     r = overflow(n1[i],(i-d<0)?'0':n2[i-d],r); 
    } 
    if (d==0) { 
     n3[i+1] = addchar(n1[i],n2[i],r); 
     r = overflow(n1[i],n2[i],r); 
    } 
    if (i==0) { 
     n3[i] = r+'0'; 
     r = 0; 
    } 
    return r; 
    } 
    if (d>=0 && n1[i]!=0) { 
    d++; 
    int r = add(i+1); 
    n3[i+1] = addchar(n1[i],(i-d<0)?'0':n2[i-d],r); 
    return overflow(n1[i],(i-d<0)?'0':n2[i-d],r); 
    } 
    if (d<=0 && n2[i]!=0) { 
    d--; 
    int r = add(i+1); 
    n3[i+1] = addchar((i+d<0)?'0':n1[i+d],n2[i],r); 
    return overflow((i+d<0)?'0':n1[i+d],n2[i],r); 
    } 
    n3[i+1] = '\0'; 
    return 0; 
} 

int main() { 
    add(0); 
    printf("%s %s %s\n",n1,n2,n3); 
} 

Основной Идея состоит в том, чтобы вычислить максимальную длину и разницу между длинами чисел при прохождении через рекурсию, а затем добавить правильные цифры при возврате из рекурсии. Основная трудность заключается в том, чтобы управлять разницей между длинами.

Этот алгоритм добавляет начало к результату, когда нет переполнения слева.

Answer 5

Вы можете проверить ошибки в строках и сделать сумму в то же время,

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

#define MAX_RES 1000 

char *s1,*s2,*res; 

int getcharval(char *s, int i) { 
    int n = s[i] - '0'; 
    return n<0 || n>9 ? -1 : n; 
} 

char *recsum(int i1, int i2, int carry, char *pres) { 
    int n1 = !i1 ? 0 : getcharval(s1, --i1); 
    int n2 = !i2 ? 0 : getcharval(s2, --i2); 
    if (n1 < 0 || n2 < 0) return NULL; 

    int n = n1 + n2 + carry; 
    *--pres = (n % 10) + '0'; 
    return !i1 && !i2 ? pres : recsum(i1, i2, n/10, pres); 
} 

с s1 указывает на строку 1, s2 точек в строке 2, res точек в области результатов.

Рекурсивный функция recsum делает работу, принимая i1 уменьшение индекса к следующему полукокса в s1, i2 уменьшение индекса к следующему полукокса в s2, carry является результатом из предыдущего расчета и pres (р-Res) указывает на следующую result char (+1) в res.

Вспомогательная функция getcharval получает цифру из строк s индекс i и возвращает это число (от 0 до 9) или -1, если символ не является цифрой.

recsum возвращает указатель на результат, то есть указатель на res, где начинается результат.
Если в любой строке была ошибка, функция возвращает NULL.

Пример как использовать recsum, для результата, имеющего 1000 символов только (MAX_RES)

int main (int argc, char **argv) 
{ 
    s1 = "02313123"; 
    s2 = "92382472699"; 
    res = malloc(MAX_RES+1); 
    res[MAX_RES] = 0; 

    char *ret = recsum(strlen(s1), strlen(s2), 0, res+MAX_RES); 

    if (!ret) printf("There is an error\n"); 
    else printf("%s + %s = %s\n", s1, s2, ret); 

    return 0; 
}