Вычисление вложенного корня в C

9

Меня попросили вычислить следующее вложенное корневое выражение, используя только рекурсию .

введите описание изображения здесь

Я написал код ниже, который работает, но они позволили нам использовать только одну функцию и 1 вход nдля цели, а не 2, как я использовал. Может кто-нибудь помочь мне преобразовать этот код в одну функцию, которая будет вычислять выражение? Нельзя использовать любую библиотеку, кроме функций из <math.h>.

выход для n = 10: 1.757932

double rec_sqrt_series(int n, int m) {
    if (n <= 0)
        return 0;
    if (m > n)
        return 0;
    return sqrt(m + rec_sqrt_series(n, m + 1));
}

double helper(int n) {
    return rec_sqrt_series(n, 1);
}
Ронен Дворкин
источник
Может кто-нибудь помочь мне преобразовать этот код в одну функцию, которая будет вычислять выражение? что? Помочь вам избавиться от helper?
4386427
Если аргументы неверны, я бы позвонил abort()(из <stdlib.h>), а не молча вернуть 0.
Каз
1
@chqrlieforyellowblockquotes Twisied. @pastaleg Как насчет бесполезной рекурсии? double nested_root(unsigned n) { double x = 0.0; if (n > 0) { x = nested_root(0); for (unsigned i = n; i > 0; i--) { x = sqrt(i + x); } } return x; }
chux - Восстановить Монику
1
@ chux-ReinstateMonica: да, простое нарушение правил.
chqrlie
2
@Oppen: если бы целью задания было финансирование нерекурсивного выражения функции, то, вероятно, не потребовалось бы решить проблему с помощью «только рекурсии». Конечно, простой цикл легко вычислит результат. Хотя я обычно сомневаюсь, когда эти вопросы публикуются в Stack Overflow без фактического текста задания.
Эрик Постпишил

Ответы:

7

Используйте старшие биты nв качестве счетчика:

double rec_sqrt_series(int n)
{
    static const int R = 0x10000;
    return n/R < n%R ? sqrt(n/R+1 + rec_sqrt_series(n+R)) : 0;
}

Естественно, что неисправности , когда начальная nявляется Rили больше. Вот более сложная версия, которая работает для любого положительного значения n. Оно работает:

  • Когда nоно отрицательное, оно работает как вышеприведенная версия, используя верхние биты для подсчета.
  • Когда nположительный, если он меньше R, он вызывает себя -nдля оценки функции, как указано выше. В противном случае он вызывает себя с R-1отрицанием. Это оценивает функцию, как если бы она была вызвана с R-1. Это дает правильный результат, потому что ряд перестает изменяться в формате с плавающей запятой после нескольких десятков итераций - квадратные корни более глубоких чисел настолько разбавляются, что не имеют никакого эффекта. Таким образом, функция имеет одинаковое значение для всего nнебольшого порога.
double rec_sqrt_series(int n)
{
    static const int R = 0x100;
    return
        0 < n ? n < R ? rec_sqrt_series(-n) : rec_sqrt_series(1-R)
              : n/R > n%R ? sqrt(-n/R+1 + rec_sqrt_series(n-R)) : 0;
}
Эрик Постпищил
источник
Хорошая идея, но предполагает 32-битные целые числа :)
chqrlie
1
@chqrlieforyellowblockquotes: Нет, именно поэтому Rон отдельный, поэтому его можно настроить. До nдостижения 32 возвращаемое значение перестает изменяться для двоичного IEEE-754, а до достижения 256 возвращаемое значение перестает изменяться для приемлемых форматов double. Поэтому я рассматриваю альтернативную версию, которая преобразует входные данные зажимов выше R, но для этого нужно использовать знаковый бит, и я все еще работаю над этим.
Эрик Постпишил
Есть и другие функции сопряжения, которые вы можете использовать, но не такие простые, как у вас. Их главным преимуществом обычно является то, что они работают с произвольной точностью, но OP никогда не упоминал об этом как о требовании.
Рууд Хелдерман
@chqrlieforyellowblockquotes: Готово. Теперь выдает правильный ответ на любой положительный результат nнезависимо от ширины int.
Эрик Постпишил
5

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

Другой способ - сохранить оригинал nв статической локальной переменной. При первом вызове, который мы сохраняем nв этой статической переменной, мы запускаем рекурсию и на последнем шаге сбрасываем ее в значение Sentinel:

// fn(i) = sqrt(n + 1 - i + fn(i - 1))
// fn(1) = sqrt(n)
//
// note: has global state
double f(int i)
{
    static const int sentinel = -1;
    static int n = sentinel;

    // outside call
    if (n == sentinel)
    {
        n = i;
        return f(n);
    }

    // last step
    if (i == 1)
    {
        double r = sqrt(n);
        n = sentinel;
        return r;
    }

    return sqrt(n + 1 - i + f(i - 1));
}

Очевидно, static int n = sentinelэто не стандартный C, потому что sentinelне является постоянной времени компиляции в C (это странно, потому что и gcc, и clang не жалуются, даже с -pedantic)

Вы можете сделать это вместо этого:

enum Special { Sentinel = -1 };
static int n = Sentinel;
Болов
источник
Интересный подход, но я боюсь, что инициализатор static int n = sentinel;не полностью соответствует C, потому что sentinelне является константным выражением согласно стандарту C. Он работает на C ++ и компилируется с текущими версиями gcc и clang в режиме C, но не MSVC 2017, но вам, вероятно, следует написать static int n = -1;см. Godbolt.org/z/8pEMnz
chqrlie
1
@chqrlieforyellowblockquotes ish. Спасибо за указание на это. Интересное поведение компилятора. Я спрашивал об этом в этом вопросе: stackoverflow.com/q/61037093/2805305
bolov
5

Эта проблема требует искаженных решений.

Вот тот, который использует одну функцию, принимающую один или два intаргумента:

  • если первый аргумент положительный, он вычисляет выражение для этого значения
  • если первый аргумент отрицателен, он должен сопровождаться вторым аргументом и выполняет один шаг в вычислении, повторяющийся для предыдущего шага.
  • он использует то, <stdarg.h>что может или не может быть разрешено.

Вот код:

#include <math.h>
#include <stdarg.h>

double rec_sqrt_series(int n, ...) {
    if (n < 0) {
        va_arg ap;
        va_start(ap, n);
        int m = va_arg(ap, int);
        va_end(ap);
        if (m > -n) {
            return 0.0;
        } else {
            return sqrt(m + rec_sqrt_series(n, m + 1));
        }
    } else {
        return rec_sqrt_series(-n, 1);
    }
}

Вот еще одно решение с одной функцией, использующее только <math.h>, но нарушающее правила другим способом: использование макроса.

#include <math.h>

#define rec_sqrt_series(n)  (rec_sqrt_series)(n, 1)
double (rec_sqrt_series)(int n, int m) {
    if (m > n) {
        return 0.0;
    } else {
        return sqrt(m + (rec_sqrt_series)(n, m + 1));
    }
}

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

double rec_sqrt_series(int n) {
    if (n > 0) {
        return rec_sqrt_series(-n);
    } else {
        double x = 0.0;
        for (int i = -n; i > 0; i--) {
            x = sqrt(i + x);
        }
        return x;
    }
}
chqrlie
источник
да, это работает, я думаю. большое спасибо за помощь
Ронен Дворкин
И последнее double rec_sqrt_series(int n), IMO, отвечает целям OP, используя знак в качестве флага рекурсии. (Я бы бросил, elseкак не нужно, как returnесть if.)
Chux - Восстановить Монику
1
@ chux-ReinstateMonica: elseконечно, отбрасывание возможно, но мне нравится симметрия обеих ветвей, ifвозвращающих результат, своего рода стиль функционального программирования.
chqrlie
@ chux-ReinstateMonica: я ожидаю, что требование назначения «только рекурсия» исключает итерацию.
Эрик Постпишил
@EricPostpischil: да, я тоже так думал, но не получил отклика от ОП.
chqrlie
0

Вот другой подход.

Это полагается на то, intчтобы быть 32 битами. Идея состоит в том, чтобы использовать верхний 32-разрядный 64-разрядный intдля

1) Проверьте, был ли вызов рекурсивным (или вызовом извне)

2) Сохранить целевое значение в старших 32 битах во время рекурсии

// Calling convention:
// when calling this function 'n' must be a positive 32 bit integer value
// If 'n' is zero or less than zero the function have undefined behavior
double rec_sqrt_series(uint64_t n)
{
  if ((n >> 32) == 0)
  {
    // Not called by a recursive call
    // so start the recursion
    return rec_sqrt_series((n << 32) + 1);
  }

  // Called by a recursive call

  uint64_t rn = n & 0xffffffffU;

  if (rn == (n >> 32)) return sqrt(rn);      // Done - target reached

  return sqrt (rn + rec_sqrt_series(n+1));   // Do the recursive call
}
4386427
источник