Quadratischer Rest rekursiv berechnen

nep

Hi,

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

der Gauß-Klammer.

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?

Christoph

nep schrieb:

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

der Gauß-Klammer.

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.

nep

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?

Christoph

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.

nep

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

Shinja

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?