zad03, Analiza, Analiza algorytmów, Analiza strukturalna danych
[ Pobierz całość w formacie PDF ]
//-->Zadanie 1Dany jest ciąg n-elementowy e[1],....,e[n] liczb rzeczywistych. Zaproponuj algorytm wyznaczającyspójny podciąg (segment), którego suma elementów jest największa.Wymagania:• W tekście rozwiązania musi się znaleźć nazwisko autora i jego numer indeksu oraz treśćrozwiązywanego zadania.• Rozwiązanie powinno zawierać• specyfikację zadania,• opis słowny metody rozwiązania,• algorytm rozwiązujący (ew. jego implementację),• analizę kosztu i• analizę poprawności względem podanej specyfikacji.• Rozwiązanie zadania musi zostać dostarczone w formie pliku .pdf i umieszczone w systemieedukacyjnym UKSW przed ustalonym terminem.Rozwiązanie:• Specyfikacja zadania:Rozważamy wyznaczenie spójnego podciagu o największej sumie dla ciągu liczb rzeczywistych.Naturanym warunkiem będzie założenie, że ciąg jest skończony i niepusty. Wartość największejobliczanej sumy podciągu musi być większa od 0.pre={ n>0, e[1]=e1,...,e[n]=en��������>0 else��������+1>0}post={wynik=max{(����+����1),...,(��������−1+��������)}}• Opis słowny metody rozwiązania:Niech dany będzie ciąg liczb rzeczywistych����1. . . ��������. Będziemy w tym ciągu poszukiwać spójnegopodciągu (czyli jednokawałkowego fragmentu), który ma największą możliwą sumę. Przykładowo,dla ciągu -6, 4, -1, 4, -2 szukanym podciągiem jest 4, -1, 4.Najszybszym rozwiązaniem danego problemu będzie przejrzenie naszego ciągu. Wystarczy, żezrobimy to tylko jeden raz, ale dokładnie. W tym celu musimy dla każdego elementu (z ciągu)obliczyć największą możliwą do uzyskania sumę podciągu, który kończy się w tym elemencie. Jeśliuzyskamy tę wartość ( oznaczoną jako��������) dla wyrazu��������, to jego obliczenie dla kolejnego wyrazu��������+1będzie polegało na wzięciu��������+��������+1, jeżeli��������>0, zaś��������+1w przeciwnym przypadku. Dzieje siętak, ponieważ dla��������≤ 0nieopłaca się nam przedłużać ciągu w lewo, ponieważ tylko możemyzmniejszyć jego wartość.Należy jeszcze dodać, że nie musimy przechowywać wszystkich wartości��������, a wystarczy, że wkażdym kroku wykorzystamy poprzednią wartość.• Algorytm rozwiązujący:int main(){int i;int w=0;wynik=0; /*suma pustego podciągu*/scanf(''%d'',&n);for( i=0; i<n;i ++){if(w>0)w+=e[i]; /* możemy wziąć poprzednie w*/elsew=e[i] /* nie możemy wziąć poprzedniego w*/if(w>wynik)wynik=w;}printf(''%dn'', wynik);return 0;}• Analiza kosztu:W celu obliczenia wartości��������musimy wykonać stałą liczbę operacji dla każdego elementu z ciągu.Zatem złożoność czasowa, będzie wyznaczona przez policzenie maksimum z watości��������, co dajenam O(n).Koszt pesymistyczny będzie zatem liniowy, gdyż dla wczytania całego ciągu będziemymusieli wykonać O(n) operacji. Koszt średni będzie także liniowy.• Analiza poprawności względem podanej specyfikacji:Dane rozwiązanie jest poprawne ze względu na swoją specyfikację, ponieważ warunekpoczątkowy i końcowy jest spełniony. Zadanie wymagało zauważenia, że można wyznaczyćczęściowy wynik dla ciągu, jeśli znamy go dla krótszego o jeden wyraz ciągu.W warunku początkowym zakładamy, że ciąg liczb jest skończony i niepusty, co pozwalanam wyznaczyć sumę najdłuższego wspólnego podciągu. Zakładamy również, że uzyskanasuma dla konkretnego elementu, musi być większa od zera, w przeciwnym wypadku danyelement musi być większy od zera (dokładne wyjaśnienie pojawiło się w opisie słownymmetody rozwiązania).Należy także, dodać, że zmienna i kontroluje pętle przyjmuje jako swoje wartości kolejneliczby naturalne, parametr n jest także liczbą naturalną. Zatem po skończonej liczbie krokówprogram kończy swoje działanie (własność stopu) i wychodzimy z pętli. W konsekwencjiwydrukowany zostaje wynik.Warunek końcowy zakłada, że otrzymanym rozwiązaniem będzie największa sumaspośród wszystkich wyznaczonych sum. [ Pobierz całość w formacie PDF ]