Berechnung einer verschachtelten Wurzel in C.

Ich wurde gebeten, den folgenden verschachtelten Root-Ausdruck nur mit Rekursion zu berechnen .

Ich habe den folgenden Code geschrieben, der funktioniert, aber sie erlaubten uns, nur eine Funktion und einen Eingang nfür diesen Zweck zu verwenden und nicht zwei, wie ich sie verwendet habe. Kann mir jemand helfen, diesen Code in eine Funktion umzuwandeln, die den Ausdruck berechnet? Ich kann keine Bibliothek außer Funktionen von verwenden <math.h>.

Ausgabe für 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);
}

Verwenden Sie die oberen Bits von nals Zähler:

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

Natürlich , dass Störungen , wenn die Anfangs nist Roder größer ist . Hier ist eine kompliziertere Version, die für jeden positiven Wert von funktioniert n. Es klappt:

• Wenn nes negativ ist, funktioniert es wie in der obigen Version, wobei die oberen Bits zum Zählen verwendet werden.
• Wenn npositiv ist, wenn es kleiner als ist R, ruft es sich selbst -nauf, um die Funktion wie oben zu bewerten. Ansonsten ruft es sich mit R-1negiert auf. Dies wertet die Funktion so aus, als ob sie mit aufgerufen worden wäre R-1. Dies führt zu dem richtigen Ergebnis, da sich die Reihe nach nur wenigen Dutzend Iterationen nicht mehr im Gleitkommaformat ändert - die Quadratwurzeln der tieferen Zahlen werden so verdünnt, dass sie keine Wirkung haben. Die Funktion hat also nüber einen kleinen Schwellenwert hinweg den gleichen Wert .

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

Ohne die Formel mathematisch zu transformieren (ich weiß nicht, ob es möglich ist), können Sie nicht wirklich nur einen Parameter verwenden, da Sie für jedes Element zwei Informationen benötigen: den aktuellen Schritt und das Original n. Sie können jedoch betrügen . Eine Möglichkeit besteht darin, die beiden Zahlen im intParameter zu codieren (wie von Eric gezeigt ).

Eine andere Möglichkeit besteht darin, das Original nin einer statischen lokalen Variablen zu speichern . Beim ersten Aufruf, den wir nin dieser statischen Variablen speichern , starten wir die Rekursion und setzen sie im letzten Schritt auf den Sentinel-Wert zurück:

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

Anscheinend static int n = sentinelist nicht Standard C, weil sentineles keine Kompilierungszeitkonstante in C ist (es ist seltsam, weil sowohl gcc als auch clang sich nicht beschweren, auch nicht mit -pedantic)

Sie können dies stattdessen tun:

enum Special { Sentinel = -1 };
static int n = Sentinel;

Dieses Problem erfordert verzerrte Lösungen.

Hier ist eine, die eine einzelne Funktion verwendet, die ein oder zwei intArgumente akzeptiert:

• Wenn das erste Argument positiv ist, berechnet es den Ausdruck für diesen Wert
• Wenn das erste Argument negativ ist, muss ein zweites Argument folgen und einen einzelnen Schritt in der Berechnung ausführen, wobei der vorherige Schritt wiederholt wird.
• es verwendet, <stdarg.h>was möglicherweise erlaubt ist oder nicht.

Hier ist der Code:

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

Hier ist eine andere Lösung mit einer einzigen Funktion, die nur <math.h>die Regeln verwendet , aber auf andere Weise missbraucht: mithilfe eines Makros.

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

Noch eine, streng genommen rekursiv , aber mit einer einzigen Rekursionsstufe und ohne andere Tricks. Wie Eric kommentierte, wird eine forSchleife verwendet, die unter den Einschränkungen des OP ungültig sein kann:

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

Hier ist ein anderer Ansatz.

Es basiert auf int32 Bit. Die Idee ist, die oberen 32 Bit eines 64 Bit intzu verwenden

1) Überprüfen Sie, ob der Anruf ein rekursiver Anruf war (oder ein Anruf von "außen").

2) Speichern Sie den Zielwert während der Rekursion in den oberen 32 Bits

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