3.5 Wieże Hanoi

 

DOWIESZ SIĘ

• na czym polega problem wież Hanoi,
• jak rozwiązać problem wież Hanoi za pomocą algorytmu rekurencyjnego,
• jak zapisać rozwiązanie problemu wież Hanoi w Scratchu.

Typowym przykładem przydatności rekurencji jest problem znany jako wieże Hanoi. Podczas tej lekcji przekonasz się, że zastosowanie wielokrotnej rekurencji bywa naprawdę pomocne.

NA CZYM POLEGA PROBLEM

Na początku świata Brahma postawił w klasztorze w Hanoi wieżę z 64 złotych krążków. Nakazał mnichom przenosić je według ścisłych zasad. Gdy mnisi przeniosą wszystkie krążki i utworzą nową wieżę, nastąpi koniec świata…

Wokół zabawki wprowadzonej na rynek europejski w 1883 r. przez francuskiego matematyka Édouarda Lucasa (czytaj: edułarda lukasa) szybko pojawiło się wiele legend. To jedna z nich. A sama zabawka? Na podstawce znajdują się trzy słupki; na jednym z nich umieszcza się osiem krążków o coraz mniejszych średnicach. Należy przenieść wszystkie krążki na inny słupek z zachowaniem następujących reguł:

• wolno przenosić po jednym krążku,
• nie wolno położyć większego krążka na mniejszym,
• można wykorzystywać trzeci słupek jako pomocniczy.

Rys. 1. Zabawka – wieże Hanoi

• Wykonaj tę grę dla trzech krążków (możesz spróbować zrobić to w pamięci). Powinno ci się udać przenieść wszystkie krążki w siedmiu ruchach.
• Znajdź w Wikipedii animację prezentującą rozwiązanie łamigłówki dla czterech krążków i zapisz kolejne ruchy, które trzeba wykonać.

JAK ROZWIĄZAĆ PROBLEM

To zadanie ma dość proste rozwiązanie rekurencyjne. Jeśli założyć, że przekładanie (n${\displaystyle n}$ – 1) krążków jakoś się uda, to algorytm – rozwiązanie dla n${\displaystyle n}$ krążków może wyglądać tak jak przedstawiono na poniższym rysunku.

1. Stan początkowy dla n${\displaystyle n}$ = 5 krążków.
   

   

2. Przenieś (n${\displaystyle n}$ – 1) krążków ze słupka A na B, potraktuj słupek C jako pomocniczy.
   

   

3. Przenieś n${\displaystyle n}$-ty krążek ze słupka A na C.
   

   

4. Przenieś (n${\displaystyle n}$ – 1) krążków ze słupka B na C; potraktuj słupek A jako pomocniczy. Jeśli nie ma krążków do przenoszenia, następuje koniec gry.
   

   

   Rys. 2. Schemat rozwiązania problemu wież Hanoi

Problem ten jest prezentowany w podręcznikach do informatyki jako przykład rekurencji oraz wykorzystywany podczas testów psychologicznych na kojarzenie i w badaniach neurologicznych. Algorytm znajduje także zastosowanie w schematach wykonywania kopii zapasowych danych czy zarządzaniu projektami.

JAK ZBUDOWAĆ SKRYPT

Skrypt bloku rekurencyjnego wHanoi, zbudowany według tego algorytmu, i wynik jego działania dla n${\displaystyle n}$ = 3 możesz zobaczyć na rys. 3, a wypróbować po uruchomieniu pokazu pod adresem https://scratch.mit.edu/projects/37051896.

Rys. 3. Skrypt wHanoi i jego rozwiązanie dla trzech krążków

Krążki są ponumerowane od najwyższego. Ile ruchów trzeba wykonać? Dla jednego krążka to oczywiście 1 ruch, dla dwóch – 3 ruchy, dla trzech – 7. Dla większej liczby krążków możesz to sprawdzić w projekcie.

Zakręt za zakrętem

 3.4 Zakręt za zakrętem
str. 81

Cele: 

- wiem, czym jest rekurencja,

- potrafię tworzyć skrypty rekurencyjne.

Rekurencja umożliwia łatwe rozwiązywanie trudnych zadań. Będziesz z niej korzystać wielokrotnie. Teraz zapoznasz się z działaniem pierwszego skryptu rekurencyjnego.

CO TO JEST REKURENCJA?

Spróbuj wytłumaczyć, jak wykonywać jakąś czynność wymagającą wielu powtórzeń, np. jak tańczyć tango. Dwa długie wolne kroki, dwa krótkie szybkie kroki. Potem cały proces się powtarza. Na tym właśnie polega rekurencja. To sposób opisywania powtarzających się czynności. W gruncie rzeczy można powiedzieć, że cały świat jest w pewnej mierze rekurencyjny – zmywanie naczyń, jedzenie zupy, przechodzenie po pasach przez ulicę, zbieranie rozsypanych kartek… Nie zawsze łatwo da się określić, ile razy powtórzyć polecenia. Opisujesz więc pewną procedurę, nie kończąc jej definiowania. Stosujesz procedury wywołujące same siebie.

Rys. 1. Schemat rekurencji bez końca i z warunkiem zatrzymania

RYSOWANIE GWIAZD

Figura przedstawiona na rys. 2 powstała wskutek wielokrotnego wykonania bloków przesuń o 200 kroków i obróć w prawo o 156 stopni. Ile razy? Dostatecznie wiele. Można pracowicie policzyć, ile potrzeba skrętów, aby uzyskać pełną gwiazdę, ale wygodniej jest zostawić tę część pracy komputerowi.

Rys. 2. Gwiazda o kącie skrętu 156º

Najprostszy plan rysowania gwiazdy, zapisany za pomocą języka naturalnego, wygląda następująco:

• przejście naprzód o długość boku,
• skręt w prawo o wartość kąta,
• powtórzenie tych samych czynności dostatecznie wiele razy.

Zrealizuj ten plan w Scratchu.

• Utwórz nowy blok o nazwie wielo, kliknij przycisk Dodaj dane wejściowe liczba lub tekst i dodaj dwa parametry liczbowe – bok i kąt.



Rys. 3. Definicja i wywołanie bloku wielo

• Utwórz skrypt, który po naciśnięciu klawisza w będzie odpowiadać za rysowanie – dodaj grupę bloków Pióro i przed wywołaniem bloku wielo wstaw bloki wyczyść wszystko (w ten sposób przy każdym uruchomieniu programu duszek będzie rysować w pustym oknie) oraz Przyłóż pisak. Jeśli chcesz, rozszerz skrypt o ustawienie właściwości pisaka.



Rys. 4. Skrypt rysowania z blokiem wielo

JAK ZATRZYMAĆ REKURENCJĘ?

Istnieje pewne ryzyko stosowania rekurencji: jeśli nie zostanie określony warunek zakończenia działania, to będzie ona działać w nieskończoność. W przypadku tańca warunek jest prosty: należy skończyć, gdy przestanie grać muzyka. Blok wielo nie ma określonego warunku zatrzymania – trzeba go zatem wstawić. Niech duszek kończy rysowanie po naciśnięciu lewego przycisku myszy.

• Dodaj do skryptu blok jeżeli (…) to (…) opisujący następującą sytuację: jeśli zostanie naciśnięty lewy przycisk myszy, to należy zatrzymać wykonywanie skryptu. Umieść go tuż po nagłówku bloku.



Rys. 5. Blok jeżeli (…) to (…)

• Przetestuj działanie skryptu – czy duszek zatrzymał się po naciśnięciu lewego przycisku myszy?
• Czy potrafisz zaplanować takie kąty skrętu, dla których powstaną ładne gwiazdy? Narysuj kilka gwiazd, żeby wypróbować różne kąty skrętu. Podaj również kąt 90 stopni. Co zostanie narysowane?

JAK ZMIENIĆ REKURENCJĘ?

Rekurencję można oczywiście zmodyfikować – wystarczy zmienić wartości parametrów w bloku rekurencyjnym.

• Zmień wartość parametrów w wywołaniu rekurencyjnym bloku wielo – niech bok zwiększa się o 5, a kąt maleje o 1.



Rys. 6. Zmiana parametrów bok i kąt w skrypcie

Skoro za pomocą bloku wielo można narysować kwadrat, to może uda się utworzyć również figurę przedstawioną na rys. 7?



Rys. 7. Labirynt

Ponieważ w tym wypadku długość boku się zmienia, trzeba wprowadzić pewne zmiany w bloku. Rysowanie należy zacząć od najkrótszego boku, np. o długości 5. Następny bok, rysowany po skręcie, powinien być o 5 dłuższy od poprzedniego i tak dalej, aż do narysowania najdłuższego boku, który dotknie krawędzi. Są tu elementy charakterystyczne dla budowy skryptu rekurencyjnego:

• warunek zakończenia: „aż do zetknięcia z krawędzią”,
• kroki do wykonania powtarzane rekurencyjnie: narysowanie boku i wykonanie skrętu o podany kąt.

Skąd jednak skrypt będzie wiedział, że ma narysować kolejny bok dłuższy od poprzedniego? To proste – blok rysuje bok, którego wartość podaje się w jego wywołaniu. Jeśli przy każdym kolejnym wywołaniu bok ma być dłuższy o 5 od poprzedniego, to należy zwiększać długość boku w wywołaniu rekurencyjnym.

• Utwórz rekurencyjny blok wielospi z parametrami bok, kąt.



Rys. 8. Blok wielospi

• Utwórz skrypt działający po naciśnięciu klawisza spacji – oprócz bloków odpowiadających za rysowanie i wywołania bloku rekurencyjnego dodaj bloki Idź do x: (…) y: (…) i ustaw kierunek na (…), tak aby duszek zaczynał rysowanie w tym samym punkcie okna i tak samo ustawiony. Wybierz parametry wywołania: bok 5, kąt 90.



Rys. 9. Skrypt uruchamiający blok wielospi

• Zwolnij działanie duszka, aby przyjrzeć się jego kolejnym ruchom – dodaj przed wywołaniem rekurencyjnym w bloku wielospi blok czekaj 0.5 sekund.
• Umieść blok czekaj za wywołaniem rekurencyjnym – tym razem duszek znów rysuje bardzo szybko, ale ma kłopoty z zakończeniem działania. Czy to możliwe, że blok dodany po wywołaniu rekurencyjnym zostanie wykonany?
• Przestaw blok czekaj na właściwe miejsce i dodaj za nim blok zmień rozmiar o 5. Jak teraz wykonywany jest skrypt? Jak powiększył się duszek?
• Wywołuj blok wielospi dla różnych kątów.



Rys. 10. Figura nakreślona po wywołaniu bloku wielospi

W projekcie znajdującym się pod adresem https://scratch.mit.edu/projects/342957512 możesz obejrzeć wiele różnych figur tworzonych przez blok wielospi.

5.5 Nie taka martwa natura

DOWIESZ SIĘ, JAK

• tworzyć film na podstawie jednego obrazu statycznego,
• wykorzystywać funkcje programu PhotoFilmStrip, m.in. importować obrazy, stosować swobodny ruch kamery, płynnie zmieniać kierunek ruchu kamery.

Na tej lekcji poznasz edytor do tworzenia animowanego pokazu slajdów PhotoFilmStrip (czytaj: fotofilmstrip). Jego ważną zaletą jest możliwość dowolnej analizy statycznego obrazu za pomocą kamery. Właśnie tę zaletę programu wykorzystasz podczas wykonywania ćwiczenia na bieżącej lekcji. Stworzysz film na podstawie jednego obrazu i plansz z napisami.

PRACE WSTĘPNE

Na warsztat weźmiesz dzieło Pietera Claesza (czytaj: Pitera Klasza) – holenderskiego malarza z okresu baroku. Obraz przedstawia martwą naturę. Na stole stoją patera z homarem i misy z owocami oraz różne przedmioty użytkowe: dzban, kielich, książki i skrzypce. Dostępna w internecie reprodukcja występuje pod niemieckim tytułem Tafel mit Hummer, Silberkanne, großem Berkemeyer, Früchteschale, Violine und Büchern.

• Wpisz w wyszukiwarce tytuł obrazu i ustaw kryteria wyszukiwania takie jak na poniższym zrzucie.



Rys. 1. Wyszukiwanie obrazu

• Pobierz obraz o możliwie największych rozmiarach i zapisz go pod nazwą Oryginał w folderze przeznaczonym na elementy graficzne.
• Przygotuj w programie GIMP czołówkę filmu, tj. planszę o rozmiarach 1920 × 1080 pikseli i rozdzielczości 72 ppi z napisem rozmieszczonym w trzech wierszach. W pierwszym wierszu ustaw tytuł MARTWA NATURA, w drugim nazwisko autora – Pieter Claesz, a w trzecim datowanie – 1597–1660. Sformatuj tekst według własnego uznania.
• W podobny sposób przygotuj planszę z napisem końcowym, np. „Realizacja filmu w programie PhotoFilmStrip: [imię i nazwisko]”.
• Zapisz oba pliki z napisami w formacie BMP w folderze przeznaczonym na prace graficzne. Nazwij je odpowiednio start i koniec.

TWORZENIE NOWEGO PROJEKTU

Składniki filmu już masz. Teraz musisz zaimportować je do swojego projektu.

• Utwórz nowy projekt w programie PhotoFilmStrip – po otwarciu aplikacji kliknij ikonę Create new project (czytaj: kriejt niu prodżekt).



Rys. 2. Tworzenie nowego projektu

• W oknie Project properties (czytaj: prodżekt propertis) uzupełnij właściwości projektu – wpisz nazwę projektu MartwaNatura, wskaż folder zapisu projektu (folder przeznaczony na pliki wideo) i ustaw współczynnik proporcji na 16:9. Zatwierdź ustawienia przyciskiem OK.



Rys. 3. Wprowadzanie nazwy projektu i ustalanie współczynnika proporcji boków klatki tworzonego filmu

• Zaimportuj plansze z napisami i reprodukcję – kliknij ikonę Import Pictures (czytaj: import pikczers), a następnie w oknie Import Images (czytaj: import imidżys) zaznacz plansze oraz reprodukcję i kliknij przycisk Otwórz.



Rys. 4. Importowanie plansz i obrazów

• Importuj reprodukcję jeszcze trzykrotnie – użyj ikony na pasku narzędzi.



Rys. 5. Ponowne importowanie reprodukcji

• Uporządkuj obrazy na taśmie filmowej u dołu strony – przeciągnij je tak, aby plansza startowa znalazła się na początku, a końcowa na końcu taśmy.

PRACA NA PLANIE FILMOWYM

Czas zająć się ożywieniem martwej natury. Zacznij od czołówki filmu, czyli animacji napisu początkowego.

• Zaznacz na taśmie planszę z napisem początkowym.

Nad taśmą znajdują się dwa okienka z aktywną planszą – w lewym pokazany jest fragment, od którego rozpocznie się animacja, a w prawym – obszar, na którym animacja się zakończy. Ustawienia te można zmieniać według własnego pomysłu.

• Zmodyfikuj początek i koniec animacji tak, aby uzyskać efekt płynnego powiększania planszy – w lewym okienku rozciągnij zaznaczenie tak, aby obejmowało całą planszę, w prawym okienku zmniejsz je tak, by mieścił się w nim tylko napis.



Rys. 6. Ustawienia pozwalające uzyskać efekt przybliżania napisu przez obiektyw kamery

• W pozycji Process określ pozostałe parametry animacji – tak jak na zrzucie poniżej.



Rys. 7. Ustalanie parametrów animacji

• Przejdź do następnej pozycji na taśmie, ustaw czas trwania animacji na 8 s i zaznacz brak przejścia.
• Ustal możliwie największy obszar początkowy animacji, a obszar końcowy zawęź do talerza z homarem. Aby precyzyjnie określić położenie zaznaczania i jego rozmiary, kliknij ikonę Adjust motion manual (czytaj: adżast mołszyn manjual), a następnie w oknie Motion positions (czytaj: mołszyn poziszyn) wpisz ustawienia dotyczące pozycji startowej i końcowej animacji – tak jak na zrzucie poniżej.



Rys. 8. Precyzyjne ustawianie położenia zaznaczenia

• Przechodź do kolejnych pozycji na taśmie i określaj dla nich parametry ruchu. W odniesieniu do obrazów z martwą naturą ustalaj czas na 8 s bez przejść. Dla ostatniego obrazu martwej natury ustal przejście w postaci przenikania. W przypadku napisu końcowego ustal czas animacji na 6 s bez przejścia.
• Animacje poszczególnych obrazów ustaw zgodnie ze schematycznym scenariuszem przedstawionym poniżej. Przy określaniu położenia i rozmiaru obszaru początkowego animacji każdego kolejnego obrazu pamiętaj, że muszą mieć one takie wartości jak wartości końcowe obrazu poprzedniego. Wykorzystaj narzędzie Adjust motion manual.



Rys. 9. Schematyczny scenariusz filmu

ZAPISYWANIE PROJEKTU I FILMU

Jeśli chcesz mieć możliwość wprowadzania poprawek – a może się okazać, że jest potrzebna jakaś zmiana – zapisz projekt filmu. Jeśli zapiszesz tylko film, nie będziesz mieć szansy na jakiekolwiek jego modyfikacje.

• W menu File (czytaj: fajl) wybierz polecenie Save project (czytaj: sejw prodżekt).

W folderze wskazanym podczas tworzenia nowego projektu program utworzy folder o nazwie MartwaNatura, a w nim zapisze plik projektu o nazwie MartwaNatura.pfs.

• Na pasku narzędzi kliknij ikonę Render filmstrip, a następnie w oknie Render filmstrip w polu Format wybierz pozycję x264/AAC (MP4), Resolution (czytaj: rezoluszyn), ustaw na FULL-HD (1920x1080) i kliknij przycisk Start.



Rys. 10. Ustalanie parametrów zapisywanego filmu

Pojawi się okno Job queue (czytaj: dżob kju) z paskiem postępu zapisu filmu. Kiedy pod paskiem postępu wyświetli się komunikat Done (czytaj: dan), można zamknąć okno i program. Film jest gotowy. Możesz obejrzeć swoje dzieło. Jeśli uznasz, że są konieczne poprawki, otwórz projekt, popraw mankamenty i ponownie zapisz projekt oraz film.

ZADANIE

1. Wyszukaj w internecie trzy (możliwie dużych rozmiarów) obrazy Józefa Chełmońskiego, na których namalowane są konie, i zapisz reprodukcje w folderze na obrazy. Wykonaj z tych materiałów trzy filmy w programie PhotoFilmStrip – każdy powinien trwać 20–30 s. Tym razem nie dodawaj plansz z napisami. Nie stosuj też żadnych dodatkowych efektów. Zapisz projekty i filmy w folderze przeznaczonym na filmy. Wykorzystasz je podczas następnej lekcji.