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


9

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

wprowadź opis zdjęcia tutaj

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

Czy ktoś może mi pomóc przekształcić ten kod w jedną funkcję, która obliczy wyrażenie? co? Pomóc pozbyć się helper?
4386427

Jeśli argumenty są błędne, zadzwoniłbym abort()(z <stdlib.h>), nie po cichu zwraca 0
Kaz

1
@chqrlieforyellowblockquotes Twisied. @pastaleg Co powiesz na bezużyteczną rekurencję? 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 - Przywróć Monikę

1
@ chux-ReinstateMonica: tak, prostsze nadużycie zasad.
chqrlie

2
@Open: Jeśli celem zadania było sfinansowanie nierekurencyjnego wyrażenia funkcji, prawdopodobnie nie zażądałby rozwiązania problemu za pomocą „tylko rekurencji”. Z pewnością prosta pętla z łatwością obliczy wynik. Chociaż generalnie jestem podejrzliwy, gdy te pytania są wysyłane do Przepełnienia stosu bez rzeczywistego tekstu zadania.
Eric Postpischil

Odpowiedzi:


7

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

Dobry pomysł, ale zakłada 32-bitowe
ints

1
@chqrlieforyellowblockquotes: Nie, dlatego Rjest osobny, więc można go dostroić. Przed nosiągnięciem 32 wartość zwracana przestaje się zmieniać dla IEEE-754 binary64, a zanim osiągnie 256, zwracana wartość przestaje się zmieniać dla rozsądnych formatów double. Zastanawiam się więc nad alternatywną wersją, która przekształca dane zacisków powyżej R, ale musi użyć bitu znakowego i nadal nad tym pracuję.
Eric Postpischil

Istnieją inne funkcje parowania, których można użyć, ale żadna z nich nie jest tak prosta jak Twoja. Ich główną zaletą jest zazwyczaj to, że pracują z dowolną precyzją, ale OP nigdy nie wspomniało o tym jako wymogu.
Ruud Helderman

@chqrlieforyellowblockquotes: Gotowe. Teraz daje poprawną odpowiedź dla każdego pozytywnego nniezależnie od szerokości int.
Eric Postpischil

5

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;

Ciekawe podejście, ale obawiam się, że inicjator static int n = sentinel;nie jest w pełni zgodny z C, ponieważ sentinelnie jest stałym wyrażeniem zgodnie ze standardem C. Działa w C ++ i kompiluje się z aktualnymi wersjami gcc i clang w trybie C, ale nie MSVC 2017, ale prawdopodobnie powinieneś napisać static int n = -1;patrz godbolt.org/z/8pEMnz
chqrlie

1
@chqrlieforyellowblockquotes ish. Dziękujemy za zwrócenie na to uwagi. Ciekawe zachowanie kompilatora. Zapytałem o to w tym pytaniu: stackoverflow.com/q/61037093/2805305
bolov

5

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

tak, to chyba działa. bardzo dziękuję za wszelką pomoc
Ronen Dvorkin

Wreszcie double rec_sqrt_series(int n), IMO, spełnia cele OP, używając znaku jako flagi rekurencyjnej. ( elsereturnif
Rzuciłbym

1
@ chux-ReinstateMonica: upuszczenie elsejest oczywiście możliwe, ale lubię symetrię obu gałęzi ifzwracanego wyniku, rodzaj funkcjonalnego stylu programowania.
chqrlie

@ chux-ReinstateMonica: Oczekuję, że wymóg „tylko rekurencja” w zadaniu wyklucza iterację.
Eric Postpischil

@EricPostpischil: tak, myślałem tak samo, ale nie otrzymałem opinii od OP.
chqrlie

0

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
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.