Rekursive Gleichungen lösen
Verfasst: Sa Jul 30, 2016 3:47 pm
Hallo,
ich würde gerne wissen, wie man bei der Lösung rekursiver Gleichungen vorgeht.
Beispiel: C[N] = C[N-1] + N für N >= 2, mit C[1] = 1.
Augelöst = C[N] beträt ungefähr N²/2
Im Buch steht dazu folgende Rechnung (von mir kommentiert):
C[N] = C[N-1] + N
= C[N-2] + (N-1) + N // das N-1 kommt doch daher, dass das N aus C[N-1] = N -1 sein muss und dann nur noch das C[N-2] aus C[N-1] zurück bleibt, oder?
= C[N-3] + (N-2) + (N-1) + N
...
= C[1] + 2 + ....+ (N-2) + (N-1) + N
= 1 + 2 + ... + (N-2) + (N-1) + N //soweit verstehe ich es, glaube ich zumindest
= (N(N+1)/2 //wie jetzt das?
bei der Erklärung steht nun, das man N * (N+1) und dies doppelt so groß ist wie das Ergebnis also noch geteilt durch 2.
Wie kommt man nun auf das geteilt durch 2?
Meine Idee: Man läuft die Rechnung N mal durch und die "Grundstellung" ist C[2] = 1 + N oder N+1 also N(N+1), aber wie geht man dann weiter vor um das geteilt durch 2 zu erhalten?
Ein anderes Beispiel:
C[N] = C[N/2] + N, für N >=2, mit C[1] = 0
C[N] = ungefähr 2N //steht so im Buch
Meine Überlegungen: Man läuft die Gleichung log2(N) durch (wenn N eine zweierpotzen ist) und hat als Grundformel C[2] = 0 + N. Müsste das Ergebnis dann nicht log2(N)*N sein? Wie kommt man also auf das Ergebnis.
Ich gebe zu bedenken, dass ich das Thema Rekursion noch nicht in der Schule hatte (glaube auch nicht, dass ich es in der Oberstufe haben werde). Für eine einfache und ausführliche Antwort wäre ich also sehr dankbar, oder für Lehrmaterial, welches das Thema recht einfach erklärt.
für Hilfe wäre ich sehr dankbar.
p.s Das O bei der O-Notation glit doch immer für den größten N-Wert einer Rechnung, wenn g(n) = O(g(n)) gelten soll?
Beispiel: g(n) = n² +n; g(n) = O(n²)
oder g(n) = n*lg(n) +n; g(n) = O(n) (für zumindest kleinere Werte für n, da irgendwann n*lg(n) größer ist)
ich würde gerne wissen, wie man bei der Lösung rekursiver Gleichungen vorgeht.
Beispiel: C[N] = C[N-1] + N für N >= 2, mit C[1] = 1.
Augelöst = C[N] beträt ungefähr N²/2
Im Buch steht dazu folgende Rechnung (von mir kommentiert):
C[N] = C[N-1] + N
= C[N-2] + (N-1) + N // das N-1 kommt doch daher, dass das N aus C[N-1] = N -1 sein muss und dann nur noch das C[N-2] aus C[N-1] zurück bleibt, oder?
= C[N-3] + (N-2) + (N-1) + N
...
= C[1] + 2 + ....+ (N-2) + (N-1) + N
= 1 + 2 + ... + (N-2) + (N-1) + N //soweit verstehe ich es, glaube ich zumindest
= (N(N+1)/2 //wie jetzt das?
bei der Erklärung steht nun, das man N * (N+1) und dies doppelt so groß ist wie das Ergebnis also noch geteilt durch 2.
Wie kommt man nun auf das geteilt durch 2?
Meine Idee: Man läuft die Rechnung N mal durch und die "Grundstellung" ist C[2] = 1 + N oder N+1 also N(N+1), aber wie geht man dann weiter vor um das geteilt durch 2 zu erhalten?
Ein anderes Beispiel:
C[N] = C[N/2] + N, für N >=2, mit C[1] = 0
C[N] = ungefähr 2N //steht so im Buch
Meine Überlegungen: Man läuft die Gleichung log2(N) durch (wenn N eine zweierpotzen ist) und hat als Grundformel C[2] = 0 + N. Müsste das Ergebnis dann nicht log2(N)*N sein? Wie kommt man also auf das Ergebnis.
Ich gebe zu bedenken, dass ich das Thema Rekursion noch nicht in der Schule hatte (glaube auch nicht, dass ich es in der Oberstufe haben werde). Für eine einfache und ausführliche Antwort wäre ich also sehr dankbar, oder für Lehrmaterial, welches das Thema recht einfach erklärt.
für Hilfe wäre ich sehr dankbar.
p.s Das O bei der O-Notation glit doch immer für den größten N-Wert einer Rechnung, wenn g(n) = O(g(n)) gelten soll?
Beispiel: g(n) = n² +n; g(n) = O(n²)
oder g(n) = n*lg(n) +n; g(n) = O(n) (für zumindest kleinere Werte für n, da irgendwann n*lg(n) größer ist)