Zanim zajmiesz się problemami, obejrzyj wykłady 7-8 , przeczytaj i zagłębij się w „ Materiały dodatkowe trzeciego tygodnia ”. Poświęcone są algorytmom wyszukiwania (liniowym i binarnym), sortowaniu (jest ich mnóstwo!), a także pracy debuggera (możliwość współpracy z debuggerem w celu debugowania programów to niezwykle ważna umiejętność!). Jeżeli z wykładami i teorią wszystko poszło tak jak powinno, bez problemu odpowiesz na pytania testowe:
Dlaczego wyszukiwanie binarne wymaga posortowanej tablicy?
Dlaczego sortowanie bąbelkowe szacuje się na O(n2)?
Dlaczego oszacowanie sortowania przez wstawianie jest Ω(n)?
Jak działa sortowanie przez wybór? Opisz w trzech zdaniach (lub mniej).
Jaki jest górny limit (najgorszy przypadek) czasu trwania sortowania przez scalanie?
Debugger GDB umożliwia debugowanie programu. A jeśli sformułujesz bardziej szczegółowo, co dokładnie ci to pozwala?
Cele
Naucz się pracować z projektami zawierającymi wiele plików
Naucz się czytać cudzy kod źródłowy
Zrozumienie różnych algorytmów i funkcji rekurencyjnych
Większość z tych celów jest praktycznie niemożliwa do formalnej oceny. Dlatego z punktu widzenia formalnej weryfikacji problemów niewiele może wydawać się trudne. Przypominamy jednak: programowania można nauczyć się tylko poprzez ciągłą praktykę! Dlatego zachęcamy nie tylko do rozwiązania zadań, ale także do poświęcenia dodatkowego czasu i wysiłku oraz wdrożenia wszystkich algorytmów, które były omawiane w tym tygodniu. Do przodu!
Zaczynać
Przypomnij sobie, że w pierwszym i drugim tygodniu na potrzeby ćwiczeń pisałeś programy od zera i tworzyłeś własne katalogi pset1 i pset2 za pomocą polecenia mkdir . Aby wykonać zadanie praktyczne z trzeciego tygodnia, musisz pobrać dystrybucję (lub „dystrybucję”, jak ją nazywamy), którą napisaliśmy i dodać do niej własne linie kodu. Najpierw przeczytaj nasz kod i spróbuj go zrozumieć. Najważniejszą umiejętnością w tym tygodniu jest nauka czytania kodu innych osób. Zaloguj się więc do cs50.io i uruchom polecenie update50 w oknie terminala, aby upewnić się, że wersja obszaru roboczego jest aktualna. Jeżeli przypadkowo zamknąłeś okno terminala i nie możesz go znaleźć, przejdź do menu Widok i upewnij się, że opcja Konsola jest zaznaczona (sprawdź ją, jeśli nie jest). Kliknij (+), w zielonym kółku w ramce okna terminala wybierz Nowy terminal . Następnie uruchom polecenie cd ~/workspace i upewnij się, że znajdujesz się w katalogu obszaru roboczego (jest to twój katalog). Następnie uruchom polecenie:, wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip aby pobrać archiwum ZIP książki problemów do swojego obszaru roboczego (wget to polecenie pobierania systemu Linux). Jeśli wszystko jest w porządku, w wierszu zobaczysz następującą frazę: 'pset3.zip' saved Upewnij się, że naprawdę pobrałeś pset3.zip , uruchamiając polecenie:, ls a następnie uruchom unzip pset3.zip , aby rozpakować plik. Jeśli teraz ponownie uruchomisz polecenie ls , zobaczysz także katalog pset3 . Przejdź do niego, uruchamiając polecenie cd pset3 , a następnie poproś o ponowne wyświetlenie zawartości katalogu: ls zobaczysz, że w tym katalogu znajdują się dwa podkatalogi: fifteen find Już intrygujące!
Szukaj
Przejdźmy teraz do jednego z tych podkatalogów. Aby to zrobić, uruchomimy polecenie: cd ~/workspace/pset3/find Jeśli wyświetlisz na ekranie zawartość tego folderu (prawdopodobnie pamiętasz już, jak to zrobić), powinieneś zobaczyć następujący widok: helpers.c helpers.h Makefile find.c generate.c Wow, jest dużo plików. Ale nie martw się, poradzimy sobie z nimi teraz. Plik generate.c zawiera kod programu, który wykorzystuje „generator liczb pseudolosowych” (generowany przez funkcję drand48 ) do generowania dużej liczby liczb losowych (właściwie pseudolosowych, komputery nie radzą sobie z czystą losowością!) liczb. i umieść je pojedynczo w wierszu. Skompiluj program: make generate Teraz uruchom go, wydając polecenie: ./generate Program wyświetli następujący komunikat: Usage: generate n [s] Oznacza to, że program oczekuje jednego lub dwóch argumentów wiersza poleceń. Używając pierwszego, n jest obowiązkowe. Ta liczba oznacza, ile liczb pseudolosowych chcesz utworzyć. Parametr s jest opcjonalny, jak wskazano w nawiasach kwadratowych. Liczbę s można nazwać „ziarnem” generatora liczb pseudolosowych. Przez „ziarno” mamy na myśli dane wejściowe do generatora liczb pseudolosowych, które wpływają na jego wynik.Na przykład, jeśli używasz drand48, najpierw wywołując srand48 (inną funkcję, której celem jest „zaszczepienie” drand48) z argumentem, powiedzmy, 1 i następnie wywołując trzykrotnie drand48, drand48 może zwrócić 2728, następnie 29785, a następnie 54710. Jeśli zamiast poprzedniego, używając drand48, najpierw wywołasz srand48 z argumentem wynoszącym, powiedzmy, 2, a następnie użyjesz drand48 ponownie trzy razy, drand48 może zwróć 59797, następnie 10425, następnie 37569. Ale jeśli ponownie zobaczysz drand48, wywołując ponownie srand48 z argumentem 1, w wyniku kolejnych trzech wywołań drand48 otrzymasz ponownie 2728, następnie 29785, a następnie 54710! Widzisz, wszystko dzieje się po coś. Uruchom program ponownie, tym razem powiedzmy n=10, jak pokazano poniżej; zobaczysz listę 10 liczb pseudolosowych. ./generate 10 Uruchommy program po raz trzeci z tą samą wartością n; powinieneś zobaczyć kolejną listę 10 liczb. Teraz spróbuj uruchomić program z dwoma parametrami. Przyjmijmy s=0, jak pokazano poniżej. ./generate 10 0 Teraz uruchom ponownie to samo polecenie: ./generate 10 0 nie możesz się nawet kłócić: ponownie zobaczyłeś tę samą „losową” sekwencję dziesięciu cyfr. Oto, co się stanie, jeśli nie zmienisz nasion generatora liczb pseudolosowych. Przyjrzyjmy się teraz samemu program generate.c(pamiętasz jak?). Komentarze na początku tego pliku wyjaśniają ogólną funkcjonalność programu. Ale wygląda na to, że zapomnieliśmy skomentować sam kod. Przeczytaj uważnie kod i czytaj go, aż zrozumiesz znaczenie każdej linii. Następnie skomentuj dla nas ten kod, zastępując każde TODO frazą opisującą cel lub funkcjonalność odpowiedniego wiersza lub wierszy kodu. (uwaga: liczba int bez znaku jest int „bez znaku”, co oznacza, że nie może być ujemna). Aby uzyskać więcej informacji o rand lub srand, uruchom: man drand48 lub man srand48 Po skomentowaniu jak najwięcej w generate.c, przekompiluj program, aby upewnić się, że niczego nie zepsułeś: make generate Jeśli generator nie kompiluje się już, napraw to, co zrobiłeś złamał: )! Przypominamy, że polecenie make automatyzuje kompilację kodu, więc nie trzeba uruchamiać polecenia clang, ręcznie wstawiając kilka przełączników. Ale w rzeczywistości make po prostu upraszcza nasze dane wejściowe, ale w rzeczywistości kryje się za nim ten sam brzęk z potrzebnymi parametrami. Jednakże w miarę jak programy stają się coraz większe, make nie może już dowiedzieć się z kontekstu, jak skompilować kod. W takim przypadku będziesz musiał powiedzieć make jak ma skompilować programy, szczególnie jeśli wymagają one użycia różnych plików źródłowych (takich jak .c). Aby rozwiązać ten problem, użyjemy plików konfiguracyjnych (Makefiles), które mówią make dokładnie, co ma robić. Skąd polecenie make wiedziało, jak powinniśmy skompilować i wygenerować? W rzeczywistości zespół użył pliku konfiguracyjnego, który już napisaliśmy. Plik ten nazywa się Makefile i znajduje się w tym samym katalogu co generate.c . Makefile to lista reguł określających sposób tworzenia pliku generowanego z generate.c. W pliku znajdziesz w szczególności odpowiednie linie: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c Pierwsza linia mówi make, że należy utworzyć "cel" o nazwie generate poprzez wywołanie komendy z drugiej linii. Co więcej, pierwsza linia mówi make, że generator zależy od generate.c, co oznacza, że make przebuduje generator tylko przy kolejnych uruchomieniach, jeśli ten plik został zmieniony. Niezła sztuczka oszczędzająca czas, prawda? W rzeczywistości uruchom ponownie poniższe polecenie, jeśli nie zmieniłeś generate.c . make generate Zostaniesz poinformowany, że generator został już zaktualizowany do aktualnej wersji. Uwaga : Wcięcie na początku drugiej linii nie jest ciągiem spacji, lecz znakiem tabulacji. Niestety, make wymaga, aby polecenia były poprzedzone tabulatorami, więc uważaj, aby nie zmienić ich na spacje, bo w przeciwnym razie napotkasz dziwne błędy! Flaga -Werror informuje polecenie clangtraktuj ostrzeżenia (złe) jako błędy (jeszcze gorsze), więc będziesz zmuszony (w dobry, pouczający sposób!) je poprawić. Przyjrzyjmy się teraz plikowi find.c. Zauważ, że ten program oczekuje jednego argumentu wiersza poleceń: „igloo”, który musi znajdować się w „stogu siana” wartości. Następnie przejrzyj kod i skompiluj program, uruchamiając poniższe polecenie. make find make zasadniczo dał nam następujące informacje: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Uważaj! Właśnie skompilowałeś aplikację składającą się z jednego, ale dwóch plików: helpers.c i find.c . Skąd się o tym dowiedział? Aby to zrozumieć, otwórz ponownie plik Makefile i zobacz, co się tam naprawdę dzieje. Odpowiednie linie znajdują się poniżej. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Przez zależność (po dwukropku) rozumiemy to, że wszelkie zmiany w find.c , helpers.c lub helpers.h zmuszą make do odbudowania find przy następnym wywołaniu w tym celu. Teraz uruchom ten program, wykonując na przykład następujące czynności: ./find 13 Następnie zostaniesz poproszony o podanie określonego stosu (to znaczy liczb całkowitych) i podawanie mu jednej słomki na raz. Gdy znudzi Ci się wpisywanie liczb, naciśnij kombinację klawiszy Ctrl-D . Ta kombinacja wyśle do programu znak końca pliku (EOF). Symbol zmusi funkcję GetInt z biblioteki CS50 do zwrócenia stałej INT_MAX , a to z kolei find.c zmusi find do zaprzestania wpisywania „stack”. Program będzie teraz szukać igły w stogu siana, który podałeś, i ostatecznie poinformuje Cię, czy została znaleziona. Krótko mówiąc, program szuka jakiejś wartości w tablicy. Przynajmniej powinna, ale haczyk jest taki, że jeszcze niczego nie znajdzie! Ale tutaj przychodzisz na ratunek! O znaczeniu Twojej roli porozmawiamy nieco później. W rzeczywistości proces dostarczania stogu siana można zautomatyzować, przynajmniej poprzez „scalanie” danych wyjściowych generatora z funkcją find jako danych wejściowych. Na przykład poniższe polecenie przekazuje do znalezienia 1000 liczb pseudolosowych, które następnie wyszukuje wśród tych wartości 42. Zwróć ./generate 1000 | ./find 42 uwagę, że gdy generator przekaże surowe dane do znalezienia, nie zobaczysz wygenerowanej liczby, ale zobaczysz, że działa find . Alternatywnie możesz „przekierować” wyjście generatora do pliku za pomocą następującego polecenia: ./generate 1000 > numbers.txt Zawartość tego pliku można przekierować na wejście find za pomocą polecenia: ./find 42 < numbers.txt Przyjrzyjmy się jeszcze raz kodowi w pliku Makefile i zwróćmy uwagę na następujący wiersz: all: find generate Oznacza to, że możesz budować, generować i znajdować, uruchamiając następujące polecenie: make all Co więcej, polecenie znajdujące się pod tym wierszem jest równoważne poleceniu znajdującemu się nad nim, ponieważ make domyślnie tworzy pierwszy wpis w pliku Makefile. make Gdybyś tylko mógł sprowadzić wszystkie te ćwiczenia do jednego polecenia! Ale niestety! Na koniec zwróć uwagę na te ostatnie linie w pliku Makefile: clean: rm -f *.o a.out core find generate Ten wpis pozwala usunąć wszystkie pliki kończące się na .o lub nazywane core (wyjaśnimy to za chwilę!), a także po prostu uruchomić funkcję wyszukiwania lub generowania programów wykonując linię: Jeśli chcesz make clean poeksperymentować, oto coś, na co należy uważać: nie dodawaj, powiedzmy, *.c do ostatniej linii pliku Makefile! (dlaczego?) Wszystkie linie zaczynające się od znaku # są tylko komentarzami.
Zadanie 1: Szukaj
Czas na coś ciekawego! Zauważ, że find.c wywołuje search , funkcję zadeklarowaną w helpers.h . Niestety zapomnieliśmy całkowicie zaimplementować tę funkcję w helpers.c ! (Należy zaznaczyć, że zawartość plików helpers.h i helpers.c moglibyśmy umieścić w jednym pliku find.c. Czasem jednak lepiej jest rozdzielić programy na kilka plików. Szczególnie, jeśli jakieś funkcje, a raczej funkcje użytkowe mogą się przydać dla innych programów.Jak na przykład funkcje biblioteki CS50.Spójrz na helpers.c , a zobaczysz, że wyszukiwanie zawsze zwraca fałsz, niezależnie od tego, czy podana wartość jest w wartościach.Przepisz wyszukiwanie tak, aby korzystało z wyszukiwania liniowego, zwracając prawdę , jeśli wartość jest w wartościach i false, jeśli wartość nie jest w wartościach. Pamiętaj, aby natychmiast zwrócić false, jeśli n nie jest dodatnie. Kiedy będziesz gotowy do sprawdzenia poprawności, spróbuj wywołać następujące polecenie: Ponieważ jedna z wydrukowanych ./generate 1000 50 | ./find 127 liczb z generowaniem, gdy 50 zostało zaszczepionych wynosi 127, Twój kod powinien znaleźć igłę! Dla kontrastu wypróbuj to polecenie: ./generate 1000 50 | ./find 128 Ponieważ 128 nie znajduje się wśród zestawu liczb generowanych przez generowanie, gdy 50 zostało zaszczepionych, Twój kod nie musi znajdować „igły” . Uruchom inne testy, uruchamiając generowanie z niektórymi nasionami, analizując dane wyjściowe i szukając igły, która powinna znaleźć się w stogu siana. Zauważ, że main w find.c jest napisany w taki sposób, że find zwraca 0, jeśli "igła" zostanie znaleziona, w przeciwnym razie zwraca 1. Możesz sprawdzić tzw. "kod wyjściowy", który main zwraca po wykonaniu po uruchomieniu innego polecenia echo $? . Na przykład, jeśli implementacja wyszukiwania jest poprawna, po uruchomieniu ./generate 1000 50 | ./find 127 echo $? zobaczysz 0, podczas gdy 127 znajdzie się wśród 1000 liczb wyprowadzonych przez wygenerowanie z ziarnem 50, więc zapisane wyszukiwanie powinno zwrócić wartość true. W tym przypadku main (napisany przez nas) powinien zwrócić 0 (czyli wyjść). Jeśli wprowadzisz następujące dane ./generate 1000 50 | ./find 128 echo $? , zobaczysz 1, ponieważ 128 nie znajduje się wśród 1000 liczb, które zostały wygenerowane przez generator z ziarnem 50. W tym przypadku wyszukiwanie (napisane przez Ciebie) zwróci wartość false, a wartość główna (napisana przez nas) ) zwróci 1 (i następnie zakończy zadanie). Czy rozumiesz logikę? Gdy wszystko będzie gotowe do sprawdzenia za pomocą check50, uruchom następującą komendę: check50 2015.fall.pset3.find helpers.c Swoją drogą, nie powinieneś przyzwyczajać się do testowania swojego kodu za pomocą check50 przed samodzielnym przetestowaniem go. Przecież check50 tak naprawdę nie istnieje, więc uruchomienie kodu z własnymi próbkami wejściowymi i porównanie rzeczywistego wyniku z oczekiwanym wyjściem to najlepszy nawyk, jaki możesz w tym momencie wyrobić. To prawda, nie uzależniaj się! Jeśli chcesz pobawić się implementacją find za pomocą asystentów CS50, uruchom tę komendę: ~cs50/pset3/find
Sortowanie
Wyszukiwanie liniowe nie robi wielkiego wrażenia, ale już z pierwszych wykładów (a na siódmym powtórzyliśmy ten trik!) pamiętasz, że znacznie szybciej można znaleźć igłę w stogu siana. Ale najpierw musimy posortować nasz stog siana. Zauważ, że find.c wywołuje sort , funkcję zadeklarowaną w helpers.h . Niestety „zapomnieliśmy” w pełni zaimplementować tę funkcję w helpers.c ! Zajrzyj do pliku helpers.c , a zobaczysz, że sortowanie zwraca natychmiast, mimo że główna funkcja find faktycznie przekazuje mu rzeczywistą tablicę. Zapamiętaj teraz składnię deklaracji tablicy. Nie tylko określasz typ elementu tej tablicy, ale także określasz jej rozmiar w nawiasach kwadratowych. To właśnie robimy dla haystack w find.c : int haystack [MAX]; Ale podczas przechodzenia przez tablicę określasz tylko jej nazwę. Robimy to dokładnie w ten sam sposób, gdy przechodzimy przez stog siana, aby sortować w find.c : sort (haystack, size); (Zgadnij, dlaczego przekazujemy rozmiar tej tablicy osobno?) Kiedy deklarujemy funkcję, która jako argument przyjmuje tablicę jednowymiarową, nie musimy określać rozmiaru tablicy. Podobnie nie zrobiliśmy tego, deklarując sortowanie w plikach helpers.h (i helpers.c): void sort (int values [] int n); Zaimplementuj sortowanie w taki sposób, aby funkcja faktycznie sortowała tablicę liczb od małych do dużych. Musi działać w czasie równym O(n 2 ), gdzie n jest rozmiarem tablicy. Prawdopodobnie będziesz chciał zaimplementować sortowanie bąbelkowe, sortowanie przez wybór lub sortowanie przez wstawianie, o czym dowiedzieliśmy się w trzecim tygodniu. Należy jednak pamiętać: nie ma „poprawnego” sposobu implementacji tych algorytmów. Istnieje ogromna liczba odmian. Tak naprawdę zawsze możesz je ulepszyć, jeśli uznasz to za stosowne, o ile twoja implementacja będzie zbieżna z O(n2 ) . Eksperymenty zostawmy jednak ciału funkcji i aby uprościć testowanie, nie zmieniajmy naszej deklaracji sortowania. Powinno to wyglądać tak: void sort (int values [] int n); Ponieważ funkcja zwraca wartość void, nie powinna zwracać posortowanej tablicy. Zamiast tego musi „destrukcyjnie” posortować rzeczywistą tablicę, przez którą „przebiega”, przesuwając jej elementy. W czwartym tygodniu omówimy, że tablice są przekazywane przez referencję, a nie przez wartość. Oznacza to, że sort nie otrzyma kopii tablicy, ale samą oryginalną tablicę. Chociaż nie możesz zmienić naszej deklaracji sortowania, zawsze możesz zdefiniować własną funkcję w helpers.c, którą można następnie wywołać z sortowania. Zdecyduj sam, jak najlepiej przetestować implementację sortowania. Nie zapominaj, że printf i GDB Ci pomogą! I nie zapominaj, że możesz w kółko tworzyć tę samą sekwencję liczb pseudolosowych, jawnie określając wartości początkowe dla generowania.
Wyszukiwanie binarne, porady
Pierwszą rzeczą, którą musisz zrozumieć na temat funkcji find , jest to, że mamy już napisany kod (dystrybucja). Po prostu uzupełniamy pewne luki w istniejącym kodzie. Program find.c żąda wprowadzenia liczb (czyli wypełnienia „stosu”), a następnie na żądanie użytkownika wyszukuje w nim „igłę”, korzystając z funkcji sortowania i wyszukiwania zdefiniowanych w helpers.c . Zatem find jest już napisany, musimy napisać pomocniki . Oto co musimy zrobić:
Zaimplementuj wyszukiwanie. Funkcja ta powinna zwrócić wartość true, jeśli wartość zostanie znaleziona na stosie, lub false, jeśli jej tam nie ma.
Zaimplementuj sortowanie, funkcję sortującą tablicę wartości.
Początkowo przeszukiwanie realizowano jako liniowe. Ale możesz zrobić lepiej. Algorytm wyszukiwania liniowego działa w czasie O(n) . Twoim zadaniem jest napisanie algorytmu wyszukiwania binarnego. Czas jego wykonania wynosi O(log n) . Jednak jego problem polega na tym, że jako dane wejściowe potrzebuje posortowanych danych, w przeciwnym razie nie będzie działać. Pamiętacie przykład podartej książki i zapewne wiecie, dlaczego tak się dzieje. Jeśli po binarnym przeszukiwaniu elementów i nie ma ich więcej (to znaczy, że w tym „stosie” po prostu nie ma „igły”), funkcja powinna zwrócić wartość false. Wyszukiwanie binarne można realizować iteracyjnie lub rekurencyjnie (David Malan mówił o rekurencji w ósmym wykładzie).
Następnie uruchom polecenie 
GO TO FULL VERSION