Niedługo mam egzamin, a chcę umieć, jak napisać równanie rekurencyjne na podstawie algorytmu.
Niech będzie ten algorytm:
ALGORYTM(n)
if n=1
then return 20+40
else ALGORYTM(n/2)
for i <-- 1 to n
do a <-- 10 * i
return ALGORYTM(n/2)
Moje rozwiązanie:
T(1) = 60
T(n) = 2T(n/2)+1, dla n>1
Jest ok.?
Ten algorym się kupy nie trzyma...
Jest ponoć dobrze napisany. Prowadzący go napisał, a po to, żeby można było się nauczyć pisać równania rekurencyjne.
Te "ponoć" jest nic nie warte. Bez względu jak się interpretuje (w rozsądny sposób) ten zapis jest bezsensu.
Coś musiałeś przekręcić, szczególnie ta część "ALGORYTM(n/2) for i <-- 1 to n do a <-- 10 * i" jest bezsensu.
Może macie rację. Algorytm dobrze przepisany. W sumie nie wiem, co mam w tej sytuacji robić. Algorytmy są ze starych zestawów z listopada. Przepisałem je stamtąd, bo chciałem się poćwiczyć, jak napisać równania rekurencyjne.
A co myślicie o tym? Czy też jest bez sensu napisany?
ALG2(n)
if n=1
then return a + b
a-b
if n=2
then return a * b
else ALG2(n-1)
a/b
ALG2(n-1)
return a
Może odstęp ma jakieś znaczenie?
No niestety, też jest bez sensu napisany...
Jeśli chcesz poćwiczyć równania rekurencyjne, polecam Cormena, już na samym początku są ładnie opisane.