Betrachten Sie die folgende Rekursionsbeziehung.Suchen einer geschlossenen Form für rekursive Funktion
T(n) = 5 if n <= 2
T(n-1) + n otherwise
geschlossene Lösung für T(n) ist
Ich habe Lösung als n(n+1)/2 + 7 für alle Werte. Aber in meiner Universitätsprüfung gaben sie die Lösung n(n+1)/2 + 2. Diese Lösung endet jedoch nicht bei 5 für die Werte n<2. Kann ein Körper bitte erklären?
Lassen Sie uns es lösen; lassen Sie uns zuerst in Teleskop Summen erweitern:
T(k) = T(k)
T(k + 1) = T(k) + k + 1
T(k + 2) = T(k + 1) + k + 2 = T(k) + k + 1 + k + 2
...
T(k + m) = T(k) + k + 1 + k + 2 + ... + k + m =
= T(k) + mk + 1 + 2 + ... + m =
= T(k) + mk + (1 + m) * m/2
...
Jetzt haben wir
T(k + m) = T(k) + mk + (1 + m) * m/2
k = 2 Lassen:
T(m + 2) = T(2) + 2m + (1 + m) * m/2 = 5 + 2m + (1 + m) * m/2
Schließlich lassen m + 2 = n oder m = n - 2:
T(n) = 5 + 2 * (n - 2) + (n - 1) * (n - 2)/2 = n * (n + 1)/2 + 2
Wir haben
T(n) = n * (n + 1)/2 + 2 when n > 2
T(n) = 5 when n <= 2
Wenn Sie eine geschlossene Formularlösung betrachten, können wir Ausnahmen hinzufügen, dass das T (n) nicht gültig für n <2 ist. Die Funktion T (n) sollte bei allen Werten ohne Ausnahmen enden. Ist das nicht die geschlossene Form? Wenn wir Ausnahmen hinzufügen, die für n <2 sind, wird T (n) ein anderes Ergebnis liefern ... wie können wir dann eine geschlossene Formlösung nennen? –
@ Y.Surya Narayana: Wie du sehen kannst, beginnen wir damit, * die Serie zu erweitern: 'T (k) = ... T (k + 1) = ...' deshalb ist die Seelenwahrheit wahr, beginnend mit einigen ' k'. Dann setzen wir explizit "k = 2", was der minimale Index ist, den wir verwendet haben, so dass die Lösung für die Indizes mehr als "2" gilt: "T (n) = n * (n + 1)/2 + 2 wenn n > 2': Wir haben 'T (2)' nicht berechnet, aber haben es genommen. –
Als einfache nicht-strenge Argumentation Übung, wir bekannt, dass T(n) = T(n-1) + n die Summe der ersten n Zahlen ergeben: S(n) = n * (n + 1)/2
Nun, wenn n=2, S(2) = 3, so dass der Wert von 5 ist eigentlich ein Inkrement von 5 - S(2) = 2. So könnten wir sagen:
T(n) = S(n) + (5 - S(2)) for n >=2
oder
T(n) = S(n) + 2 for n >= 2
T(n) = 5 for n <= 2
Beachten Sie, dass bei n=2 die beiden Beziehungen identisch sind.
n (n + 1)/2 + 2 ist keine Lösung der angegebenen Gleichungen. Was ist zu erklären? –
@PaulHankin hat es getestet, 'n (n + 1)/2 + 2' funktioniert für alle Werte im Bereich 2-50. Funktioniert nicht für "n = 1", aber abgesehen davon ist dies definitiv die Lösung. – Paul
Ich stimme ab, diese Frage als off-topic zu schließen, weil es eine reine mathematische Frage ist, keine Programmierfrage. –