zad01, Analiza, Analiza algorytmów, Analiza strukturalna danych
[ Pobierz całość w formacie PDF ]
//-->Anna Głowacka nr indeksu 77488Sformułowanie problemu:Dana jest funkcja f ze zb A w zb B, card(A)=n. Funkcja została zapisana w dwuwymiarowej tablicytab o 2 wierszach i n kolumnach, w taki sposób, że:pierwszy wiersz zawiera wszystkie el. zb. A, czyli A={tab[0,i]: -1<i<n}, a drugi wiersz tablicy tabzawiera wartości funkcji, tzn. dla wszystkich i<n, jeżeli tab[0,i]=a, to tab[1,i]=f(a). Zadanie polegana zbadaniu wł. funkcji f. Postaraj się, aby poprawne algorytmy miały możliwie małe koszty.Wariant 2Dane: liczba naturalna n i tablica tab reprezentująca funkcję f i tablica tabB zaw. el. zb. B.Polecenie :W każdym z 3 przypadków, napisz algorytm, który zbada czy funkcja f jest odwzorowaniem na zbB.Przypadek 1Zb B ma co najwyżej n el.Przypadek 2Tablica tabB zawiera elementy zbioru B uporządkowane rosnąco.Przypadek 3Wartościami funkcji f są liczby mniejsze niż k ( w tym przypadku k jest dodatkowym parametremalgorytmu)Rozwiązanie:Przypadek 1for(i=0;i<n;i++){for(j=i+1;j<n;j++){if( tabB[i]==tab[1][j]) return 0;if( tabB[i]!=tab[1][j]) return 1;}}Specyfikacja:pre={-1<i<n i n należy do N}post={result=true wttw tabB[i]=tab[1][i+1]}Opis metody rozwiązania:Szukamy takiego algorytmu, który sprawdzi czy dana funkcja jest odwzorowaniem na, czyli czyjest surjekcją. Zatem dla każdego b należącego do B istnieje a należące do A b=f(a). Jeśli warunkejest spełniony to zwracamy 0, jeśli nie to fałsz, czyli 1.Koszt danego algorytmu jest kwadratowy: O(n2)Przypadek 2 jest analogiczny do 1 (mamy już posortowane elementy ).Przypadek 3for(i=0;i<n;i++){for(j=i+1;j<n;j++){if( tabB[i]==tab[1][j]&& tab[1][j]<k) return 0;if( tabB[i]!=tab[1][j]&&tab[1][j]<k) return 1;}}Specyfikacja:pre={-1<i<n i n należy do N oraz tab[1][j]<k}post={result=true wttw tabB[i]=tab[1][i+1] i tab[1][i+1]<k}Opis metody rozwiązania:Analogiczny jak w pkt 1. Sprawdzamy też, czy wartości funkcji f są mniejsze od kKoszt algorytmu: jak w przypadku 1 [ Pobierz całość w formacie PDF ]