Eli-algorytmy

Gość

Rekurencja: w teoretyce rekurencją nazywamy po prostu wywoływanie samego siebie. W praktyce ogranicza się to głównie do sytuacji takich, jak na WDI - każdorazowe wywołanie schodzi o "poziom niżej", czyli podaje dalej n-1. Rzadko stosuje się rekurencję w inny sposób, bo to dość chaotyczne i ciężkie do opanowania - czyli potencjalnie niebezpieczne.

Odnośnie tych przykładów z n-1.
Załóżmy, że mamy stworzyć podprogram, który przyjmie liczbę n i wyliczy z niej silnię.
Wychodzimy tutaj z założenia, że jeśli np. n będzie wynosić 5, to nie rozpisujemy 5! standardowo jako:
5! = 5 * 4 * 3 * 2 * 1
, a tak:
5! = 4! * 5
Z kolei 4! będzie wynosić:
4! = 3! * 4
i dalej:
3! = 2! * 3
2! = 1! * 2
1! = 0! * 1
0! = 1

Na każdym, prócz ostatniego, poziomie mamy dokładnie ten sam wzór "lokalny":
n! = (n-1)! * n
Tak więc przestajemy się w ogóle interesować tym, że jest to jakiś ciąg, czasem ogromnej ilości elementów, nie interesują nas żadne pętle i inne takie - stosujemy w kółko skrajnie banalny wzór i dochodzimy do rozwiązania nieco ekhmm... bardziej "naturalnymi" metodami, niż organizowanie pętli.
Czyli zmniejszamy "pole widzenia" programisty - nie musi on już przeglądać całej pętli, jak ona idzie od początku, do końca, jak kolejno zlicza, kiedy się zaczyna, kiedy kończy i co właściwie robi - wszystko się sprowadza do jakby samoistnie się wykonującego, "myślącego" algorytmu, składającego się zazwyczaj z prostego jak drut przeliczenia. Przestajemy w ogóle uważać na to, jak algorytm ma zliczać cały ciąg - istnieje dla nas tylko obliczenie jednego jego elementu, a zliczenie całości wychodzi jakoś "samo".

A przechodząc do praktycznego rozwiązania na przykładzie tej silni.
Mamy jakąś funkcję/procedurę silnia - ona przyjmuje jako parametr liczbę n i zwraca wartość silni dla niej.
Funkcja będzie skrajnie banalna - zwróci po prostu:
return silnia(n-1) * n
Czyli nasz wcześniejszy wzór - jeśli poprosimy o silnię z 5, funkcja po prostu wywoła samą siebie dla 4 i to pomnoży razy 5. Tamto wywołanie dla 4 wywoła siebie dla 3 i wynik pomnoży razy 4. To z kolei pójdzie jeszcze głębiej i tak aż do tego ostatniego etapu (we wcześniejszej rozpisce zaznaczyłem, że 0! już nie jest obliczana z tego samego wzoru - wynosi po prostu 1 i tyle). Stąd na samym początku funkcji potrzebny jest jeszcze warunek, że jeśli n wyniesie 0, funkcja już dalej się nie wywołuje, a po prostu zwróci stałą wartość 1.
I tak to wszystko działa :-)

Tak ogólnie o rekurencji: generalnie to jest chujowa. Tzn. zabiera wieeeelokrotnie więcej zasobów od zwyczajnej pętli.
Zauważmy, że jeśli np. wywołamy naszą silnię dla 100, to w momencie, gdy będzie wywoływana silnia(0), zamrożone i oczekujące będą wszystkie wywołania z góry - a tych będzie 100. Tak więc komputer musi pamiętać o tej setce oczekujących na wyniki funkcji, musi pamiętać ich wszystkie lokalne zmienne, musi pamiętać, w którym miejscu program się zatrzymał, itd. Zresztą wystarczy sobie napisać taką silnie w ELI za pomocą pętli i rekurencji - włączyć podglądanie zmiennych i od razu zobaczymy różnicę w ich ilości - kilkadziesiątkrotną dla 100!. A co gdybyśmy sobie zażyczyli 10000! ?
W takim razie jakie są jej zalety? Jak pisałem wcześniej - w wielu przypadkach znacznie upraszcza spojrzenie na jakiś problem. W świecie programowania wydajność już od dawna nie jest absolutnie najważniejszym priorytetem - w wielu dziedzinach stawia się na przejrzystość zaprojektowanej konstrukcji. Wam w tym momencie rekurencja może się wydawać właśnie nieprzejrzysta, ale to kwestia nieco nietypowego jej podejścia - uwierzcie, że zazwyczaj aż błogo jest popatrzyć, jak 3 linijki naszego kodu wywołują cały szereg niekontrolowanych, wydawać by się mogło, procesów, które jakimś cudem układają się pięknie w rozwiązanie. Naprawdę fajnie jest myśleć tylko o tym, *co* chcemy policzyć, a nie o tym *jak* mamy to zrobić, a w niektórych złożonych problemach takie przejście jest na wagę złota.

c.d.n.

Gość

Odnośnie tego Hornera: tak, będzie tutaj potrzebna tablica, bo przecież nie można obliczyć, ile jest a + b, jeśli nie zna się ani jednego, ani drugiego :-)

Prowadzący chcą, żebyśmy skupiali się na samych algorytmach, żeby wprowadzanie danych nam nie przeszkadzało, więc najlepiej po prostu porzygotować sobie już wypełnioną tablicę.

[link widoczny dla zalogowanych]
Wczytać, ustawić sobie jakieś n w pierwszym bloczku po starcie algorytmu, wypełnić w tablicy kolumnę 0 wartościami w wierszach <0, n> i uruchomić.
Jak zupka instant :-)

Dominik

ser w ziołach proszę.
a tak co do tego co wyżej .... eee ... masakiera ?

Gość

Dominik 35/36 twoich postow to pewnie spam Razz

no ale ktos musi spamowac Smile

Pewnie masz neostrade 1mbps Smile

neostrada tp 1 mega, szybko i niedrogo
spamujesz, blokujesz, zaśmiecasz, klniesz, żałujesz, lagujesz, rozłączasz, zatruwasz, zarażasz

Gość

ej włacha!! powiesic spamera za kuca!!!!!!!!!!!!!!!!
i bana mu bo marudzi.... BOT jeden:P

Dominik

kamel, prawie jak admin

Gość

Tu jest powazny temat o eli <lol2>. Spamowac idzcie gdzie indziej Razz

Edit: Napisalbym posta nizej ale jeszcze ja zostalbym posadzony o spam Razz

Gorush, wiesz jak sie nazywa to co robimy ... xD