Algorytmy problem kolejny

[gizmo1985]

Hej Wam
Mam takie śmieszne zadanko i nie wiem jak zwykle jak je zagryźć

Dana jest procedura, która wypisuje + na ekranie Ile wypisze + w zależności od liczby n ?

Kod: Zaznacz cały

Krzyzyk(n)
if n = 1 
then Write(+)
else for i=1 to n-1
do Krzyzyk(i)
for i=1 to n
do for j=1 to n
do Write(+)

Generalnie nie chodzi mi o samo stwierdzenie ile, bo to może nie byłoby takie straszne Muszę to wykazać obliczeniami. Jak to ugryźć?

Pozdrawiam

[Zordon]

Napisz wzór rekurencyjny.

[gizmo1985]

Hmm, brzmi zachęcająco a może coś więcej, bo nie bardzo mi to rozjaśniło

[matshadow]

zobacz ile wypisze dla n=1, n=2 itp, i spróbuj znaleźć jakąś zależność

[gizmo1985]

No ok zbadałem, asem z algorytmów nie jestem, ale wyszło mi, że zależność dla n>1 wynosi n^{2}

Dla n = 3 wykona się 9 razy
dla n = 4 wykona się 16
dla n=5 wykona się 25

i.t.d

Co dalej mi to daje ? generalnie nie wiem jak to pociągnąć dalej, chyba mam dobry tok rozumowania, ale nie wiem jak to skleić w całość. Wydaje mi się, że sama zależność n2 nic mi nie da

możecie pomóc ? bo nie umiem tego poskładać, a nie daje mi to spać

Czyli podstawiając do wzoru :

a(n) = a(n) * a(n)

[smiechowiec]

No ok zbadałem, ... wyszło mi, że zależność dla n>1 wynosi n^{2}

Dla n = 3 wykona się 9 razy
dla n = 4 wykona się 16
dla n=5 wykona się 25
Czyli podstawiając do wzoru :

a(n) = a(n) * a(n)

Obawiam się, że algorytm funkcji Krzyzyk może być nieco inny.
Zobaczmy co się dzieje w kolejnych instrukcjach
1. Jeżeli (n = 1) => Write(+)
2. Wywołaj Krzyzyk dla parametrów mniejszych od n => Krzyzyk(i) tyle razy ile byłoby dla wszystkich mniejszych n czyli jest to suma dotychczasowych wyników.
3. Wypisz n kwadrat krzyżyków
Wniosek \(\displaystyle{ Krzyzyk(1) = 1 + 1}\)
dla większych n mamy
\(\displaystyle{ Krzyzyk(n) = n^2 + \sum_{i=1}^{n} Krzyzyk(i)}\)
przykładowe wartości
Krzyzyk(1) = 2
Krzyzyk(2) = 2 + 4 = 6
Krzyzyk(3) = 2 + 6 + 9 = 17
Krzyzyk(4) = 2 + 6 + 17 + 16 = 41
Krzyzyk(5) = 2 + 6 + 17 + 41 + 25 = 91

[gizmo1985]

No ok Zrozumiałem przykładowe wyniki, nie rozumiem tylko skąd ten tok myślenia, czy możesz jaśniej to rozumowanie wyjaśnić ? bo szczerze to się zgubiłem szedłem w całkiem inną stronę.
Skąd tam to \(\displaystyle{ n^{2}}\) ? I dlaczego jest to suma poprzednich wyników ?

[smiechowiec]

Może zacznijmy od anaily algorytmu który podałeś.
Krzyzyk(n)
if n = 1
then Write(+)
else for i=1 to n-1
do Krzyzyk(i)
for i=1 to n
do for j=1 to n
do Write(+)

Dla n = 1 mamy

if n = 1
then Write(+) => więc wypisujemy 1 krzyżyk

Warunek przciwny jest pomijany
else for i=1 to n-1
do Krzyzyk(i)

for i=1 to 1
do for j=1 to 1
do Write(+) => czyli wypisujemy jeden krzyżyk

Czyli dla n = 1 wypisaliśmy 2 krzyżyki

Dla n = 2 mamy

else for i=1 to 1
do Krzyzyk(i) => wypisujemy krzyżyki dla n = 1 czyli 2


for i=1 to 2
do for j=1 to 2
do Write(+) => czyli wypisujemy 2 razy 2 krzyżyków

Czyli dla n = 2 wypisaliśmy 2 + 4 = 6 krzyżyków

zgoda ?

[gizmo1985]

tak, teraz zgoda;) Troszkę się to pokrywa z moim tokiem hehe , nie do końca, ale prawie Jeszcze ciekawi mnie geneza tego wzoru, bo będe musiał go wybronić

[smiechowiec]

tak, teraz zgoda;) ciekawi mnie geneza tego wzoru

Dla jedynki chyba sprawa jest już jasna,
dla większych n czynnik n kwadrat pochodzi z końca funkcji
for i=1 to n
do for j=1 to n
do Write(+)

Suma poprzednich wyników pochodzi z pętli wykonywanej dla n > niż 1
for i=1 to n-1
do Krzyzyk(i),
która wprost wywołuje samą siebie dla wszystkich i mniejszych od n

[gizmo1985]

no tak, 2 kwadrat, bo mamy pętlę w pętli,
Hehe, teraz już rozumiem wielkie dzięki, te algorytmy były dla mnie nie do przejścia
Miałem jeszcze 2 tematy z algorytmami, jakbyś tylko zerknął okiem, wcale bym się nie pogniewał

-- 18 lis 2010, o 20:26 --

Czyli rozumiem, że zapis ostateczny rozwiązania powinien wyglądać :
2 dla n=1
\(\displaystyle{ Krzyzyk(n) = n^2 + \sum_{i=1}^{n} Krzyzyk(i) dla n>1}\)