Quadratischer Rest rekursiv berechnen



  • Hi,

    also der quadratische Rest ist ja wie folgt definiert:
    q(n) = n - [ sqrt(n) ]²

    Wie könnte man das jetzt rekursiv berechnen? Wäre super wenn mir da jemand weiterhelfen könnte. Bin nicht so der Held in Rekursionen 😞

    Wenn jemand ausserdem eine Idee hat, wie ich rekursiv das Minimum 2er Zahlen bestimmen kann, dann wäre das auch hilfreich... also sprich wie könnte ich ne Funktion min(int m, int n) rekursiv berechnen?


  • Mod

    nep schrieb:

    also der quadratische Rest ist ja wie folgt definiert:
    q(n) = n - [ sqrt(n) ]²

    Wie könnte man das jetzt rekursiv berechnen? Wäre super wenn mir da jemand weiterhelfen könnte. Bin nicht so der Held in Rekursionen 😞

    Zuerst musst du dir den Basis-Fall anschauen, also z.B. das kleinste n. In deinem Fall sind die einfachten Fälle n=0 und n=1, also definierst du schonmal
    q(0) = 0
    q(1) = 0.
    Dann musst du überlegen, ob du den allgemeinen Fall n>1 auf die niedrigeren Fälle zurückführen kannst. Ich nehme mal an, dass du nur Additionen und Subtraktionen benutzen möchtest, denn sonst bräuchtest du ja nicht rekursiv rechnen. Dein q ist für Quadratzahlen genau 0, ansonsten gerade die Differenz zur nächstkleineren Quadratzahl. Die nächstkleinere Quadratzahl ist q' := n-1-q(n-1). Also hat man:
    q(n) = 0 | falls n Quadratzahl
    q(n) = n - q' | falls n keine Quadratzahl

    Um jetzt festzustellen, ob n eine Quadratzahl ist, kannst du ausnutzen, dass die Differenzen von Quadratzahlen einem sehr einfachen Muster folgen:
    0,1,4,9,16,25,...
    Die Differenzen zweier aufeinanderfolgender Quadratzahlen wachsen immer um 2:
    1,3,5,7,9,...
    Du musst also nur die Differenz der letzten beiden Quadratzahlen nehmen, 2 dazuaddieren und schauen, ob das die Differenz von n zur nächstkleineren Quadratzahl ist. Zuerst noch der nächstkleinere Quadratzahl einen Namen geben, damit man einfacher darüber reden kann: q'' := q' - 1 - q(q' - 1).
    Dann ist die Definition von q:
    q(n) = 0 | falls q' - q'' + 2 = n - q'
    q(n) = n - q' | sonst

    In Haskell würde das etwa so aussehen:

    q 0 = 0
    q 1 = 0
    q n | q' - q'' + 2 == n - q' = 0
        | otherwise = n - q'
        where q'  = (n-1) - q (n-1)
              q'' = (q'-1) - q (q'-1)
    

    nep schrieb:

    Wenn jemand ausserdem eine Idee hat, wie ich rekursiv das Minimum 2er Zahlen bestimmen kann, dann wäre das auch hilfreich... also sprich wie könnte ich ne Funktion min(int m, int n) rekursiv berechnen?

    Falls du min(unsigned int, unsigned int) meinst, sind die Basisfälle min(0, n) = min(m, 0) = 0 für alle m, n. Den allgemeinen Fall bekommst du bestimmt selbst raus, der ist viel einfacher als der für die Quadratzahlen.



  • Hi,
    also erst mal danke für die ausführliche Hilfe.
    Das mit dem quadratischen Rest ist ja doch ganz schön aufwendig, aber ich denke ich habe es einigermaßen 😉 verstanden... ich hab jetzt mal versucht das in eine C Funktion zu packen:

    int quadRest(int n) {
    
    	if ( n <= 1)
    		return 0;
    	else {
    		int q1 = (n-1) - quadRest(n-1);
    		int q2 = (q1-1) - quadRest(q1-1);
    		if ( q1 - q2 + 2 == n - q1)
    			return 0;
    		else
    			return quadRest(n-q1);
    	}
    }
    

    Allerdings krieg ich da immer 0 zurück.

    Bei dem min(unsigned m, unsigned n) hängts bei mir auch irgendwo; solche Rekursionen sind einfach nicht mein Ding 😞
    Also ich hab mir halt gedacht, dass man das in Subtraktionen zerlegen kann, d.h. dass ich diese Funktion dann immer mit beiden Argumenten um eins vermindert rekursiv aufrufe. Wenn dann z.B. der if (m <= 0) - Zweig durchlaufen wird, dann weiß ich, dass m das Minimum ist. Nur kann ich dann ja nicht die eigentliche Zahl m zurückgeben, sondern nur 0 (da m ja jetzt auch 0 ist). Also das funktoniert natürlich, wenn ich noch 2 Zusatzparameter hab, welche bei jeder Rekursion die Originalwerte mitschleppen. Aber vielleicht gibts da noch ne "elegantere" möglichkeit?


  • Mod

    nep schrieb:

    ich hab jetzt mal versucht das in eine C Funktion zu packen:

    if ( q1 - q2 + 2 == n - q1)
    			return 0;
    		else
    			return quadRest(n-q1);
    

    Im else-Zweig musst du nicht mehr quadRest aufrufen.

    nep schrieb:

    Also ich hab mir halt gedacht, dass man das in Subtraktionen zerlegen kann, d.h. dass ich diese Funktion dann immer mit beiden Argumenten um eins vermindert rekursiv aufrufe.

    Das ist genau der richtige Ansatz.

    nep schrieb:

    Wenn dann z.B. der if (m <= 0) - Zweig durchlaufen wird, dann weiß ich, dass m das Minimum ist. Nur kann ich dann ja nicht die eigentliche Zahl m zurückgeben, sondern nur 0 (da m ja jetzt auch 0 ist). Also das funktoniert natürlich, wenn ich noch 2 Zusatzparameter hab, welche bei jeder Rekursion die Originalwerte mitschleppen. Aber vielleicht gibts da noch ne "elegantere" möglichkeit?

    Du denkst schon einen Schritt zu weit. Was du planst, nennt sich Endrekursion (tail recursion). Das ist programmiertechnisch in erster Linie eine Optimierung.
    Endrekursion bedeutet, dass der rekursive Aufruf der allerletzte ist und nichts mehr mit dem Ergebnis gemacht wird, es also direkt zurückgegeben wird. Sowas ist zum Beispiel endrekursiv:

    uint fac(uint n, uint a = 1) {
      if(n == 0)
        return a;
      else
        return fac(n - 1, n * a);
    }
    

    fac(n) berechnet n!, also 1*2*3*4*...*n. Falls fac rekursiv aufgerufen wird (falls also n nicht 0 ist), wird danach nichts mehr mit dem Ergebnis angestellt.
    Das hier wäre eine nicht endrekursive Version derselben Funktion:

    uint fac2(uint n) {
      if(n == 0)
        return 1;
      else
        return n * fac(n - 1);
    }
    

    Hier wird nach dem rekursiven Aufruf etwas mit dem Ergebnis gemacht: Es wird mit n multipliziert. Dadurch verbraucht fac2 sehr viel mehr Speicher als fac, weil der rekursive Aufruf nicht wegoptimiert werden kann. Bei der ersten Version wird statt eines "call"- ein "jmp"-Befehl im erzeugten Code stehen. Im allgemeinen kann Endrekursion den Speicherverbrauch eines Algorithmus enorm senken.

    Aber wenn es nur ums Prinzip geht, so wie bei dir, muss man nicht auf Endrekursion achten. Du lagst ganz richtig mit der Idee, min(m-1, n-1) als rekursiven Aufruf zu benutzen. Denn du hast zu dem Zeitpunkt ja schon ausgeschlossen, dass m oder n gleich 0 sind. Der Trick bei der Rekursion ist nun, dass du annehmen darfst, dass min() mit Parametern, die kleiner als m, n sind, bereits völlig korrekt arbeitet. Du kannst also das Minimum von m-1 und n-1 bestimmen, indem du einfach min(m-1, n-1) aufrufst. Was musst du damit machen, um daraus das Minimum von m und n zu bekommen?

    p.s.: Achso, bei der q-Funktion siehst du zum Beispiel, dass naive rekursive Algorithmen in C++ nicht wirklich gut funktionieren: Denn bei der Funktion gibt es pro Aufruf zwei rekursive Aufrufe und kein Caching, d.h. der Rechenaufwand steigt exponentiell.



  • Ahja super, jetzt funktioniert das mit dem Quadratischen Rest.

    Sowieso, jetzt hab ich ja noch richtig viel gelernt hier durch dich und bisschen über den Tellerrand geschaut, danke 🙂

    Aber wenn es nur ums Prinzip geht, so wie bei dir, muss man nicht auf Endrekursion achten. Du lagst ganz richtig mit der Idee, min(m-1, n-1) als rekursiven Aufruf zu benutzen. Denn du hast zu dem Zeitpunkt ja schon ausgeschlossen, dass m oder n gleich 0 sind. Der Trick bei der Rekursion ist nun, dass du annehmen darfst, dass min() mit Parametern, die kleiner als m, n sind, bereits völlig korrekt arbeitet. Du kannst also das Minimum von m-1 und n-1 bestimmen, indem du einfach min(m-1, n-1) aufrufst. Was musst du damit machen, um daraus das Minimum von m und n zu bekommen?

    Tja das ist die Frage 😉 Irgendwie stehe ich da auf dem Schlauch, bzw. komm ebend immer nur auf meine Lösung. Ich meine ist jetzt auch nicht so wichtig, wie du auch schon selbst sagtest, da es bei mir eh nur ums Prinzip geht. Aber interessieren tuts mich schon 😉



  • Naja, denk mal kurz nach: min(m,n) soll entweder m oder n zurueckliefern (je nachdem) min(m-1,n-1) liefert also m-1 oder n-1 zurueck. Verglichen mit den Werten die zurueckgegeben werden sollen sind die was?


Log in to reply