Harvard CS50: Zadania w tygodniu 3 (wykłady 7 i 8), część 2

Harvard Programming Podstawy Wykłady CS50 Dodatkowe materiały: notacja asymptotyczna, algorytmy sortowania i wyszukiwania Zadania w tygodniu 3, część 1. Sortowanie i wyszukiwanie.

Gra się rozpoczyna!

Jest czas na zabawę! Większość ludzi zna grę logiczną „Tag”. Aby to sformalizować, „Tag” to dwuwymiarowe pole 4x4, w tym polu nie jest 16, ale 15 kwadratów, to znaczy jedno miejsce pozostaje puste. Każde z pól jest ponumerowane i może poruszać się w obrębie pola w poziomie lub w pionie (jeśli oczywiście jest na to miejsce). Celem jest ułożenie liczb w kolejności od 1 do 15, od lewej do prawej, od góry do dołu. Wtedy pusta przestrzeń będzie w prawym dolnym rogu. Ruch dowolnego kafelka (lub kilku) jest „krokiem” w tej przestrzeni gry. Kombinacja pokazana na powyższym obrazku jest już ułożona w stos, ale pamiętaj, że w puste miejsce można zepchnąć 12 lub 15 płytek. Zasady stanowią, że płytki nie można przesuwać po przekątnej ani usuwać z planszy. Konfiguracji na rozpoczęcie gry jest właściwie sporo (można policzyć ile dokładnie), ale dla uproszczenia ułóżmy kafelki w kolejności od największej do najmniejszej i zostawmy puste miejsce w prawym dolnym rogu planszy . Jedyną rzeczą jest zamieńmy 1 i 2, aby zagadka była możliwa do rozwiązania. Teraz przejdź do katalogu ~/ swojego środowiska roboczego , następnie /pset3/fifteen i otwórz piętnaście.c . Zawiera kod silnika gry. Zadanie polega na dodaniu kodu do gry. Ale najpierw skompilujmy nasz „silnik” (prawdopodobnie już wiesz, jak to zrobić). Pomimo tego, że gra nie jest jeszcze ukończona, możesz uruchomić aplikację. Wygodniej będzie uruchomić go w większym niż zwykle oknie terminala, które otworzymy klikając na zielony plus (+) obok jednej z zakładek z kodem i wybierając Nowy Terminal . Możesz też otworzyć okno terminala na pełnym ekranie, klikając ikonę Maksymalizuj w prawym górnym rogu konsoli. Widzisz, że pewne rzeczy jakoś działają. Ale tak naprawdę większość gry nie została jeszcze napisana. A tutaj - przygotuj się - jest twoje wyjście!

Badanie

Przestudiuj kod i komentarze piętnastki.c , a następnie odpowiedz na poniższe pytania:

1. Oprócz planszy 4x4, jaki rozmiar pola pozwala na nasz silnik?
2. Jaką strukturą danych jest pole gry?
3. Jaka funkcja jest wywoływana w celu powitania gracza na początku gry?
4. Jakie funkcje musisz wdrożyć?
5. Uwaga: Jeśli chcesz, aby automatyczne sprawdzanie informowało Cię, czy odpowiedziałeś poprawnie na pytania, obok pliku piętnaście.c znajdź plik piętnaście.txt i zapisz w nim odpowiedzi na te pytania.

Realizacja

Cóż, zacznijmy wdrażać grę. Pamiętaj, że działamy małymi krokami, nie próbuj robić wszystkiego na raz. Zamiast tego wdrażajmy funkcje pojedynczo i upewnijmy się, że działają, zanim przejdziemy dalej. W szczególności sugerujemy implementację funkcji gry w następującej kolejności: init (inicjalizacja), remis (rysowanie), ruch (zrób krok), wygrana (wygrana). Decyzje projektowe (takie jak ilość miejsca pomiędzy naszymi kafelkami z numerami) należą do Ciebie. Pole gry powinno wyglądać mniej więcej tak: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Jeszcze raz zwróćmy uwagę, że w pozycji wyjściowej cyfry 1 i 2 znajdują się w odwrotnej kolejności (dotyczy to klasycznego pola 4x4, jeśli liczba płytek jest nieparzysta). Jeśli liczba płytek jest parzysta, a pole wynosi 3x3, nie ma potrzeby zamieniania dwóch „najniższych” płytek. 8 7 6 5 4 3 2 1 _ Aby przetestować implementację „Tag”, musisz spróbować je odtworzyć (pamiętaj, że możesz wyjść z programu przed jego naturalnym zakończeniem, naciskając kombinację klawiszy crtl+c). Upewnij się, że program będzie działał w przypadku wprowadzenia nieprawidłowych liczb. I pamiętaj, że tak jak zautomatyzowałeś wprowadzanie danych do find, możesz zautomatyzować „przejście” gry. Tak naprawdę w folderze ~cs50/pset3 znajdują się pliki 3x3.txt i 4x4.txt , które zawierają wszystkie sekwencje kroków prowadzących do wygranej na polach 3x3 i 4x4. Aby przetestować program np. na pierwszym z plików, uruchom komendę: ./fifteen 3 < ~cs50/pset3/3x3.txt Ustaw argument potrzebny do przyspieszenia animacji. I ogólnie, jeśli chcesz, zawsze możesz zmienić grę. Aby dobrze się bawić „sekwencjami ucieczki ANSI”, w tym kolorem. Przyjrzyj się naszej implementacji Clear i odwiedź http://isthe.com/chongo/tech/comp/ansi_escapes.html , aby nauczyć się nowych sztuczek. Jeśli chcesz, napisz własne funkcje lub zmień prototypy funkcji, które napisaliśmy. Jedynym ograniczeniem jest to, że nie zmieniasz logiki funkcji głównej, w przeciwnym razie nie będziemy mogli zastosować do niej automatycznych testów, aby potwierdzić, że Twój program działa poprawnie. W szczególności main musi zwrócić 0 wtedy i tylko wtedy, gdy użytkownik rozwiązał zagadkę. Dla wszystkich opcji błędów muszą zostać zwrócone wartości niezerowe. Jeśli wystąpią jakieś błędy napisz do nas. Cóż, jeśli chcesz pobawić się implementacją aplikacji przygotowanej przez asystentów CS50, uruchom następującą komendę: ~cs50/pset3/fifteen Jeśli interesuje Cię fajniejsza implementacja, z automatycznym rozwiązywaniem łamigłówek, sprawdź wersję programu „Hacker”: ~cs50/hacker3/fifteen Zamiast wpisywać liczbę w oknie gry, wpisz słowo BÓG. Świetnie, prawda? Jeśli chcesz oficjalnie sprawdzić poprawność swojego programu za pomocą check50, pamiętaj, że check50 zakłada, że ​​puste miejsce pola gry jest wypełnione 0; jeżeli wybrałeś inną wartość, zamień ją na zero dla poprawnej weryfikacji. Ponadto check50 zakłada, że ​​indeksujesz pola tablicy w kolejności [wiersz] [kolumna], a nie tablica [kolumna] [wiersz]. check50 2015.fall.pset3.fifteen fifteen.c

Dowiedz się więcej o implementacji funkcji gry Piętnaście

• init (inicjalizacja)
• rysować
• poruszyć się (zrobić krok)
• wygrał (wygrał)

w tym

W tej funkcji wprowadzamy pole gry. Aby to zrobić, używamy dwuwymiarowej tablicy liczb całkowitych. Wymiar tablicy to MAX x MAX, gdzie MAX jest stałą wskazującą maksymalną liczbę płytek, które mieszczą się w wierszu lub kolumnie pola. Musimy zatem zdefiniować zmienną int board[MAX][MAX] Należy jednak pamiętać, że o wielkości pola gry decyduje użytkownik. Musimy zatem zdefiniować zmienną, która wskazywałaby rozmiar tablicy, jaki użytkownik musi wprowadzić. To jest int d . gdzie d jest wymiarem płyty, d <= MAX. Jednak w C nie można zmienić rozmiaru tablicy, więc musisz zadowolić się maksymalnym rozmiarem. W init musisz umieścić wartości na tablicy. Przeczytaj więcej o tablicach dwuwymiarowych, jeśli jeszcze z nimi nie pracowałeś. Krótko mówiąc, mają dwa indeksy, pierwszy oznacza numer wiersza, drugi numer kolumny. W przypadku naszego problemu zaczynamy od maksymalnej liczby i kończymy w przypadku d = 3 („ósemki”) jedynką i pustym rogiem. Jeśli nadal mamy „Tag”, zamieniamy 1 i 2. Co zrobić z pustą przestrzenią? Nasza tablica składa się z liczb całkowitych, więc pustka musi zostać wypełniona jakąś liczbą całkowitą. Dlatego musisz wybrać liczbę całkowitą, aby zainicjować pusty kafelek (lub, w przypadku gry fizycznej, brak kafelka). Pętle można wykorzystać do inicjalizacji planszy i wypełnienia jej początkowym zestawem płytek. Przechodzimy przez indeksy i oraz j, gdzie tablica[i][j] to kafelek znajdujący się w wierszu o numerze i i w kolumnie o numerze j. Wypełniamy planszę w kolejności malejącej. Jeśli liczba płytek (bez pustych) jest nieparzysta, zamień 1 z 2.

rysować

Ta funkcja powinna wydrukować aktualny stan pola gry. Pamiętajcie, że możemy mieć wartości jedno lub dwucyfrowe, dlatego dla pięknego formatowania po liczbach 1-9 funkcja powinna wypisać spację ( #s ). Można to zrobić za pomocą symbolu zastępczego %2d . printf (“%2d”, board[i][j]); Nie zapomnij także o pustej komórce. Wybierz znak, który będzie go reprezentował (w naszym przykładzie jest to podkreślenie). Funkcja rysowania powinna narysować ten znak, gdy tylko trafisz na pustą komórkę. Zatem nasza pętla wyglądałaby mniej więcej tak: for каждой строки for каждого element строки print oznaczający и пробел print новую строку Pamiętaj, że kolejność, w jakiej funkcja rysowania rysuje kafelki na ekranie, powinna odzwierciedlać kolejność, w jakiej znajdują się one w tablicy zdefiniowanej w funkcji init .

przenosić

Po zainicjowaniu pola gry i narysowaniu początkowych pozycji płytek należy pozwolić użytkownikowi na edycję położenia płytek, czyli wykonywanie ruchów. Zatem w Fifteen.c program pobiera dane wyjściowe od użytkownika, buduje planszę, a następnie wywołuje funkcję przenoszenia i mówi jej, którą płytkę chce przesunąć. Bądź ostrożny: stosujesz funkcję konkretnie do liczby na kafelku, a nie do jej pozycji na planszy (w tablicy). Musisz więc znaleźć rzeczywistą pozycję płytki. Ponadto należy zezwalać użytkownikowi na przesuwanie kafelka tylko wtedy, gdy jest to możliwe. Na powyższym obrazku możemy przesuwać tylko płytki nr 2, 5 i 8. Jak to ustalić? Według wartości pustej płytki. Zatem funkcja przenoszenia działa mniej więcej tak:

• Akceptuje numer kafelka, który użytkownik chce przenieść
• Szuka pozycji w szyku (na boisku) tego kafelka
• Zapamiętuje położenie pustej płytki
• Jeśli pusty kafelek sąsiaduje z tym, który użytkownik chce przesunąć, są one zamieniane w szyku.

wygrał

Ta funkcja sprawdza, czy gra się zakończyła po każdym kroku użytkownika. Zwraca wartość true, jeśli kafelki są we właściwej kolejności (w tym pozycja pustego kafelka w prawym dolnym rogu). W takim przypadku program można zakończyć. Jeśli kafelki nadal są porozrzucane, funkcja zwraca wartość false i przekazuje stery funkcji przenoszenia . Jak zorganizować kontrolę? Podobnie jak w przypadku inicjowania i rysowania planszy - przy użyciu dwóch zagnieżdżonych pętli for. Na przykład możesz ustawić warunek, że każda kolejna liczba w tablicy musi być większa od poprzedniej. Zwróć uwagę, jaka wartość jest zapisana w pustym kafelku. Lub inaczej - użyj licznika, aby upewnić się, że wszystkie płytki są na swoim miejscu, jeśli dasz radę i napisz formułę, aby je uzyskać. Życzymy powodzenia w eksperymentach!

Jak zweryfikować kod i zdobyć oceny

Uwaga! Jeśli ważne jest dla Ciebie sprawdzenie tylko poprawności zadań to użyj cs50check. Jeżeli chcesz otrzymywać oceny na platformie edx postępuj zgodnie z procedurą opisaną poniżej. Należy pamiętać, że ta procedura wykorzystuje ten sam program cs50check do sprawdzania zadań. Jedyną różnicą jest to, że zapamiętuje wyniki i oblicza ogólny wynik.

1. Zaloguj się do CS50 IDE
2. W pobliżu lewego górnego rogu CS50 IDE , gdzie znajduje się jego przeglądarka plików (nie w oknie terminala), kliknij prawym przyciskiem myszy katalog pset3 i kliknij Pobierz . Powinieneś zobaczyć, że przeglądarka pobrała archiwum pset3.tar.gz .
3. W osobnym oknie lub zakładce zaloguj się do CS50 Submit
4. Kliknij ikonę Prześlij w lewym górnym rogu ekranu
5. Na liście folderów po lewej stronie kliknij katalog Problem Set 3 , a następnie kliknij przycisk Prześlij nowe zgłoszenie. To jest po prawej.
6. Na wyświetlonym ekranie kliknij przycisk Dodaj pliki .... Otworzy się okno wyboru plików z komputera.
7. Przejdź do folderu, w którym zapisałeś plik pset3.tar.gz. Najprawdopodobniej znajduje się on w folderze Pobrane lub w dowolnym miejscu, w którym przeglądarka domyślnie umieszcza pliki. Gdy znajdziesz pset3.tar.gz , kliknij go raz, aby go wybrać, a następnie kliknij Otwórz .
8. Kliknij Rozpocznij przesyłanie . Twoje pliki zostaną przesłane na serwery CS50 .
9. Na wyświetlonym ekranie powinno pojawić się okno Nie wybrano pliku . Jeśli przesuniesz kursor myszy w lewo, zobaczysz listę pobranych plików. Aby potwierdzić, kliknij każdy z nich. Jeśli nie jesteś czegoś pewien, możesz ponownie przesłać pliki, powtarzając te same kroki. Możesz to zrobić tyle razy, ile chcesz, do końca 2016 roku.