Berechnung einer verschachtelten Wurzel in C.

9

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

Geben Sie hier die Bildbeschreibung ein

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);
}
Ronen Dvorkin
quelle
Kann mir jemand helfen, diesen Code in eine Funktion umzuwandeln, die den Ausdruck berechnet? Was? Helfen Sie, die loszuwerden helper?
4386427
Wenn die Argumente falsch sind, würde ich abort()(von <stdlib.h>) anrufen und nicht still 0 zurückgeben.
Kaz
1
@chqrlieforyellowblockquotes Twisied. @pastaleg Wie wäre es mit nutzloser Rekursion? 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 - Monica
1
@ chux-ReinstateMonica: Ja, ein einfacherer Missbrauch der Regeln.
Chqrlie
2
@Oppen: Wenn das Ziel der Zuweisung darin besteht, einen nicht rekursiven Ausdruck der Funktion zu finanzieren, wird wahrscheinlich nicht verlangt, dass das Problem mit "nur Rekursion" gelöst wird. Sicherlich würde eine einfache Schleife das Ergebnis leicht berechnen. Obwohl ich im Allgemeinen misstrauisch bin, wenn diese Fragen ohne den eigentlichen Text der Aufgabe an Stack Overflow gesendet werden.
Eric Postpischil

Antworten:

7

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;
}
Eric Postpischil
quelle
Gute Idee, geht aber von 32-Bit-Ints aus :)
chqrlie
1
@chqrlieforyellowblockquotes: Nein, deshalb Rist es separat, damit es abgestimmt werden kann. Bevor n32 erreicht wird, ändert sich der Rückgabewert für IEEE-754 binary64 nicht mehr, und bevor er 256 erreicht, ändert sich der Rückgabewert für vernünftige Formate für nicht mehr double. Ich denke also über eine alternative Version nach, die die oben genannten Klemmeingänge transformiert R, aber das Vorzeichenbit verwenden muss, und ich arbeite noch daran.
Eric Postpischil
Es gibt andere Pairing-Funktionen, die Sie verwenden können, aber keine so einfach wie Ihre. Ihr Hauptvorteil ist normalerweise, dass sie mit willkürlicher Präzision arbeiten, aber OP hat dies nie als Voraussetzung erwähnt.
Ruud Helderman
@chqrlieforyellowblockquotes: Fertig. Erzeugt nun die richtige Antwort für jedes Positiv, nunabhängig von der Breite von int.
Eric Postpischil
5

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;
Bolov
quelle
Interessanter Ansatz, aber ich fürchte, der Initialisierer static int n = sentinel;ist in C nicht vollständig konform, da er sentinelkein konstanter Ausdruck gemäß C-Standard ist. Es funktioniert in C ++ und kompiliert mit aktuellen Versionen von gcc und clang im C-Modus, jedoch nicht mit MSVC 2017, aber Sie sollten wahrscheinlich schreiben, static int n = -1;siehe godbolt.org/z/8pEMnz
chqrlie
1
@chqrlieforyellowblockquotes ish. Vielen Dank für den Hinweis. Interessantes Compilerverhalten. Ich habe dies in dieser Frage gefragt: stackoverflow.com/q/61037093/2805305
bolov
5

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;
    }
}
chqrlie
quelle
Ja, das funktioniert, denke ich. Vielen Dank für all die Hilfe
Ronen Dvorkin
Zuletzt double rec_sqrt_series(int n)erfüllt IMO die Ziele von OP, indem das Zeichen als Rekursionsflag verwendet wird. (Ich würde das fallen lassen, elseda es nicht benötigt returnwird if.)
chux - Monica
1
@ chux-ReinstateMonica: das Löschen elseist natürlich möglich, aber ich mag es irgendwie, beide Zweige der ifRückgabe eines Ergebnisses zu symmetrieren , eine Art funktionalen Programmierstil.
Chqrlie
@ chux-ReinstateMonica: Ich gehe davon aus, dass die Anforderung der Zuweisung "nur Rekursion" eine Iteration ausschließt.
Eric Postpischil
@EricPostpischil: Ja, ich dachte das gleiche, bekam aber kein Feedback vom OP.
Chqrlie
0

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
}
4386427
quelle