Treści zawarte w tym e‑materiale wykraczają poza poziom edukacyjny. Jeśli jednak jesteś zainteresowany tematyką rekurencji oraz wykorzystaniem jej do obliczania największego wspólnego dzielnika (NWD), to zachęcamy Cię do zapoznania się z poniższym e‑materiałem.
Ten materiał wymaga znajomości środowiska Scratch. Potrzebne informacje na ten temat znajdziesz w materiale Wprowadzenie do środowiska ScratchP9AYGQXHJWprowadzenie do środowiska Scratch.
Pewnie mieliście okazję zagrać w grę, w której bohater musiał pokonać labirynt. Być może nawet sami tworzyliście grę, w której gracze sterowali bohaterem, prowadząc go przez labirynt. Teraz zadanie dla duszka będzie trudniejsze. Po kliknięciu zielonej flagi, duszek będzie musiał samodzielnie znaleźć drogę na wyjście z labiryntu. Będzie realizował algorytm, który poprowadzi go do wyjścia przez labirynt. Przykładowe działanie aplikacji można zobaczyć na poniższym filmie.
RcYgjpKWcXFJN
Film pokazujący działający algorytm. Na scenie widoczna jest plansza. Jest ona labiryntem z zielonymi polami będącymi ścieżką i czerwonymi reprezentującymi ściany. Niebieskie pole to miejsce, do którego ma trafić duszek. Zgodnie z działaniem algorytmu duszek porusza się po zielonych polach docierając do celu, zostawiając przy tym czerwone kropki w odwiedzonych miejscach.
Film pokazujący działający algorytm. Na scenie widoczna jest plansza. Jest ona labiryntem z zielonymi polami będącymi ścieżką i czerwonymi reprezentującymi ściany. Niebieskie pole to miejsce, do którego ma trafić duszek. Zgodnie z działaniem algorytmu duszek porusza się po zielonych polach docierając do celu, zostawiając przy tym czerwone kropki w odwiedzonych miejscach.
Film przedstawiający działanie algorytmu.
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.
Film pokazujący działający algorytm. Na scenie widoczna jest plansza. Jest ona labiryntem z zielonymi polami będącymi ścieżką i czerwonymi reprezentującymi ściany. Niebieskie pole to miejsce, do którego ma trafić duszek. Zgodnie z działaniem algorytmu duszek porusza się po zielonych polach docierając do celu, zostawiając przy tym czerwone kropki w odwiedzonych miejscach.
Na planszy w powyższej aplikacji są pola w trzech kolorach – zielonym, czerwonym i jedno niebieskie. Zielony oznacza korytarz, czyli pola po których duszek może się poruszać, a czerwony - ściany, czyli pola, niedostępne dla duszka. Wyjście oznaczone jest kolorem niebieskim.
Wiedząc, że scena w Scratchu ma 480 pikseli szerokości i 360 pikseli wysokości możesz łatwo obliczyć długość boku pojedynczego pola. Dzieląc, np. wysokość (360) przez liczbę pól, które znajdują się w jednej kolumnie (9) dostaniesz wyniki równy 40. Tyle wynosi długość boku pojedynczego pola.
Przykładowy plik z planszą możesz pobrać poniżej.
R1217LNuF5eNb
Załącznik zawierający planszę będącą labiryntem o wymiarach 9x12.
Wykorzystaj poniższy dziennik do zapisywania notatek lub przemyśleń.
RmmJjmSvVzQ5i
Notatnik.
Źródło: GroMar, licencja: CC BY 3.0.
1
Ćwiczenie 1
Wczytaj planszę z labiryntem jako nowe tło sceny. Pamiętaj o usunięciu domyślnego, białego tła. Zmień rozmiary duszka, tak aby mieścił się w pojedynczym polu.
W prawym dolnym rogu programu znajduje się przycisk do dodawania nowego tła. Po jego kliknięciu pojawi się opcja, która pozwoli ci wczytać własne tło. Jeśli chcesz dostosować rozmiar duszka, możesz to zrobić edytując odpowiednie pole, które znajduje się po prawej stronie w sekcji zarządzania duszkami.
W celu wczytania pobranego tła, zlokalizuj i naciśnij przycisk Wczytaj tło. Poniższy zrzut ekranu pomoże ci go zlokalizować. Następnie wybierz wcześniej pobraną grafikę i naciśnij Otwórz.
R1b8YzqCK6unh
Grafika przedstawia okienko programu Scratch. W prawym dolnym rogu wyróżniono za pomocą czerwonego prostokąta miejsce wstawiania nowego tła. Znajduje się w nim niebieski okrągły przycisk z rozwijaną listą i wybraną opcją "Wczytaj tło".
Dodawanie tła w programie Scratch.
Źródło: GroMar, licencja: CC BY 3.0.
Aby podstawowy duszek zmieścił się w pojedynczym kwadracie, ustaw jego rozmiar na 35. W tym celu wpisz odpowiednią liczbę w polu tekstowym obok napisu Rozmiar.
R19CQxXQhxOK3
Grafika przedstawia okienko programu Scratch. Po prawej stronie pod sceną znajduje się pole tekstowe do zmiany rozmiaru duszka z wpisaną wartością 35. Wyróżnione jest ono czerwonym prostokątem.
Zmiana rozmiaru duszka w programie Scratch.
Źródło: GroMar, licencja: CC BY 3.0.
Algorytm znajdowania wyjścia z labiryntu
1
Ćwiczenie 2
Opracuj plan działania dla duszka, określając, jak powinien się poruszać, aby znaleźć drogę. Przyjmij założenie, że duszek „patrzy” tylko o jedno pole wprzód oraz pamięta (oznacza) pola, które już odwiedził. Może więc stwierdzić, czy sąsiednie pole jest ścianą, wolnym polem albo polem, przez które już przeszedł. Może też cofać się, jak trafi w ślepą uliczkę.
Do poprawnego stworzenia algorytmu rozwiązującego to zadanie niezbędne będzie zrozumienie pojęcia rekurencjiPXyPxbpbPrekurencji. Rekurencja jest ważnym konceptem programistycznym, który polega na tym, że funkcja może wywołać samą siebie w celu rozwiązania problemu.
Duszek, stojąc na danym polu, powinien najpierw je oznaczyć. Następnie może próbować podjąć próbę przejścia na jedno z czterech sąsiednich pól. Ponieważ nic więcej nie wie, więc jest obojętne, które pole wybierze. Może na przykład rozpocząć od pola w kierunku, w którym aktualnie patrzy. Przy próbie przejścia na sąsiednie pole mogą wystąpić następujące sytuacje:
Sąsiednie pole jest wyjściem. Sukces i koniec algorytmu.
Sąsiednie pole jest wolne i nie było odwiedzane. Należy na nie przejść i kontynuować działanie, tak jakby to było pole startowe. Jeżeli nie przyniesie rezultatu (nie doprowadzi do wyjścia) należy się wycofać z ruchu.
Sąsiednie pole jest ścianą lub było już odwiedzone. Należy zmienić kierunek (np. w prawo o 90 stopni).
Ponieważ duszek ma do sprawdzenia cztery kierunki, powyższe czynności powinien powtórzyć cztery razy.
Funkcja szukaj_drogi:
Oznacz pole, na którym stoisz.
Powtórz 4 razy: 2.1. Jeżeli pole, na które patrzy duszek jest wyjściem to: ⠀ 2.1.1. Przejdź na pole na wprost (przesuń o 40 kroków). ⠀ 2.1.2. Powiedz: „Znalazłem wyjście!”. ⠀ 2.1.3. Zatrzymaj wszystko. 2.2. Jeżeli pole na wprost jest wolne i nie było odwiedzane, to: ⠀ 2.2.1. Przejdź na pole na wprost (przesuń o 40 kroków). ⠀ 2.2.2. Wywołaj funkcję szukaj_drogi. ⠀ 2.2.3. Wycofaj się z ostatniego ruchu (przesuń o -40 kroków). 2.3. Jeżeli pole na wprost jest ścianą lub było odwiedzone to: ⠀ 2.3.1. Obróć się w prawo o 90 stopni.
Zatrzymaj ten skrypt.
Zwróć uwagę na bardzo ważny punkt 2.2.2. Duszek rozpoczyna ponownie wykonywanie tego samego algorytmu od początku, ale z innego pola. Jeżeli z tego pola jest wyjście, nie wróci już do punktu 2.2.3. (ponieważ zakończy wykonywanie algorytmu w punkcie 2.1.2.). Natomiast jeżeli poszukiwanie drogi z tego pola zakończy się niepowodzeniem, wróci do punktu 2.2.3. i wycofa się z ostatniego ruchu. Zwróć też uwagę, że sprawdzenie warunku w punkcie 2.3. jest niepotrzebne. Jeżeli sąsiednie pole nie było wyjściem (punkt 2.1.) i nie dało się przez nie dojść do wyjścia (punkt 2.2.), to jest ścianą lub zostało oznaczone jako odwiedzone. Powyższy przepis można więc nieznacznie uprościć.
szukaj_drogi:
Oznacz pole, na którym stoisz.
Powtórz 4 razy: 2.1. Jeżeli pole na wprost jest wyjściem to: ⠀ 2.1.1. Przejdź na pole na wprost (przesuń o 40 kroków). ⠀ 2.1.2. Powiedz: „Znalazłem wyjście!”. ⠀ 2.1.3. Zatrzymaj wszystko. 2.2. Jeżeli pole na wprost jest wolne i nie było odwiedzane to: ⠀ 2.2.1. Przejdź na pole na wprost (przesuń o 40 kroków). ⠀ 2.2.2. Szukaj drogi. ⠀ 2.2.3. Wycofaj się z ostatniego ruchu (przesuń o -40 kroków). 2.3. Obróć się w prawo o 90 stopni.
Zatrzymaj ten skrypt.
2
Ćwiczenie 3
Wykonaj poniższe kroki, aby ustalić aktualną pozycję i kierunek duszka. Zakładamy, że duszek zaczyna na polu B2 i spogląda w dół. Kierunki jakie może wykonać to: dół, góra, lewo, prawo.
Zapisz początkową pozycję duszka jako B2,
Zapisz początkowy kierunek duszka jako dół,
Przejdź do następnego kroku algorytmu.
R5K5MZejQRBWr
Grafika przedstawia planszę gry będącą labiryntem z czerwonymi polami jako ściany, zielonymi jako ścieżka i niebieskim jako punkt końcowy. Na obrzeżach wyróżnione są współrzędne w postaci cyfr od 1 do 5 i liter A do E.
Labirynt z wyróżnionymi współrzędnymi.
Źródło: GroMar, licencja: CC BY 3.0.
R1GEJkQ7V7r1g
Tabela przedstawiająca ruchy duszka.
Źródło: GroMar, licencja: CC BY 3.0.
Poniższy film pokazuje działanie algorytmu dla planszy powyżej. Wypełniona tabela powinna odpowiadać ruchom duszka.
RXsPxc44cOT6r
Na filmie widoczna jest dołączona do zadania plansza. Ma ona wymiary 5x5, a w środku w kształcie litery H znajduje się ścieżka wyróżniona kolorem zielonym. W prawym dolnym rogu planszy na bloku powyżej jest cel, do którego dąży duszek. Cel jest jest pomalowany na niebiesko, a pozostałe bloki są czerwone. Duszek porusza się po zielonej ścieżce zostawiając czerwone kropki na odwiedzonych polach.
Na filmie widoczna jest dołączona do zadania plansza. Ma ona wymiary 5x5, a w środku w kształcie litery H znajduje się ścieżka wyróżniona kolorem zielonym. W prawym dolnym rogu planszy na bloku powyżej jest cel, do którego dąży duszek. Cel jest jest pomalowany na niebiesko, a pozostałe bloki są czerwone. Duszek porusza się po zielonej ścieżce zostawiając czerwone kropki na odwiedzonych polach.
Działanie algorytmu na załączonej planszy.
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.
Na filmie widoczna jest dołączona do zadania plansza. Ma ona wymiary 5x5, a w środku w kształcie litery H znajduje się ścieżka wyróżniona kolorem zielonym. W prawym dolnym rogu planszy na bloku powyżej jest cel, do którego dąży duszek. Cel jest jest pomalowany na niebiesko, a pozostałe bloki są czerwone. Duszek porusza się po zielonej ścieżce zostawiając czerwone kropki na odwiedzonych polach.
Kolejne wywołania algorytmu szukaj_drogi:
RiniYdpwHEFaQ
Diagram szukania drogi przez duszka. Każdy kolejny krok znajduje się w prostokącie z zaokrąglonymi rogami. Pierwszym krokiem jest "Szukaj drogi z pola B2". Z pierwszego kroku poprowadzona jest strzałka do drugiego kroku "Szukaj drogi z pola C2". Kolejna strzałka jest rozgałęzieniem, krok po lewej mówi "Szukaj drogi z pola D2". Na tym kończą się kroki w tej ścieżce. Druga opcja, krok po prawej, mówi "Szukaj drogi z pola C3". Poprowadzona z tego pola strzałka prowadzi do kolejnego kroku "Szukaj drogi z pola C4", kolejna prowadzi do "Szukaj drogi z pola D4".
Diagram szukania drogi przez duszka.
Źródło: GroMar, licencja: CC BY 4.0.
Rq6bB3Zg4dDVx
Grafika przedstawiająca tabelę z ruchami duszka. Składa się z 2 kolumn: "Pozycja (pole) duszka" i "Kierunek". Pozycja przedstawiona się za pomocą współrzędnych, gdzie pierwsza składowa to litera od A do E, a druga to cyfra od 1 do 5. Kierunek natomiast to jedna z opcji: "góra", "dół", "lewo", "prawo".
Tabela z ruchami duszka.
Źródło: Janusz Wierzbicki, Maciej Borowiecki, licencja: CC BY 3.0.
Ważne!
W naszym rozwiązaniu, gdy napotkaliśmy pewien problem, zastosowaliśmy podejście, w którym odwołujemy się do tego samego problemu, ale dla innych danych. Może to oznaczać, że mamy podobną sytuację do rozwiązania, ale z innymi wartościami lub innymi warunkami. Na przykład, jeśli mamy do wykonania pewne zadanie, które można podzielić na mniejsze zadania tego samego typu, możemy użyć rekurencji (rekursji). To znaczy, że w celu rozwiązania całego zadania, wykonujemy te same kroki dla każdego z tych mniejszych zadań. Rekurencja polega na tworzeniu zbioru poleceń, które wywołują same siebie wewnątrz siebie. W Scratchu takie zbiory stanowią utworzone przez nas bloki w kategorii Moje bloki. Działa to podobnie jak rosyjskie lalki Matrioszka, gdzie jedna lalka jest schowana wewnątrz drugiej. W przypadku rekurencji, funkcja wykonuje się, a następnie wywołuje samą siebie, aby rozwiązać podzadanie, a to podzadanie może z kolei wywołać kolejne podzadania, aż do momentu osiągnięcia warunku zakończenia.
Więcej na temat rekurencji dowiesz się w dalszej części materiału.
Tworzymy skrypty dla duszka
Przed przystąpieniem do tworzenia skryptów należy jeszcze rozstrzygnąć dwa problemy:
Jak duszek ma oznaczać pole?
W jaki sposób duszek ma rozpoznawać kolor sąsiedniego pola?
Zwróć uwagę, że nie ma znaczenia, czy pole jest ścianą, czy było już odwiedzone. Najwygodniej będzie oznaczać pola odwiedzone tym samym kolorem co ściana. Jak można zauważyć na filmach, duszek stawia na nowo odwiedzanym polu kropkę w kolorze ściany.
Żeby sprawdzić w jakim kolorze jest sąsiednie pole, duszek musi niestety na nim stanąć. Przejdzie więc najpierw na sąsiednie pole. Jeżeli pod duszkiem nie ma koloru czerwonego, kontynuuje działania. Jeżeli jest kolor czerwony, wycofuje się. W związku z tym dostosujemy nasz algorytm w postaci listy kroków do możliwości duszka w środowisku Scratch.
szukaj_drogi:
Oznacz pole, na którym stoisz.
Powtórz 4 razy: 2.1. Przesuń o 40 kroków. 2.2. Jeżeli dotyka koloru niebieskiego to: ⠀ 2.2.1. Powiedz „Znalazłem wyjście przez 2 sekundy”. ⠀ 2.2.2. Zatrzymaj wszystko. 2.3. Jeżeli nie dotyka koloru czerwonego to: ⠀ 2.3.1. Szukaj drogi. 2.4. Przesuń o -40 kroków. 2.5. Obróć się w prawo o 90 stopni.
Zatrzymaj ten skrypt.
2
Ćwiczenie 4
Stwórz swój własny skrypt, który będzie wykonywał opisany wcześniej algorytm. Zacznij od utworzenia nowego bloku o nazwie oznacz_pole. Możesz tego dokonać klikając przycisk Utwórz blok w kategorii Moje bloki. Dane wejściowe pozostaw puste.
Po utworzeniu nowego bloku jest on od razu dostępny w kategorii Więcej bloków. Możesz go wykorzystać w definicji tego bloku. W ten sposób wykonasz wywołanie tej samej funkcji dla nowych parametrów.
R16RMCVP9IfSd
Na grafice widoczne jest plansza programu Scratch ze skryptem. Składa się on z 3 głównych bloków. Pierwszy z nich to własny blok koloru różowego z tekstem "definiuj szukaj_drogi". Drugi klocek również jest własnym blokiem i jest opisany jako "oznacz_pole". Po nim znajduje się żółty blok kontroli "powtórz ... razy" z wpisaną wartością 5 w polu tekstowym. Pozwala on zagnieżdżać w sobie inne bloki. Pierwszym z nich jest niebieski klocek "przesuń o ... kroków" z uzupełnioną wartością 40. Do niego dołączony jest blok "jeżeli ... to" z klockiem "dotyka koloru niebieskiego?" jako argument. Wewnątrz klocka "jeżeli" znajdują się 2 bloki: "powiedz ..." z wpisaną wiadomością "Hurra! Znalazłem wyjście!" i "zatrzymaj ..." z rozwijaną listą ustawioną na wartość "wszystko". Trzeci zagnieżdżony blok wewnątrz klocka "powtórz ..." to "jeżeli ... to". Bloczek "nie" jest argumentem i ma w sobie klocek "dotyka koloru czerwonego" ustawiony jako wartość. Wewnątrz bloku "jeżeli" jest własny klocek "szukaj_drogi". Dwa ostatnie klocki będące częścią klocka pętli "powtórz" to "przesuń o -40 kroków" i "obróć w prawo o 90 stopni". Na sam koniec skryptu dołączony jest blok "zatrzymaj" z wybraną z listy opcją "ten skrypt".
Przykładowy skrypt szukania ścieżki.
Źródło: GroMar, licencja: CC BY 3.0.
2
Ćwiczenie 5
Uzupełnij blok oznacz_pole. Zastanów się, jak narysować czerwony ślad. Pamiętaj, że duszek po narysowaniu musi być na tej samej pozycji, co przed rysowaniem.
Wystarczy jak czerwony ślad będzie pojedynczą kropką. Jego zadanie to pokazanie przebytej przez duszka drogi.
RsjShxG8BNq6s
Grafika przedstawia definicja własnego bloku "oznacz_pole". Rozpoczyna się od różowego bloku "definiuj oznacz_pole". Kolejny klocek to zielony blok z ikonką pisaka i poleceniem "Przyłóż pisak". Po nim występują 2 niebieskie klocki "przesuń o ... kroków". Pierwszy ma wpisaną wartość 1, a drugi -1. Do nich dołączony jest zielony blok pisaka. Opisany jest jako "Podnieś pisak" i tak jak poprzedni ma na początku ikonę pisaka. Skrypt kończy klocek "zatrzymaj ..." z wybraną z listy rozwijanej wartością "ten skrypt".
Definicja bloku "oznacz_pole".
Źródło: GroMar, licencja: CC BY 3.0.
2
Ćwiczenie 6
Przygotuj skrypt, który po uruchomieniu spowoduje, że duszek dotrze do niebieskiego pola na planszy. Aby tego dokonać, umieść duszka na polu startowym i ustal, w którym kierunku ma się poruszać. Dodatkowo, użyj pisaka do oznaczenia odwiedzonych miejsc. Do znalezienia trasy wykorzystaj wcześniej przygotowany blok o nazwie szukaj_drogi.
Zastanów się, jakie czynności początkowe, oprócz ustawienia atrybutów pisaka (rozmiaru, koloru), należy wykonać po kliknięciu zielonej flagi. Weź też pod uwagę, że jeżeli duszek będzie zbyt dużych rozmiarów, Scratch będzie błędnie interpretował, że duszek zawsze dotyka koloru czerwonego.
Duszka należy ustawić w polu startowym, obróconego w wybranym kierunku (jeden z czterech: lewo, prawo, góra, dół) oraz wyczyścić scenę po poprzednim uruchomieniu.
R1W1iItrO4XsF
Grafika przedstawia skrypt języka Scratch do znajdywania ścieżki. Całość zaczyna się od żółtego bloku "kiedy kliknięto zieloną flagę". Następnie dołączony jest zielony blok pisaka "wyczyść wszystko". Po nim dodane są 2 niebieski klocki: "Idź do x: -180 y: 120" i "ustaw kierunek na 90". Kolejnym klockiem jest fioletowy blok "ustaw rozmiar na ... %" z wpisaną wartością 35. Następnie wykonywane jest polecenie "Ustaw kolor pisaka na czerwony", a po nim "Ustaw rozmiar pisaka na 5". Blok "powiedz ... przez ... sekund" jest kolejnym i ma uzupełnione pola na "Znajdę wyjście z labiryntu" i 2. Przedostatnio blok to "szukaj_drogi", a po nim polecenie "zatrzymaj ..." z "wszystko" jako wybrana opcja z rozwijanej listy.
Przykładowy skrypt z wykorzystaniem bloku "szukaj_drogi".
Źródło: GroMar, licencja: CC BY 3.0.
Uruchom i przetestuj działanie aplikacji. Prawdopodobnie duszek bardzo szybko biega po labiryncie. Możesz go spowolnić, wstawiając klocek czekaj … si0E2ogPrm8_d479e210czekaj … s z odpowiednio dobranym czasem opóźnienia przed wywołaniem bloku szukaj_drogi. Możesz także przygotować drugi skrypt uruchamiany po kliknięciu zielonej flagi animujący duszka podczas chodzenia po labiryncie.
i0E2ogPrm8_d479e187
R2TTlVzOyuwRw
Niebieski klocek z tekstem "dotyka koloru ... ?" i wybranym fioletowym kolorem.
Blok "dotyka koloru ... ?" z kategorii "Czujniki".
Źródło: GroMar, licencja: CC BY 3.0.
Czujnik sprawdza, czy duszek dotyka wybranego koloru na scenie. Aby wybrać kolor, należy kliknąć myszką w kwadracik z kolorem w klocku, następnie wskazać kursorem myszy kolor na ekranie.
Przykład:
R1YAHxtaDdCzy
Skrypt realizujący powtarzanie instrukcji rozpoczynający się poleceniem "kiedy kliknięto w zieloną flagę", po którym dołączony jest blok "Idź do x: ... y: ..." z ustawionymi wartościami na 0. Następnie dodany jest klocek "powtarzaj aż ..." z blokiem "dotyka koloru fioletowego?" jako argument. Wewnątrz bloku powtórzeń znajdują się 3 bloki podrzędne: "przesuń o ... kroków" z wpisaną wartością 5, "następny kostium" i "czekaj 0.3 sekundy". Po bloku "powtarzaj aż ..." Dołączony jest klocek "Powiedz ..." z wpisanym komunikatem "Doszedłem do ściany!". Ostatni klocek to "zatrzymaj ..." z "ten skrypt" jak wybrana z listy opcja.
Skrypt realizujący powtarzanie instrukcji.
Źródło: GroMar, licencja: CC BY 3.0.
i0E2ogPrm8_d479e210
R1Z6YginlxEqt
Grafika przedstawia żółty klocek programu Scratch z kategorii "Kontrola" z poleceniem "czekaj aż ..." i pustym polem do podania wartości.
Klocek "czekaj aż ..." z kategorii "Kontrola".
Źródło: GroMar, licencja: CC BY 3.0.
Bloczek powoduje wstrzymanie działania skryptu na określony czas.
Przykład:
RZze1Pxa3TEq4
Skrypt realizujący instrukcję w pętli. Składa się z bloku rozpoczynającego "kiedy kliknięto w zieloną flagę" i bloku "zawsze". W klocku "zawsze" umieszczone są 2 bloki: "następny kostium" i "czekaj ... sekund" z wpisaną wartością 0.3.
Przykład z zastosowaniem bloku "zawsze".
Źródło: GroMar, licencja: CC BY 3.0.
Zadania uzupełniające
2
Ćwiczenie 7
Popraw planszę tak, aby nie było przejścia z pola startowego do wyjścia lub usuń wyjście. Możesz w tym celu skopiować tło sceny i je nieznacznie poprawić w edytorze graficznym. Na którym polu duszek zakończy poszukiwanie drogi? Jaki blok za to odpowiada? Popraw skrypt tak, aby duszek poinformował w dymku komiksowym, że nie ma przejścia do wyjścia.
Zablokowanie drogi do wyjścia możesz osiągnąć zmieniając kolor jednego z pól, np. D4 z zielonego na czerwony. Możesz także usunąć wyjście zamalowując niebieski kwadrat na czerwono.
Przyjrzyj się skryptowi odpowiedzialnemu za szukanie drogi i znajdź polecenie, które odpowiada za poruszanie się duszka po planszy.
RR9wp5uthXmLl
Załącznik zawierający planszę będącą labiryntem o wymiarach 9x12.
Załącznik zawierający planszę będącą labiryntem o wymiarach 9x12.
Źródło: GroMar, licencja: CC BY 3.0.
Plik PNG o rozmiarze 1.60 KB w języku polskim
Duszek powróci do pola startowego po odwiedzeniu wszystkich możliwych pól, do których może dojść. Wywołanie wcześniej wykonanych skryptów zakończy się po wykonaniu wszystkich bloków (ostatni blok zatrzymaj ten skrypt), więc sterowanie wróci do skryptu zielonej flagi. Tam, po wykonaniu bloku szukaj_drogi, można dodać wyświetlenie informacji w dymku komiksowym o nieznalezieniu wyjścia.
2
Ćwiczenie 8
Zmodyfikuj tak aplikację, aby duszek próbę wykonania kolejnego ruchu rozpoczynał zawsze od tego samego kierunku (np. w prawo), a nie kierunku, w którym patrzy.
Zadbaj o to, aby duszek wycofując się z ruchu, patrzył w tym samym kierunku, w którym wykonał ruch.
Wstaw dodatkowy blok ustawiający duszka w wybraną stronę tuż przed rekurencyjnym wywołaniem funkcji szukaj_drogi.
R1bTNH5HlV4yg
Na grafice widoczne jest plansza programu Scratch ze skryptem. Składa się on z 3 głównych bloków. Pierwszy z nich to własny blok koloru różowego z tekstem "definiuj szukaj_drogi". Drugi klocek również jest własnym blokiem i jest opisany jako "oznacz_pole". Po nim znajduje się żółty blok kontroli "powtórz ... razy" z wpisaną wartością 5 w polu tekstowym. Pozwala on zagnieżdżać w sobie inne bloki. Pierwszym z nich jest niebieski klocek "przesuń o ... kroków" z uzupełnioną wartością 40. Do niego dołączony jest blok "jeżeli ... to" z klockiem "dotyka koloru niebieskiego?" jako argument. Wewnątrz klocka "jeżeli" znajdują się 2 bloki: "powiedz ... przez ... sekund" z wpisaną wiadomością "Hurra! Znalazłem wyjście!" i ustawionym czasem na 2 sekundy oraz "zatrzymaj ..." z rozwijaną listą ustawioną na wartość "wszystko". Trzeci zagnieżdżony blok wewnątrz klocka "powtórz ..." to "jeżeli ... to". Bloczek "nie" jest argumentem i ma w sobie klocek "dotyka koloru czerwonego" ustawiony jako wartość. Wewnątrz bloku "jeżeli" jest własny klocek "szukaj_drogi". Dwa ostatnie klocki będące częścią klocka pętli "powtórz" to "przesuń o -40 kroków" i "obróć w prawo o 90 stopni". Na sam koniec skryptu dołączony jest blok "zatrzymaj" z wybraną z listy opcją "ten skrypt".
Przykładowy skrypt z ustawieniem kierunku.
Źródło: GroMar, licencja: CC BY 3.0.
Ciekawostka
Do realizacji zadania została zastosowana technika projektowania algorytmów – rekurencja. Budując algorytm rekurencyjny należy pamiętać o podstawowych zasadach: wywołanie rekurencyjne zazwyczaj występuje dla zmienionych danych przy spełnieniu pewnego warunku. Ciąg wywołań rekurencyjnych powinien się zakończyć w momencie spełnienia warunku stopu. Warunek stopu oznacza, że program dla dowolnych danych musi ostatecznie zakończyć działanie. Ustalenie warunku stopu jest ważne w przypadku funkcji rekurencyjnych, bowiem definiując funkcje rekurencyjne nietrudno o warunku stopu zapomnieć. Najczęściej budujemy blok rekurencyjny z danymi wejściowymi, a warunek, kiedy następuje wywołanie rekurencyjne zależy od tych danych. W omawianym algorytmie rekurencyjnym (wychodzenia z labiryntu) rolę danych wejściowych pełni pole, na którym stoi duszek, choć sam blok (w skryptach) jest zdefiniowany bez parametrów. Wywołanie rekurencyjne zależy od koloru pola, na które próbuje przejść duszek. Porównaj działanie opracowanej przez siebie aplikacji z filmem, który znajduje się na początku tego materiału. Czy obie aplikacje stosują ten sam algorytm znajdowania drogi wyjścia z labiryntu? Łatwo zauważysz, że w twojej aplikacji duszek znajduje drogę do wyjścia, ale wcale nie najkrótszą, często wracając. Takie algorytmy nazywane są algorytmami z powrotami i często są zapisywane rekurencyjnie. Natomiast w przedstawionej na filmie aplikacji duszek znajduje najkrótszą drogę do wyjścia. Rozwiązuje tak naprawdę bardziej ogólny problem znalezienia najlepszej drogi (w tym przypadku najkrótszej) pomiędzy dwoma miejscami (polami). Z problemem znalezienia najlepszej drogi (najkrótszej, najszybszej) możesz się zetknąć choćby korzystając z nawigacji satelitarnej lub map internetowych. W przyszłości, jeśli będziesz kontynuować swoją przygodę z algorytmami, poznasz zapewne algorytm znajdowania najkrótszej drogi przejścia, a także inne problemy rozwiązywane algorytmami z powrotami.
2
Ćwiczenie 9
Zajrzyj do projektu Ułamki zwykłeD1AyvQpb3Ułamki zwykłe dotyczącego algorytmu Euklidesa. Własność NWD została zdefiniowana rekurencyjnie:
przy założeniu, że a>b.
Spróbuj utworzyć własny blok obliczający NWD rekurencyjnie i stwórz prostą aplikację sprawdzającą, czy blok działa poprawnie.
Dodatkowe informacje znajdziesz w materiale Klasyczny Algorytm Euklidesa z resztą z dzieleniaPs7XRBNbCKlasyczny Algorytm Euklidesa z resztą z dzielenia. Odpowiednie zrozumienie algorytmu Euklidesa jest niezbędne, aby stworzyć poprawne rozwiązanie.
Zapoznaj się z przykładem skryptu, który znajdziesz w materiale Tworzenie gry interaktywnej - ułamki zwykłeD1AyvQpb3Tworzenie gry interaktywnej - ułamki zwykłe. Skrypt ma za zadanie znaleźć największy wspólny dzielnik (NWD). Jedyną różnicą jest to, że funkcja zostanie wywołana ponownie, ale z innymi liczbami jako parametrami. Dzięki temu możemy wielokrotnie używać tej samej funkcji do rozwiązywania problemów z różnymi liczbami.
Przykładowe skrypty:
R1LiLNHW7KbPa
Skrypt zaczyna się od bloku "definiuj" z uzupełnionym polem "NWD" przyjmującym 2 parametry: a i b. Następnie dołączony jest klocek "jeżeli ... to" z warunkiem "a = b". Wewnątrz bloku znajdują się 2 klocki: "ustaw ... na ..." z wartością NWD wybraną z rozwijanej listy i uzupełnioną wartością "a". Drugi klocek wewnątrz to "zatrzymaj" z opcją "ten skrypt" wybraną z listy. Po bloku "jeżeli ... to" występuje klocek "jeżeli ... to ... w przeciwnym razie". Tym razem argumentem jest blok "a > b". Pierwsza wartość dla warunku prawdziwego to wywołanie definicji za pomocą klocka "NWD" z dwoma wartościami - "a - b" i "b". Alternatywne rozwiązanie to wywołanie polecenia "NWD", tym razem z argumentami "a" i "b‑a".
Definicja skryptu obliczającego NWD.
Źródło: GroMar, licencja: CC BY 3.0.
RMTEFzwiToH6L
Skrypt rozpoczyna się od klocka "kiedy kliknięto w zieloną flagę". Po nim występuje blok "zapytaj ... i czekaj" z ustawionym komunikatem "Podaj a". Następnie dołączony jest blok "ustaw ... na ...". Z rozwijanej listy wybrana jest opcja "a", a drugi argument stanowi wartość pola "odpowiedź". Kolejnym blokiem jest "zapytaj ... i czekaj", tym razem z wartością "Podaj b". Po nim również następuje blok "ustaw" z wybraną wartością "b" z listy i wartością "odpowiedź" jako drugi argument. Następnym blokiem w skrypcie jest własny blok "NWD" przyjmujący 2 argumenty. Pierwszy z nich to "a", a drugi to "b". Do bloku "NWD" dołączony jest klocek "powiedz ... przez 2 sekundy". Treść komunikatu jaki ma się wyświetlić ustawiony jest na blok "połącz ... i ..." z dwoma polami: "Największy wspólny dzielnik wynosi: " i "NWD". Całość zakończona jest blokiem "zatrzymaj" ustawionym na "wszystko".
Przykład z zastosowaniem bloku NWD.
Źródło: GroMar, licencja: CC BY 3.0.
Ważne!
Dla wielu problemów można podać rozwiązanie zarówno rekurencyjne, jak i iteracyjne (czyli z wykorzystaniem pętli). W szczególności, jeśli w algorytmie rekurencyjnym następuje dokładnie jedno wywołanie rekurencyjne, zawsze można podać rozwiązanie z jedną pętlą powtarzaj ażi0E2ogPrm8_d479e272powtarzaj aż. W takiej sytuacji lepiej jest stosować rozwiązanie iteracyjne.
i0E2ogPrm8_d479e272
RgPsBWPPBDAOE
Żółty blok "powtarzaj aż ..." z wyróżnionym miejscem do podania warunku i miejscem na wstawienie bloków wewnątrz.
Blok "powtarza aż ..." z kategorii "Kontrola".
Źródło: GroMar, licencja: CC BY 3.0.
Klocek powtarza zestaw poleceń aż do spełnienia warunku logicznego. Warunki budujemy z klocków kategorii Czujniki i Wyrażenia.
Przykład:
RqzczEkM1ytrG
Skrypt składa się z 3 głównych bloków. Są nimi odpowiednio "kiedy kliknięto w zieloną flagę", "powtarzaj aż ..." z warunkiem "dotyka ... ?" z wybraną opcją "krawędź" z rozwijanej listy oraz "zatrzymaj" z opcją "ten skrypt". Wewnątrz bloku "powtarzaj aż ..." znajdują się 3 podbloki. Pierwszy z nich to "przsuń o ... kroków" z wpisaną wartością 3. Drugi blok to "następny kostium", a ostatnim klockiem wewnątrz jest "czekaj ... sekund" z uzupełnioną wartością "0.3".
Przykładowy skrypt z wykorzystaniem "powtarzaj aż ...".
