Вернуть результат суммы символьных массивов

Question

Недавно в одном из интервью мне задали вопрос о написании функции, которая принимает в качестве входных данных два символьных массива (целых числа) и возвращает массив выходных символов.

Подпись функции:

char* find_sum(char* a, char* b)

Как можно подойти к этому?

Пример сценария:

find_sum("12345","32142") = "44487"

Примечание:

Количество цифр может быть много (1-100).

Answer 1

вы можете добавлять огромные числа, используя массив символов. однако вам нужно удалять char * после каждого его использования или использовать какой-нибудь умный указатель.

 char* find_sum(char* a, char* b) {
    int lenA = strlen(a), lenB = strlen(b);
    int max = lenA > lenB ? lenA : lenB; // Get the max for allocation
    char* res = (char*)malloc (max+2);
    memset(res, '0', max +1);      // set the result to all zeros
    res[max+1] = '\0';
    int i=lenA - 1, j = lenB - 1, k = max;
    for (; i >= 0 || j >=0; --i, --j, --k) {
            int sum = 0;
            if (i >= 0 && j>=0)
                    sum = a[i] - '0' + b[j] - '0' + res[k] - '0' ;  // add using carry
            else if (j >= 0)
                    sum =  b[j] - '0' + res[k] - '0' ;     // add the carry with remaining
            else if (i >= 0)
                    sum =  a[i] - '0' + res[k] - '0' ;
            res[k] = sum % 10 + '0';
            res[k-1] = sum / 10 + '0';
    }
    return res;
 }

 int main() {
    printf (" sum = %s ", find_sum("12345432409240242342342342234234234", "9934563424242424242423442424234"));
    return 0;
 }

Примечание: предварительным условием для функции является то, что входные массивы должны содержать только цифры.

Answer 2

Наиболее очевидный ответ заключается в том, чтобы внутренне использовать что-то вроде atoi и sprintf для преобразования чисел в целые числа, суммирования и возврата ответа как char* Однако здесь важно не что интервьюер спрашивает, но почему.

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

1. Что произойдет, если ваши входные числа не являются целыми числами?(например, 13.245, 2.3E + 7)

2. Что произойдет, если ваши «цифры» вообще не являются числами?

3. Что произойдет, есливаши входные целые действительно большие?(т. е. ~ 2 ^ 31)

4. Как вы можете обнаружить ошибку и как вы ее сообщите.

5. Как бы вы распределили памятьрезультирующая строка?

6. Что будет означать распределение памяти для вызывающего кода?

7. Какова эффективность функции и как вы могли бысделать его более эффективным?

Таким образом, интервьюер хочет исследовать ваш опыт критического подхода к решению проблем.Естественно, есть много способов решения этой проблемы.Некоторые из подходов имеют побочные эффекты, но в определенных контекстах эти побочные эффекты (например, целочисленное переполнение) могут быть не очень важны.

Кодирование часто является компромиссом между всеобъемлющим решением и тем, что можно быстро получить (и, следовательно, дешевле). Эти вопросы позволяют интервьюеру почувствовать ваше понимание качества - то есть, можете ли вы спроектировать что-то подходящее для цели, надежное, но не собирающее слишком много времени, - а также ваш опытнеобходимость выявления / устранения распространенных ошибок.

Answer 3

Вы ничего не упомянули о том, что не используете никакую внешнюю команду.

Мы можем сделать это легко на машинах, которые имеют команду bc. Вы можете добавить любое количество цифр:

$ echo "99999999999999999999999999999999+1" | bc
100000000000000000000000000000000
$ 

Мы называем это bc из программы на Си. Нам нужно построить правильную командную строку как

echo "n1+n2" | bc

и затем используйте popen, чтобы прочитать его результат. Ниже приведена функция для этого. В коде отсутствует много проверок на ошибки.

char* find_sum(char* a, char* b) {

        int l1 = strlen(a),l2 = strlen(b);
        int cmdLen = l1 + l2 + 30; // 30 to accomodate echo,bc and stuff.

        char *cmd = malloc(cmdLen);    
        snprintf(cmd,cmdLen,"echo \"%s+%s\"|bc",a,b);

        FILE *fp = popen(cmd, "r");

        int max = (l1 > l2) ? l1:l2;
        max += 2; // one for additional digit, one for null.
        char *result = malloc(max);

        fgets(result, max, fp);
        return result;
}

Рабочее звено

Answer 4

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

char* find_sum(char* a, char* b) {
    static char buf[MAX_STRING];
    ...
    return buf;
}

или

char* find_sum(char* a, char* b) {
    char *buf = malloc(MAX_STRING*sizeof(char));
    ...
    return buf;
}

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

Answer 5

Вот другой подход. Не то, что мне не нравится прототип для find_sum. Я бы очень предпочел, чтобы это было

char *find_sum(char *dst, size_t len, const char *a, const char *b);

предоставление вызывающей стороне ответственности за управление ресурсами.

a и b - строки, состоящие из 1 или более цифр (и только цифр); результат должен быть освобожден вызывающей стороной. Вызов find_sum с неверным вводом вызывает UB: -)

char *find_sum(char *a, char *b) {
  char *res;
  int alen, blen, rlen;
  int carry;

  alen = strlen(a);
  blen = strlen(b);
  rlen = 1 + ((alen > blen) ? alen : blen);
  res = malloc(1 + rlen);
  if (res) {
    int oldlen = rlen;
    res[rlen] = 0;
    carry = 0;
    while (rlen) {
      int tmp;
      if (alen && blen) tmp = a[--alen] - '0' + b[--blen] - '0';
      else if (alen) tmp = a[--alen] - '0';
      else if (blen) tmp = b[--blen] - '0';
      else tmp = 0;
      tmp += carry;
      res[--rlen] = '0' + tmp % 10;
      carry = tmp / 10;
    }
    if (res[0] == '0') memmove(res, res+1, oldlen);
  }
  return res;
}

В ideone есть рабочая версия функции (http://ideone.com/O2jrx).

Answer 6

В некоторых ответах упоминается использование функций atoi & itoa.

atoi возвращает int.Ваши числа могут не соответствовать целочисленному типу данных.

Вы можете попытаться решить проблему (хотя и не полностью), используя atol, который возвращает long int или atoll, который возвращает long long int.

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

Answer 7

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

char *sum(char *a,char *b);

int main()
{
        char a[] = "100";
        char b[] = "300";
        char *c;
        c = sum(a,b);
        printf("%s",c);
}

char *sum(char *a,char *b)
{
        int x,y,z,z2,zLen;
        char *result;
        x = atoi(a);
        y = atoi(b);
        z = x + y;
        z2 = z;
        /* Determine the length of the string now! */
        for(zLen = 1; z > 0 || z < 0; zLen++)
                z/=10;
        result = (char *)malloc(zLen*sizeof(char)+1);
        sprintf(result,"%d\0",z2);
        return result;
}

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

Интернет-версия кода

Answer 8

Просто вспомните, как вы делали сложение во втором классе на бумаге.

Answer 9

itoa(atoi(a) + atoi(b), t, 10);, если вы хотите быть ленивым, где t это char[MAX_NUMBER_OF_DIGITS].

Реальный вопрос касается выходного массива, как упоминали другие пользователи.