Написание функции, которая вычисляет сумму квадратов в диапазоне в одной строке в C

Question

Моя попытка

double sum_squares_from(double x, double n){

    return n<=0 ? 0 : x*x + sum_squares_from((x+n-1)*(x+n-1),n-1);

}

Вместо того, чтобы использовать циклы, мой профессор хочет, чтобы мы писали такие функции, как это ... То, что просит упражнение, - это функция sum_squares_from () с двойным x как начальным числом и nэто номер числа. Например, если вы делаете x = 2 и n = 4, вы получаете 2 * 2 + 3 * 3 + 4 * 4 + 5 * 5. Он возвращает ноль, если n == 0.

Я думал, что в моем примере я имею в основном x * x + (x + 1) (x + 1) + (x + 1 + 1) (x+ 1 + 1) + (x + 1 + 1 + 1) (x + 1 + 1 + 1) = (x + 0) (x + 0) + (x + 1) (x + 1) + (x +2) (x + 2) + (x + 3) (x + 3) = (x + n-1) ^ 2 повторяется n раз, где n уменьшается каждый раз на единицу, пока не станет равным нулю, а затем вы суммируете все.

Правильно ли я это сделал?

(если мой профессор кажется немного требовательным ... он каким-то образом все это делает в голове без вспомогательных вычислений. Страшный парень)

Answer 1

Это не рекурсивно, но это одна строка:

int 
sum_squares(int x, int n) {
  return ((x + n - 1) * (x + n) * (2 * (x + n - 1) + 1) / 6) - ((x - 1) * x * (2 * (x - 1) + 1) / 6);
}

Сумма квадратов (целых чисел) имеет закрытое решение для 1 .. n. Этот код вычисляет сумму квадратов из 1 .. (x+n), а затем вычитает сумму квадратов из 1 .. (x-1).

Answer 2

^{В оригинальной версии этого ответа использован ASCII art.}

Итак,

• ∑ _{i: 0..n} i = n (n + 1) (½)
• ∑ _{i: 0..n} i ² =n (n + 1) (2n + 1) (⅙)

Отметим, что

• ∑ _{i: 0..n} (x + i) ²
  = ∑ _{i: 0 ... n} x ² + 2xi + i ²
  = (n + 1) x ² + (2x) ∑ _{i: 0..n} i + ∑ _{i: 0..n} i ²
  = (n + 1) x ² + n (n + 1) x + n (n + 1) (2n + 1) (⅙)

Таким образом, ваша сумма имеет закрытую форму:

double sum_squares_from(double x, int n) {
    return ((n-- > 0)
            ? (n + 1) * x * x
              + x * n * (n + 1)
              + n * (n + 1) * (2 * n + 1) / 6.
            : 0);
}

Если я применю некоторую запутанность, однострочная версия станет:

double sum_squares_from(double x, int n) {
    return (n-->0)?(n+1)*(x*x+x*n+n*(2*n+1)/6.):0;
}

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

static double sum_squares_from_loop(double x, int n, double s) {
    return (n <= 0) ? s : sum_squares_from_loop(x+1, n-1, s+x*x);
}

double sum_squares_from(double x, int n) {
    return sum_squares_from_loop(x, n, 0);
}

В качестве иллюстрации, если вы наблюдаете сгенерированную сборку в GCC на достаточном уровне оптимизации (-Os, -O2 или -O3), вы заметите, что рекурсивный вызов исключен (и sum_squares_from_loop не загружается).

Попробуйте онлайн!

Answer 3

Как упоминалось в моем исходном комментарии, n не должно быть типа double, а вместо этого должно быть типа int, чтобы избежать проблем сравнения с плавающей запятой с n <= 0. Внося изменения и упрощая умножение и рекурсивный вызов, вы делаете:

double sum_squares_from(double x, int n)
{
    return n <= 0 ? 0 : x * x + sum_squares_from (x + 1, n - 1);
}

Если вы думаете о том, чтобы начать с x * x и увеличить x в 1, n раз, тогда простоx * x + sum_squares_from (x + 1, n - 1) довольно легко понять.

Answer 4

Может быть, это?

double sum_squares_from(double x, double n) {
    return n <= 0 ? 0 : (x + n - 1) * (x + n - 1) + sum_squares_from(x, n - 1);
}