Ania Wieża Hanoi

Lista obecności

Wieża Hanoi

Dziś się dowiesz :

1. na czym polega problem wież Hanoi,
2. jak rozwiązać problem wież Hanoi za pomocą algorytmu rekurencyjnego,
3. jak zapisać rozwiązanie wież Hanoi w Scratch.

2.03

Na czym polega problem

Zagadka wież Hanoi powstała prawdopodobnie w Azji Wschodniej w XIX wieku lub wcześniej. Krążki były ceramiczne, produkowane w Chinach, Japonii i Wietnamie. Gra ta została sprowadzona na Zachód po raz pierwszy przez francuskiego matematyka Édouarda Lucasa w 1883 roku. Do sprzedawanego zestawu dołączona była tybetańska legenda, według której mnisi w świątyni Brahmy rozwiązują tę łamigłówkę dla 64 złotych krążków. Legenda mówi, że gdy mnisi zakończą zadanie, nastąpi koniec świata. Zakładając, że wykonują 1 ruch na sekundę, ułożenie wieży zajmie 264 −1 = 18 446 744 073 709 551 615 (blisko 18 i pół tryliona) sekund, czyli około 584,6 miliardów lat. Dla porównania: Wszechświat ma około 13,7 mld lat.

https://youtu.be/Mt-qP7-V6oU

2.03

Na czym polega problem

Wersja klasyczna wieży z Hanoi składa się z trzech słupków, na których umieszczona jest określona liczba krążków różnej wielkości poukładanych, począwszy od dołu, od największego do najmniejszego. Gra polega na przekładaniu krążków z jednego słupka na drugi tak, aby spełnione zostały następujące reguły: – podczas jednego ruchu można przenieść tylko jeden krążek, – nie można położyć krążka, który jest większy na krążku, który jest mniejszy. - można wykorzystywać trzeci słupek jako pomocniczy.

https://youtu.be/Mt-qP7-V6oU

2.03

Na czym polega problem

Wersja klasyczna wieży z Hanoi składa się z trzech słupków, na których umieszczona jest określona liczba krążków różnej wielkości poukładanych, począwszy od dołu, od największego do najmniejszego. Gra polega na przekładaniu krążków z jednego słupka na drugi tak, aby spełnione zostały następujące reguły: – podczas jednego ruchu można przenieść tylko jeden krążek, – nie można położyć krążka, który jest większy na krążku, który jest mniejszy. - można wykorzystywać trzeci słupek jako pomocniczy.

https://youtu.be/Mt-qP7-V6oU

2.03

Jak rozwiązać problem

To zadanie ma dość proste rozwiązanie rekurencyjne. Jeśli założyć, że przekładanie (n-1) krążków się uda, to algorytm - rozwiązania dla n krążków może wyglądać tak jak przedstawiono na poniższym rysunku. Dla trzech krążków należy wykonać 7 ruchów krążków.

1 ruch

4 ruch

https://youtu.be/Mt-qP7-V6oU

6 ruch

2 ruch

5 ruch

3 ruch

7 ruch

2.03

Ogólny wzór na ilość ruchów

Ogólny wzór na ilość ruchów (n - liczba krążków):

https://youtu.be/Mt-qP7-V6oU

2.03

Zadanie

Otwórz link i przetestuj gręhttp://online.freeware.info.pl/hanoi.html Zadanie 1 Narysuj w programie graficznym wieżę Hanoi składającą się z dwóch krążków, następnie przenieś wszystkie krążki z pierwszego drążka na drugi przy użyciu trzeciego. Trzeba to jednak zrobić przy dwóch założeniach: • wolno przenosić krążki tylko pojedynczo • ani przez moment krążek większy nie może leżeć na krążku mniejszym. Narysuj po kolei kroki przeniesienia tych drążków

https://youtu.be/Mt-qP7-V6oU

Wykonaj 5 duplikacji duszka arbuz, każdy skryp przypisz do odpowiedniego duszka.

2.03

Umieszczamy odpowiednio duszki potrzebne do projektu

W bibliotece duszków Scratch nie mamy odpowiednich duszków, dlatego musimy je ściągnąć na komputer. Pobieramy duszki potrzebne do gry. Będą to -wieża - zasłona - narysuj duszka zasłone w kolorze białym Tutaj możesz pobrać duszka wieża na komputer:

Wieża

Poruszanie się duszka

Wybór i ustawienie duszka

2.03

Tworzymy pierwszy blok

Definiujemy nowe bloki, klikając na "moje bloki" , dalej klikamy utwórz blok

1. Następnie klikamy cztery razy na dodaj dane i po koleji wpisujemy n,z,pom,na

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

Poruszanie się duszka

Wybór i ustawienie duszka

2.03

Tworzymy drugi blok

Tworzymy drugi blok , klikając na "moje bloki" ,dalej klikamy utwórz blok

2.

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

Klikamy trzykrotnie na dodaj dane i po kolej w kółka wpisujemy n,z, na

Poruszanie się duszka

Wybór i ustawienie duszka

2.03

Tworzymy zmienną i tworzymy listę

Tworzymy zmienną i listę , klikając na "zmienne"

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

Tworzymy zmienną klikając na utwórz zmienną i wpisujemy nazwę: - Krążków: Tworzymy listę klikając na stwórz listę i wpisujemy nazwę : -ruchy

+info

Wybór i ustawienie duszka

2.03

Tworzymy skrypt dla wieży

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

+info

Wybór i ustawienie duszka

2.03

c. d. Tworzymy skrypt dla wieży

blok dodaj jest w grupie zmienne

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

+info

Wybór i ustawienie duszka

2.03

c. d. Tworzymy skrypt dla wieży

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

+info

Wybór i ustawienie duszka

2.03

Tworzymy skrypt dla zasłony

Jeżeli duszka (kotka) dotknie przeszkoda to niech duszek “ucieka” w określone miejsce oraz punkty zmniejszają się o 2:

Dziękuję za uwagę!