Mam z informatyki pisać sprawdzian z turbopascala i mam trzy tematy do wyboru: rekurencję, sortowanie i macierze. Nic z rzadnego nie kapuję. Powiedzcie mi, który jest najprostszy…
No jeżeli nie jesteś orłem w programowaniu to odradzam rekurencję, bo się można czasem w niej pogubić
Macierze… no cóż zależy co z nimi bo nie wiem, czy chodzi o jakieś proste działania na tablicach czy wkraczamy w algebrę
Sortowanie -> mnóstwo materiałów w sieci na ten temat
Jeżeli chodzi o proste działania na tablicach to bym wybrał właśnie to, ale jezeli algebra (czyli macierze odwrotne, mnożenie itp.) to sortowanie
Dodawanie macierzy to też algebra (i pod tym terminem przeważnie należy szukać - czy to w sieci czy w książkach). Operacje na macierzach to proste algorytmy opracowane dawno temu, które się obecnie jedynie implementuje, nic super-złożonego, ale pewnych rzeczy trzeba się wyuczyć. Rekurencja jest moim zdaniem nejprostszym zagadnieniem, ale wymaga odrobiny wyobraźni. Zakładając, że to liceum lub gimnazjum, nie spodziewałbym się czegoś więcej niż proste operacje na ciągach czy np. ciągi fibonacciego. Sortowanie z kolei to temat dosyć rozległy a algorytmów dużo, ale na poziomie LO będzie to góra 5-6 algorytmów (z których na tym etapie najtrudniejszy chyba będzie quick sort). Zależy jak leży - ja bym wziął rekurencję.
coś znalazłem o rekurencji :
http://pascal.lo2.opole.pl/rekurencja.html
sortowanie :
http://pascal.lo2.opole.pl/sortowanie_babelkowe.html
http://pascal.lo2.opole.pl/sortowanie_przez_wybor.html
http://pascal.lo2.opole.pl/sortowanie_p … ianie.html
http://pascal.lo2.opole.pl/sortowanie_p … lanie.html
Na tej stronce http://pascal.lo2.opole.pl/ jest to fajnie wytłumaczone, a na tej masz gotowce http://4programmers.net/article.php?cat=4
Rekurencja to coś co jest wtedy gdy funkcja lub procedura wywołuje samą siebie określoną ilośc razy zależną od podanego parametru
np. rekurencyjne liczenie silni
Procedure silniarek(liczba : integer)
Begin
if (liczba=0) or (liczba=1) then silniarek:=1
else
silniarek:=liczba*silniarek(liczba-1)
end;
end
Procedura oblicza silnie z podanej liczby rekurencyjnie
np silnia(3)=1*2*3=6
silnia z 0 albo z 1 wynosi 1 więc dla takich parametrów procedura zwróci 1
,co się stanie,gdy parametr jest większy od i np silnia z 3 ?
aby obliczyc silnie z 3 musimy znac silnie z 2,dla silni z 2 silnie z 1
procedura musi stworzyc swoje kopie dla silni(2) i silni(1),każda o poziom w dół,gdy będzie znany ostateczny wynik silni w z ostatniej kopii,zostanie przekazany na górę do oryginalnej procedury,tak działa rekurencja
Zaletą rekurencji jest krótki zapis - wszystko odbywa się w jednej linii
wadą zagmatfanie - nie widac działania od razu czytając program i zajętośc pamięci - kompilator przechowując wyniki operuje na tzw stosie,gdzie odkłada wyniki poszczególnych kopii funkcji,procedur,stos może się przepełnic - brak pamięci dla następnego wyniku
Sortowanie
Sortowanie przez wstawianie
jeśli np. poprzedni element jest mniejszy od n astępnego to je zamień i wstawe w odpowiedzie miejsce
złożonośc wykładnicza n kwadrat,co eliminuje ten algorytm z poważnych zastosowań
sortowanie bąbelkowe - nazwa pochodzi od bąbelków gazu ulatującego w górę,mniejsze elementy - liczby,idą na górę,większe,cięższe idą po kolei na dół
złożonośc n kwadrat
Quick Sort - sortowanie szybkie - polega na podziale tablicy na połowę i układaniu elementów mniejsze od liczby na lewo,większe na prawo,potem
to samo robi się w podtablicach elementów większych,dzielenie podtablicy na pół i znowu układanie
złożonośc n*log(n)
Macierze - działania na dwuwymiarowych tablicach
Dzięki wielkie za pomoc!Naprawdę, w tym temacie jestem całkiem zielona… Zacznę więc od rekurencji. Nie wiem tylko gdzie mogłabym znaleźć jeszcze jakieś przykłady programów rekurencyjnych oprócz silni i ciągu Fibonacciego… :?