Algorytmy i struktury zadań

Zestaw I.

1. Dokonać analizy poprawności algorytmu Euklidesa wyznaczania
WD (
ajwiększego Wspólnego

Dzielnika) dwóch liczb naturalnych. Idea algorytmu oparta jest na dzieleniu z resztą większej z
liczb przez mniejszą. Za liczbę większą przyjmuje się liczbę mniejszą w dzieleniu z poprzedniej
iteracji. Do zbudowania niezmienników iteracji skorzystaj z następujących własności:
WD(a,b)=

WD(a-b,b);
WD(a,b)=
WD(b,a);
WD(a,a)=a.

2. Wyznaczyć wartość symbolu Newtona za pomocą algorytmu iteracyjnego. Dokonaj analizy

złożoności obliczeniowej algorytmu.

3. Zbudować algorytmy do sortowania elementów tablicy. Rozważyć sortowanie: „przez wybór”

(Selection_Sort), poprzez wstawianie (Insertion_Sort) i bąbelkowe (Bubble_Sort). Dokonać
analizy złożoności obliczeniowej (czasowej i pamięciowej).

4. Obliczyć wartość jednomianu p(x) = 1+x+...+x+...+x

n

w zadanym punkcie x=y. Zastosować

schemat Hornera.

5. Dokonać konwersji dziesiętnej, nieujemnej liczby całkowitej N na liczbę w systemie o podstawie

B. Wyprowadzić wartość liczby w nowym systemie.

6. Zbudować stabilny algorytm sortowania „przez wybór” oraz algorytm sortowania „bąbelkowego”

o optymistycznej złożoności obliczeniowej.

7. Sprawdzić czy zadana liczba x należy do posortowanego ciągu n liczb, n=2

k

. Zastosuj regułę

przeszukiwania binarnego ciągu.

Zestaw II.

1. Znaleźć minimalny i maksymalny element tablicy. Zastosować technikę „dziel i rządź”. Dokonać

analizy czasowej złożoności obliczeniowej algorytmu.

2. Obliczyć wartość n-tego wyrazu ciągu Fibonacciego metodą programowania dynamicznego.

Dokonać porównania z algorytmem rekurencyjnym. Wyznacz złożoności obliczeniowe
algorytmów.

3. Zbudować rekurencyjny algorytm sortowania „przez wybór”.

4. Wypełnić „po spirali” tablicę wartościami tworzącymi ciąg arytmetyczny o zadanym wyrazie

początkowym i zadanej różnicy ciągu. Rozpatrzyć przypadek wypełnienia zaczynając od
dowolnego elementu skrajnego oraz środkowego. Zbudować algorytm iteracyjny i rekurencyjny.

5. Metodą „przewidywania rozwiązania” rozwiązać równania rekurencyjne. Za pomocą indukcji

udowodnić ich poprawność:

T(n) = 2T(n-1) + 1

dla n ≥ 2,

T(1) = 2

T(n) = 2T(n-1) + n

dla n > 1,

T(1) = 1

6. Rozwiązać równania rekurencyjne zakładając, że T(1)=1, zaś dla n>1:

T(n) = 2T(n/2) + (n-1)
T(n) = nT(n-1) + n!
T(n) = 8T(n/2) + n

3

7. Uporządkuj pod względem tempa wzrostu następujące funkcje:

;

;

;

;

lg

/

;

lg

;

;

2

;

;

lg

lg

lg

)

2

/

3

(

)

2

/

(

2

2

n

n

n

n

n

n

n

n

n

n

n

n

n

Zestaw III.

1. Wstawić na n-tą pozycję listy nowy element. Założyć można, że lista posiada co najmniej

n elementów.

2. Pojedyncza, niepusta lista jednokierunkowa zakończona jest cyklem. Wyznaczyć ilość

elementów w cyklu.

3. Wyznaczyć liczbę elementów listy cyklicznej, mając wskaźnik do jednego z elementów

listy.

4. Dwie pojedyncze listy jednokierunkowe zawierają niepowtarzające się liczby naturalne

posortowane rosnąco. Przekształcić te listy w jedną listę, której elementy są posortowane
rosnąco. Listy wejściowe są usuwane z pamięci.

5. W liście jednokierunkowej usunąć powtarzające się elementy. Założyć można, ze lista jest

niepusta.

6. W liście dwukierunkowej zwolnić każdy parzysty węzeł.