Récurrence relations devoirs Struggles
-
27-10-2019 - |
Question
Voici la question:
Résoudre la récurrence en obtenant un thêta lié à T (n) étant donné que T (1) = theta (1).
T(n) = n + T(n-3)
Solution Tentative:
T(n) = T(n-6) + (n-3) + n
= T(n-9) + (n-6) + (n-3) + n
= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]
= T(1) + [0 + 3 + 6 + ... + n]
= theta(1) = 3[1 + 2 + 3 + ... + n/3]
= theta(1) + [(n/3)(n/3 + 1)]/2
= theta(1) + (n^2+3n)/6
Quand je double vérification pour voir si la solution correspond à la récurrence, il ne fonctionne pas.
La solution
La question est que vous obtenez la mauvaise sommation. Il ne démarre pas à 0, depuis votre dernière fonction T a T (n - (n-1)), ce qui signifie précédent était T (n (n-4)). Ainsi, la somme commence à 4, et va jusqu'à n.
Si vous ne savez pas comment trouver la somme, je vous suggère de regarder quelques-unes des preuves de la formule de sommation. C'est ce que la solution ressemble.
T(n) = T(n-3) + n
= T(n-6) + (n-3) + n
= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n]
= T(1) + [4 + 7 + ... + n]
= theta(1) + (4 + n) * (n - 1)/6
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow