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.

19. Tik-tak, tik-tak. Formaty dat, wykonywanie obliczeń na liczbach reprezentujących daty – arkusz kalkulacyjny

 

Cele:

- posługuję się formatami daty w arkuszu 

- wykonuje obliczenia na liczbach reprezentujących daty 

Co tak tyka? To zegar odmierzający kolejne sekundy, minuty, godziny. W zależności od dnia i sytuacji czas płynie szybko albo wlecze się nieznośnie. Podczas tej lekcji sprawdzisz, ile czasu poświęcasz na niektóre czynności i ile dni minęło od twoich urodzin.

CO ROBISZ W CIĄGU DNIA

Spójrz na tabelę wypełnioną przez Andzię.

Andzia wpisała czas trwania różnych czynności. Podała czas w minutach lub w godzinach, w zależności od tego, co uznała za wygodniejsze rozwiązanie. Następnie uzupełniła wolne miejsca – przeliczyła minuty na godziny i odwrotnie. Wystarczy tu wprowadzić odpowiednią formułę, z uwzględnieniem tego, że godzina ma 60 minut. Andzia dodała też kategorię inne, bo okazało się, że nie wszystko da się podliczyć. Ten zgubiony przy codziennych działaniach czas to reszta z całej doby, po odliczeniu czasu przeznaczonego na wszystkie wymienione czynności.

• Wykonaj podobną tabelę dla swojego poniedziałkowego rozkładu dnia.
• A teraz rozbuduj swoją tabelę tak, by uwzględnić wszystkie dni tygodnia. Sobota i niedziela będą zapewne wyglądały inaczej niż pozostałe dni.
  

  

  

• W dodatkowej tabeli zlicz czas (w godzinach) związany z poszczególnymi czynnościami dla całego tygodnia. W razie potrzeby wprowadź nowe kategorie.
  

  

ILE TO DNI, GODZIN, MINUT

Czy wiesz, ile dni minęło od chwili twojego urodzenia? Wyznaczenie dokładnej liczby dni może okazać się kłopotliwe ze względu na lata przestępne. Jeśli jednak wykorzystasz do tego arkusz, obliczenia okażą się łatwiejsze, niż myślisz.

W arkuszu kalkulacyjnym każdej dacie została przypisana kolejna liczba. To właśnie te liczby są używane do obliczeń. W Excelu liczba 1 oznacza 1 stycznia 1900 roku (pierwsza dostępna data, arkusz nie uznaje dat wcześniejszych), zaś liczba 2 958 465 oznacza 31 grudnia 9999 roku (ostatnia oznaczona data). W tej numeracji zostały uwzględnione wszystkie lata przestępne. Daty służące do obliczeń należy wprowadzać w takiej postaci, aby arkusz odróżnił je od zwykłego zapisu liczbowego. Zgodny z normą ISO format daty to RRRR-MM-DD, np. 4 października 2003 roku jest zapisywany jako 2003-10-04. Excel ze standardowymi ustawieniami zmodyfikuje ten zapis na 04.10.2003. Poprawnie wpisana data zostanie wyrównana, podobnie jak liczba, do prawej krawędzi komórki. Należy pamiętać, że wyświetlanie daty w arkuszu jest zależne od ustawień systemu i może być różne w różnych krajach.

• Wpisz do arkusza dzisiejszą datę za pomocą kombinacji klawiszy – ustaw kursor w komórce przeznaczonej na dzisiejszą datę i naciśnij kombinację klawiszy Ctrl + ; (średnik). Sprawdź, co się pojawiło w komórce, a co widać w podglądzie w wierszu edycji.
  

  

• Wpisz datę swoich urodzin w odpowiedniej postaci.

Pozostaje pytanie, jak znaleźć liczbę dni od daty twojego urodzenia. Jeśli wszystkie daty są w arkuszu kolejno ponumerowane, wystarczy od dzisiejszej daty odjąć datę urodzin!

A czy umiesz wskazać dokładnie tysięczny dzień swojego życia? A pięciotysięczny?

• Sporządź tabelę, tak jak zrobiła to Andzia, i podaj swoje obliczenia.
  

  

Dnia 17 czerwca 2018 roku Andzia miała 4205 dni. A ty? Ile dni, godzin, minut, sekund minęło od chwili twojego urodzenia do dziś?

Podczas wykonywania obliczeń na datach może się zdarzyć, że arkusz poda wynik w postaci liczby, a nie daty. Należy wówczas ustawić kursor w odpowiedniej komórce i na karcie Narzędzia główne w grupie Liczba wybrać z listy format daty.