Obliczanie zagnieżdżonego katalogu głównego w C

Poproszono mnie o obliczenie następującego zagnieżdżonego wyrażenia głównego przy użyciu tylko rekurencji .

Napisałem poniższy kod, który działa, ale pozwolili nam użyć tylko jednej funkcji i 1 wejścia ndo tego celu, a nie 2 takich jak ja. Czy ktoś może mi pomóc przekształcić ten kod w jedną funkcję, która obliczy wyrażenie? nie mogę użyć żadnej biblioteki oprócz funkcji z <math.h>.

wyjście dla 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);
}

Użyj górnych bitów njako licznika:

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

Oczywiście to działa nieprawidłowo, gdy wartość początkowa njest Rwiększa lub większa. Oto bardziej skomplikowana wersja, która działa dla dowolnej dodatniej wartości n. To działa:

• Gdy njest ujemne, działa jak w powyższej wersji, zliczając górne bity.
• Kiedy njest dodatnia, jeśli jest mniejsza niż R, wywołuje się w -ncelu oceny funkcji jak wyżej. W przeciwnym razie nazywa się R-1negacją. To ocenia funkcję tak, jakby była wywołana za pomocą R-1. Daje to prawidłowy wynik, ponieważ seria przestaje się zmieniać w formacie zmiennoprzecinkowym po zaledwie kilkudziesięciu iteracjach - pierwiastki kwadratowe z głębszych liczb stają się tak rozcieńczone, że nie działają. Tak więc funkcja ma tę samą wartość dla całego nmałego progu.

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

Bez matematycznego przekształcenia formuły (nie wiem, czy jest to możliwe), nie można tak naprawdę użyć tylko jednego parametru, ponieważ dla każdego elementu potrzebne są dwie informacje: bieżący krok i oryginał n. Możesz jednak oszukiwać . Jednym ze sposobów jest zakodowanie dwóch liczb w intparametrze (jak pokazuje Eric ).

Innym sposobem jest przechowywanie oryginału nw statycznej zmiennej lokalnej. Przy pierwszym wywołaniu, które zapisujemy nw tej zmiennej statycznej, rozpoczynamy rekurencję, a na ostatnim etapie resetujemy ją do wartości wartownika:

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

Najwyraźniej static int n = sentinelnie jest standardowym C, ponieważ sentinelnie jest stałą czasową kompilacji w C (to dziwne, ponieważ zarówno gcc, jak i clang nie narzekają, nawet z -pedantic)

Możesz to zrobić zamiast tego:

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

Ten problem wymaga wykrzywionych rozwiązań.

Oto jedna, która korzysta z jednej funkcji, biorąc jeden lub dwa intargumenty:

• jeśli pierwszy argument jest dodatni, oblicza wyrażenie dla tej wartości
• jeśli pierwszy argument jest ujemny, po nim musi następować drugi argument i wykonuje pojedynczy krok w obliczeniach, powtarzając się w poprzednim kroku.
• wykorzystuje, <stdarg.h>które mogą, ale nie muszą być dozwolone.

Oto kod:

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

Oto inne rozwiązanie z pojedynczą funkcją, używając tylko <math.h>, ale nadużywając reguł w inny sposób: używając makra.

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

Jeszcze jeden, ściśle rekurencyjny , ale z jednym poziomem rekurencji i bez innych sztuczek. Jak skomentował Eric , wykorzystuje forpętlę, która może być niepoprawna z powodu ograniczeń PO:

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

Oto inne podejście.

Polega na intbyciu 32 bitami. Chodzi o to, aby korzystać z górną 32 bit 64 bit intdo

1) Sprawdź, czy połączenie było połączeniem rekurencyjnym (czy połączeniem „z zewnątrz”)

2) Zapisz wartość docelową w górnych 32 bitach podczas rekurencji

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