Меня попросили вычислить следующее вложенное корневое выражение, используя только рекурсию .
Я написал код ниже, который работает, но они позволили нам использовать только одну функцию и 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
?abort()
(из<stdlib.h>
), а не молча вернуть 0.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; }
Ответы:
Используйте старшие биты
n
в качестве счетчика:Естественно, что неисправности , когда начальная
n
являетсяR
или больше. Вот более сложная версия, которая работает для любого положительного значенияn
. Оно работает:n
оно отрицательное, оно работает как вышеприведенная версия, используя верхние биты для подсчета.n
положительный, если он меньшеR
, он вызывает себя-n
для оценки функции, как указано выше. В противном случае он вызывает себя сR-1
отрицанием. Это оценивает функцию, как если бы она была вызвана сR-1
. Это дает правильный результат, потому что ряд перестает изменяться в формате с плавающей запятой после нескольких десятков итераций - квадратные корни более глубоких чисел настолько разбавляются, что не имеют никакого эффекта. Таким образом, функция имеет одинаковое значение для всегоn
небольшого порога.источник
R
он отдельный, поэтому его можно настроить. Доn
достижения 32 возвращаемое значение перестает изменяться для двоичного IEEE-754, а до достижения 256 возвращаемое значение перестает изменяться для приемлемых форматовdouble
. Поэтому я рассматриваю альтернативную версию, которая преобразует входные данные зажимов вышеR
, но для этого нужно использовать знаковый бит, и я все еще работаю над этим.n
независимо от шириныint
.Без математического преобразования формулы (я не знаю, возможно ли это), вы не сможете по-настоящему использовать только один параметр, так как для каждого элемента вам нужны две информации: текущий шаг и оригинал
n
. Однако вы можете обмануть . Одним из способов является кодирование двух чисел вint
параметре (как показано Эриком ).Другой способ - сохранить оригинал
n
в статической локальной переменной. При первом вызове, который мы сохраняемn
в этой статической переменной, мы запускаем рекурсию и на последнем шаге сбрасываем ее в значение Sentinel:Очевидно,
static int n = sentinel
это не стандартный C, потому чтоsentinel
не является постоянной времени компиляции в C (это странно, потому что и gcc, и clang не жалуются, даже с-pedantic
)Вы можете сделать это вместо этого:
источник
static int n = sentinel;
не полностью соответствует C, потому чтоsentinel
не является константным выражением согласно стандарту C. Он работает на C ++ и компилируется с текущими версиями gcc и clang в режиме C, но не MSVC 2017, но вам, вероятно, следует написатьstatic int n = -1;
см. Godbolt.org/z/8pEMnzЭта проблема требует искаженных решений.
Вот тот, который использует одну функцию, принимающую один или два
int
аргумента:<stdarg.h>
что может или не может быть разрешено.Вот код:
Вот еще одно решение с одной функцией, использующее только
<math.h>
, но нарушающее правила другим способом: использование макроса.Еще один, строго говоря, рекурсивный , но с одним уровнем рекурсии и без других уловок. Как прокомментировал Эрик , он использует
for
цикл, который может быть недопустимым при ограничениях OP:источник
double rec_sqrt_series(int n)
, IMO, отвечает целям OP, используя знак в качестве флага рекурсии. (Я бы бросил,else
как не нужно, какreturn
естьif
.)else
конечно, отбрасывание возможно, но мне нравится симметрия обеих ветвей,if
возвращающих результат, своего рода стиль функционального программирования.Вот другой подход.
Это полагается на то,
int
чтобы быть 32 битами. Идея состоит в том, чтобы использовать верхний 32-разрядный 64-разрядныйint
для1) Проверьте, был ли вызов рекурсивным (или вызовом извне)
2) Сохранить целевое значение в старших 32 битах во время рекурсии
источник