Cálculo de una raíz anidada en C

9

Me pidieron que calcule la siguiente expresión de raíz anidada usando solo recursión .

ingrese la descripción de la imagen aquí

Escribí el siguiente código que funciona, pero nos permitieron usar solo una función y 1 entrada npara el propósito y no 2 como usé. ¿Alguien puede ayudarme a transformar este código en una función que calcule la expresión? No puedo usar ninguna biblioteca excepto las funciones de <math.h>.

salida para 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);
}
Ronen Dvorkin
fuente
¿Alguien puede ayudarme a transformar este código en una función que calcule la expresión? ¿Qué? Ayuda a deshacerse de la helper?
4386427
Si los argumentos son incorrectos, llamaría abort()(desde <stdlib.h>), no devolvería silenciosamente 0.
Kaz
1
@chqrlieforyellowblockquotes Twisied. @pastaleg ¿Qué tal una recursión inútil? 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 - Restablece a Mónica el
1
@ chux-ReinstateMonica: sí, un abuso más simple de las reglas.
chqrlie
2
@Open: si el objetivo de la tarea fuera financiar una expresión no recursiva de la función, probablemente no solicitaría que el problema se resuelva utilizando "solo recursividad". Ciertamente, un bucle simple calcularía el resultado fácilmente. Aunque generalmente sospecho cuando estas preguntas se publican en Stack Overflow sin el texto real de la tarea.
Eric Postpischil

Respuestas:

7

Use los bits superiores de ncomo contador:

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;
}

Naturalmente, eso funciona mal cuando la inicial nes Ro mayor. Aquí hay una versión más complicada que funciona para cualquier valor positivo de n. Funciona:

  • Cuando nes negativo, funciona como la versión anterior, utilizando los bits superiores para contar.
  • Cuando nes positivo, si es menor que R, se llama a sí mismo -npara evaluar la función como se indicó anteriormente. De lo contrario, se llama a sí mismo con R-1negado. Esto evalúa la función como si se llamara con R-1. Esto produce el resultado correcto porque la serie deja de cambiar en el formato de punto flotante después de unas pocas docenas de iteraciones: las raíces cuadradas de los números más profundos se diluyen tanto que no tienen ningún efecto. Por lo tanto, la función tiene el mismo valor para todos nen un umbral pequeño.
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;
}
Eric Postpischil
fuente
Buena idea, pero supone
entradas de
1
@chqrlieforyellowblockquotes: No, es por eso que Restá separado, por lo que se puede ajustar. Antes de nllegar a 32, el valor de retorno deja de cambiar para IEEE-754 binary64, y antes de llegar a 256, el valor de retorno deja de cambiar para formatos razonables para double. Así que estoy considerando una versión alternativa que transforma las entradas de las abrazaderas anteriores R, pero necesita usar el bit de signo, y todavía estoy trabajando en ello.
Eric Postpischil
Hay otras funciones de emparejamiento que puede usar, pero ninguna tan simple como la suya. Su principal ventaja suele ser que trabajan con precisión arbitraria, pero OP nunca mencionó eso como un requisito.
Ruud Helderman
@chqrlieforyellowblockquotes: Hecho. Ahora produce la respuesta correcta para cualquier positivo, nindependientemente del ancho de int.
Eric Postpischil
5

Sin transformar matemáticamente la fórmula (no sé si es posible), no puede usar realmente un solo parámetro, ya que para cada elemento necesita dos informaciones: el paso actual y el original n. Sin embargo, puedes hacer trampa . Una forma es codificar los dos números en el intparámetro (como lo muestra Eric ).

Otra forma es almacenar el original nen una variable local estática. En la primera llamada que guardamos nen esta variable estática, comenzamos la recursión y en el último paso la restablecemos al valor centinela:

// 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));
}

Aparentemente static int n = sentinelno es C estándar porque sentinelno es una constante de tiempo de compilación en C (es extraño porque tanto gcc como clang no se quejan, incluso con -pedantic)

Puedes hacer esto en su lugar:

enum Special { Sentinel = -1 };
static int n = Sentinel;
bolov
fuente
Enfoque interesante, pero me temo que el inicializador static int n = sentinel;no es totalmente conforme en C porque sentinelno es una expresión constante según el Estándar C. Funciona en C ++, y se compila con las versiones actuales de gcc y clang en modo C, pero no en MSVC 2017, pero probablemente debería escribir static int n = -1;vea godbolt.org/z/8pEMnz
chqrlie
1
@chqrlieforyellowblockquotes ish. Gracias por señalar esto. Comportamiento interesante del compilador. He preguntado sobre esto en esta pregunta: stackoverflow.com/q/61037093/2805305
bolov
5

Este problema pide soluciones retorcidas.

Aquí hay uno que usa una sola función tomando uno o dos intargumentos:

  • si el primer argumento es positivo, calcula la expresión para ese valor
  • Si el primer argumento es negativo, debe ser seguido por un segundo argumento y realiza un solo paso en el cálculo, recurriendo al paso anterior.
  • utiliza lo <stdarg.h>que podría o no estar permitido.

Aquí está el código:

#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);
    }
}

Aquí hay otra solución con una sola función, usando solo <math.h>, pero abusando de las reglas de una manera diferente: usando una macro.

#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));
    }
}

Otro más, estrictamente hablando recursivo , pero con un solo nivel de recursión y sin otros trucos. Como Eric comentó, usa un forbucle que podría ser inválido bajo las restricciones del 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
fuente
Sí, eso funciona, supongo. muchas gracias por toda la ayuda
Ronen Dvorkin
Por último double rec_sqrt_series(int n), IMO cumple con los objetivos de OP utilizando el signo como una bandera de recursión. ( elsereturnif
Dejaría lo
1
@ chux-ReinstateMonica: elsedescartar es posible, por supuesto, pero me gusta un poco la simetría de ambas ramas de la ifdevolución de un resultado, una especie de estilo de programación funcional.
chqrlie
@ chux-ReinstateMonica: espero que el requisito de la asignación de "solo recursión" excluya la iteración.
Eric Postpischil
@EricPostpischil: sí, pensé lo mismo, pero no recibí comentarios del OP.
chqrlie
0

Aquí hay otro enfoque.

Se basa en intser de 32 bits. La idea es utilizar los 32 bits superiores de 64 bits intpara

1) Vea si la llamada fue recursiva (o una llamada desde el "exterior")

2) Guarde el valor objetivo en los 32 bits superiores durante la recursividad

// 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
fuente