3

Встретился такой код:

function res(a, b, t, c){
  if(a.length == 0 && b.length == 0 && !c)
    return t;
  var l = parseInt(a.pop() || '0') + parseInt(b.pop() || '0') + (c || 0);
  return res(a, b, l + (t || ""), l > 9? 1:0);
}

function add(a, b) {
  return res(a.toString().split(""), b.toString().split(""), "").toString();
}

Судя по всему, код реализует сложение «длинных» целых (функция res() – вспомогательная). Но, похоже, делает это с ошибками. Например, для add(5,5) результат 110, вместо ожидаемого 10, хотя для add(2,3) получается правильный: 5.

Я не могу понять, как этот код работает, и где может быть ошибка. Объясните, пожалуйста, доступно.

16
  • А что этот код, хотя бы делает? Или мы должны это угадать? 28 ноя 2015 в 12:25
  • 1
    похоже - складывает числа :-)
    – Grundy
    28 ноя 2015 в 12:28
  • 1
    @VladD, да в принципе и так понятно: даешь массивы из цифр, и рекурсивно складываешь по разрядам
    – Grundy
    28 ноя 2015 в 12:32
  • 1
    @Grundy, 5+5=110?
    – Ni55aN
    28 ноя 2015 в 13:12
  • 2
    Хороший же вопрос – разбор чужого кода, исправление косяков – так и учатся. Голосуйте скорее за переоткрытие! : )
    – Sergiks
    28 ноя 2015 в 17:54

1 ответ 1

11

Здесь происходит поразрядное сложение. Таким способом можно складывать как угодно большие числа, не только ограниченные максимально допустимым значением, для js это 1.79E+308, поэтому это называется длинной арифметикой. Поскольку обыкновенные числа ограничены, результат выдаётся в виде строки.

Для начала рассмотрим функцию add

function add(a, b) {
  return res(a.toString().split(""), b.toString().split(""), "").toString();
}

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

В ней происходит вот что. Сначала, если a не было строкой, оно превращается в строку. Затем при помощи функции split разбивается на массив из отдельных цифр. То же происходит со вторым слагаемым — b. Затем вызывается функция res, которая и будет вычислять наш ответ. Поскольку число может быть как угодно длинное, то ответ мы будем собирать по одной цифре, в виде строки. Начальное значение строки-ответа "", на каждом рекурсивном вызове res мы будем вычислять по одной цифре.

Дальше вызывается функция res с начальными параметрами, запускает рекурсию.

Теперь по функции res: данная функция как раз и производит сложение. Практически обыкновенное, привычное школьное сложение в столбик.

сложение по разрядам

Если немного переименовать параметры:

function res(a, b, result, carry) {

У нас слагаемые a и b, промежуточный результат в result, перенос из предыдущего разряда в carry.

Если и левое, и правое слагаемое пустое, и нет переноса, то результат готов, его и возвращаем.

  if(a.length == 0 && b.length == 0 && !carry)
    return result;

Вынесем сложные выражения в локальную переменную для простоты. Мы собираемся получить младшую цифру каждого из слагаемых, и убрать эту цифру из дальнейшего рассмотрения. Для этого мы пользуемся функцией pop, которая убирает последний элемент массива, отдаёт нам его.

  var left = parseInt(a.pop() || '0', 10);
  var right = parseInt(b.pop() || '0',10);

То есть, для массива ['9', '8', '7'] функция pop() вернёт '7', а от массива останется лишь ['9', '8'].

Если массив на самом деле был пустой, функция вернёт undefined. Тут-то нам и пригодится трюк с || '0': если результат был цифрой, она при этом не испортится, а вот undefined превратится в '0'!

Полученную цифру-строку мы превратили в число при помощи parseInt.

Дальше мы складываем левую и правую цифры, и не забываем добавить перенос:

  var l = left + right + (carry || 0);

Если перенос не указан, при помощи того же трюка превращаем его в 0.

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

  return res(a, b, l + (result || ""), l > 9? 1:0);
}

Но, как правильно заметил @Ni55aN, данная функция не всегда корректно работает.

Нужно немного изменить ее.

  1. Добавить основание, например 10. Дело в том, что мы складываем по одной цифре. Но мы можем, по идее, и складывать большими кусками. Это была бы оптимизация.
  2. Затем, у нас баг: мы к результату добавляем часть, не «откусив» от неё перенесённый старший разряд. Это неправильно, надо убирать лишнее.
  3. Для случая двух слагаемых перенос не больше 1, но если мы захотим обобщить код на случай большего числа слагаемых, точное значение нужно будет вычислять.

Напишем точное вычисление «на вырост».

function res(a, b, result, carry, base) {
  if(a.length == 0 && b.length == 0 && !carry)
    return result;

  //берем младшие разряды
  var left = parseInt(a.pop() || '0', 10);
  var right = parseInt(b.pop() || '0', 10);

  //складываем и добавляем перебор с прошлой итерации
  var l = left + right + (carry || 0);

  //вызываем для следующих разрядов, правильно вычисляя добавленную цифру и цифру переноса
  return res(a, b, l % base + (result || ""), Math.floor(l/base), base);
}

function add(a, b) {
  return res(a.toString().split(""), b.toString().split(""), "","",10).toString();
}

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

Пример:

$(function() {
  
  $('#left,#right').change(function(){
    var left = $('#left').val().trim();
    var right = $('#right').val().trim();
    console.log(left,right,isNaN(left),isNaN(right));
    if(isNaN(left) || isNaN(right)) return;
    
    $('#sum').html(add(left,right));
    
  });
  
  function res(a, b, result, carry, base) {
    if (a.length == 0 && b.length == 0 && !carry)
      return result;

    //берем младшие разряды
    var left = parseInt(a.pop() || '0', 10);
    var right = parseInt(b.pop() || '0', 10);

    //складываем и добавляем перебор с прошлой итерации
    var l = left + right + (carry || 0);

    //вызываем для следующих разрядов
    return res(a, b, l % base + (result || ""), Math.floor(l / base), base);
  }

  function add(a, b) {
    return res(a.toString().split(""), b.toString().split(""), "", "", 10).toString();
  }
});
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
left:
<input type="text" id="left" />
<br/>right:
<input type="text" id="right" />
<br/>sum: <span id="sum"></span>

8
  • Длинная потому, что по идее код может складывать числа любой разрядности. Для небольших чисел можно просто parseInt и сложить.
    – VladD
    28 ноя 2015 в 19:23
  • @VladD, там основание по умолчанию было зашито 10, так что не особо и длинная :-)
    – Grundy
    28 ноя 2015 в 19:26
  • Переименовал c в carry
    – VladD
    28 ноя 2015 в 19:26
  • @VladD, а я не смог придумать как обозвать перебор который переносится :-)
    – Grundy
    28 ноя 2015 в 19:26
  • Ну, по идее, код может сложить "9999999999999999999999999999999999999999999" с "1". Обычная арифметика такого не сумеет.
    – VladD
    28 ноя 2015 в 19:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.