Algorytmy Nauka

Question

Witam , mam pytanie w jaki sposób uczyć się argorytmów i ich używania , czy przerabiać jakaś książkę czy kursy osobno czy po prostu robić zadania i uczyć się nowych argorytmów przez pisanie różnych programów w c++?

Answer 1

Nie ma sensu kupować książek, algorytmy są dostępne w internecie dla różnych języków. Najlepiej szukaj algorytmu z wyjaśnieniem działania i analizuj. Potem spróbuj napisać go sam.

Answer 2

Tak jak napisał @mtk3d, w internecie jest wiele przykładów algorytmów, ich rozwiązania, wskazówki, instrukcje, dokładne analizy. Oczywiście, jeżeli wolisz naukę z książki, to również są ciekawe pozycje. W internecie jednak, wiadomo, masz to co chcesz i na wyciągnięcie ręki. Przede wszystkim ĆWICZYĆ :D

Pozdrawiam.

Answer 3

Cormen Wprowadzenie do algorytmów to dość dobry pomysł Podaje algorytmy stosunkowo łatwe do zapisania w języku programowania Z Niklausem Wirthem i jego książką Algorytmy+struktury danych=programy jest już gorzej ale np temat o sortowaniu uzupełniony jest o sortowanie plików Wydaje mi się że książka Diksa Ryttera Banachowskiego prezentuje się najgorzej

 

Sortowanie przez scalanie od Cormena

Merge(A,p,q,r)
    n1:=q-p+1
    n2:=r-q
    for k:=p to q do 
        B[k-p+1]:=A[k]
    for k:=q+1 to r do
        C[k-q]:=A[k]
    B[n1+1]:=infty
    C[n2+1]:=infty
    i:=1
    j:=1
    for k:=p to r do 
        if B[i]<=C[j] then 
            A[k]:=B[i];
             i:=i+1;
        else 
                A[k]:=C[j];
                 j:=j+1;

 MergeSort(A,p,r)
      if(p<r) then
         q:=floor((p+r)/2)
         MergeSort(A,p,q)
         MergeSort(A,q+1,r)
         Merge(A,p,q,r)


Jako zadanie spróbuj usunąć wartowników i połączyć dwie tablice pomocnicze w jedną
Usunięcie rekurencji wymaga nieco innego podejścia ale 
funkcję scalającą możesz wykorzystać bez zmian

Sortowanie przez kopcowanie od Cormena 

Heapify(A,i,heapsize)
     l:=2*i
     r:=2*i+1
     if (l<=heapsize)and(A[l]>A[i]) then
          largest:=l
     else largest:=i;
     if (r<=heapsize)and(A[r]>A[largest]) then
          largest:=r
    if(largest<>i) then
      zamien(A[i],A[largest]);
      Heapify(A,largest,heapsize)
 
BuildHeap(A,length)
     heapsize:=length;
     for i:=floor(length/2) downto 1 do 
           Heapify(A,i,heapsize)


HeapSort(A,length)
     BuildHeap(A,length)
     heapsize:=length
     for i:=length downto 2 do
         zamien(A[1],A[i])
         heapsize:=heapsize-1
         Heapify(A,1,heapsize)

Jako zadanie spróbuj usunąć rekurencję z procedury przywracającej własność kopca


Teraz sortowanie u Diksa Ryttera Banachowskiego 

Scalanie wielofazowe z 4 plikami {Tak je nazwali}

Załóżmy że bloki zostały rozłożone na pliki P0 i P1.
Pliki P2 i P3 są początkowo puste.

i1:=0; i2:=1; {numery plików wejściowych, tzn. otwartych do czytania}
j1:=2; j2:=3; {numery plików wyjściowych, tzn. otwartych do pisania}

dopóki jest więcej niż jeden blok wykonuj
a)	scal pierwszy blok na Pi1 z pierwszym blokiem na Pi2  i powstający blok zapisz na Pj1
b)	scal następny blok na Pi1 z następnym blokiem na Pi2  i powstający blok zapisz na Pj2
c)	powtarzaj kroki a) i b) (kładąc powstające bloki na przemian na pliki Pj1 i Pj2) aż zostanie osiągnięty koniec plików Pi1 i Pi2
d)	przewiń wszystkie pliki do początku; dodaj liczbę 2 mod 4 do		i1, i2, j1, j2, odwracając w ten sposób rolę plików wejściowych i wyjściowych

Blok to posortowany ciąg elementów inaczej zwany serią

Jak ci się podobają te przykłady algorytmów  ?
Kto według ciebie przedstawia je w sposób bardziej czytelny ?

Answer 4

Z książek - David Harel "Rzecz o istocie informatyki. Algorytmika".