Вычислить сумму чисел до данного

Напишите функцию sumTo(n), которая для данного n вычисляет сумму чисел от 1 до n, например:

sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050

Сделайте три варианта решения:

С использованием цикла.
Через рекурсию, т.к. sumTo(n) = n + sumTo(n-1) для n > 1.
С использованием формулы для суммы арифметической прогрессии из алгебры.

Пример работы вашей функции:

function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050

P.S. Как соотносится скорость работы трёх вариантов решения? Почему именно так?

P.P.S. Можно ли при помощи рекурсии посчитать sumTo(100000)? Если нет, то почему?

Решение

Решение с использованием цикла:

function sumTo(n) {
  var sum = 0;
  for(var i=1; i<=n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

Решение через рекурсию:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n-1);
}

alert( sumTo(100) );

Решение по формуле: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n*(n+1)/2;
}

alert( sumTo(100) );

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

Вариант с циклом — второй по скорости. Он быстрее рекурсии, так как операции по сути те же, но нет накладных расходов на вложенный вызов функции.

Рекурсия в данном случае работает медленнее всех.

P.P.S. Существует ограничение глубины вложенных вызовов, поэтому рекурсивный вызов sumTo(100000) выдаст ошибку.

#362

Вычислить сумму чисел до данного

Реклама

Нашли опечатку?

Последние Комментарии

Помоги другим!