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+...+xn 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=2k. Zastosuj regułę przeszukiwania binarnego ciągu. Zestaw II. 1. Znalezć minimalny i maksymalny element tablicy. Zastosować technikę dziel i rządz . 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 e" 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) + n3 7. Uporządkuj pod względem tempa wzrostu następujące funkcje: lg n n lg n n lg n n ; ; 2 n ; n ; lg n ; n / lg n ; ; ; ; (n / 2 ) (3 / 2 ) 2 2 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 wskaznik 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ł.