Zakręt za zakrętem – Dział III Algorytmy

Na dzisiejszych zajęciach przechodzimy do kolejnego działu algorytmy.

Algorytm – ciąg skończonych jasno zdefiniowanych czynności koniecznych do wykonania pewnego rodzaju zadań, sposób postępowania prowadzący do rozwiązania problemu.

Na dzisiejszych zajęciach dowiemy się w jaki sposób tworzy się skrypty rekurencyjne.

Rysowanie gwiazd

Rysowaliśmy już wielokąty foremne w Scratchu wykorzystując blok powtórz … razy – blok ten umożliwia powtórzenie danego polecenia kilkadziesiąt razy. Jednakże czasami nie wiadomo ile razy dane polecenie należy powtórzyć.

Zadanie czy jesteś w stanie narysować za pomocą Scratcha gwiazdę. według jakiego algorytmu musisz postępować? Jak zaplanować kolejne kroki działania?

Najprostszy plan rysowania gwiazdy to:

przejście naprzód o długość boku;
skręt w prawo o wartość kąta;
powtórzenie tych czynności dostateczną liczbę razy.

Przechodzimy do programu Scratch – przejdź do opcji więcej bloków – utwórz blok – nazwij go wielo – „wejdź” w opcje parametr liczbowy (dwukrotnie wybierz tą opcje) kolejne parametry nazwij bok i kąt.

Co to jest rekurencja?

Rekurencja – odwoływanie się np. funkcji lub definicji do samej siebie.

W logice wnioskowanie rekurencyjne opiera się na założeniu istnienia pewnego stanu początkowego oraz zdania (lub zdań) stanowiącego podstawę wnioskowania (przy czym, aby cały dowód był poprawny, zarówno reguła, jak i stan początkowy muszą być prawdziwe).

źródło: Wikipedia

Jeśli nie zostanie określony warunek końcowy działania rekurencji to ta procedura będzie działała w nieskończoność. W przypadku tańca należy skończyć tańczyć gdy gra muzyka.

Blok, który stożyliśmy wielo nie ma określonego warunku zatrzymania i byłoby nie dobrze gdyby nie czerwony przycisk zatrzymania całego programu – należy unikać takich konstrukcji.

Jak zatrzymać rekurencję?

Należy wstawić warunek zatrzymania. Niech duszek skończy rysowanie gwiazdy po naciśnięciu przycisku myszki. Do bloku należy podpiąć blok jeżeli.

Z rekurencji będziemy korzystać często. Umożliwia on łatwe rozwiązanie trudnych zadań. Pamiętaj, że zawsze należy zatrzymać wykonywanie skryptu.

Zadanie

Narysuj kilka gwiazd z różnymi kątami skrętu. Podaj również kąt 90 stopni – zostanie wówczas narysowany kwadrat – okazuje się, że blok wielo może rysować również wielokąty.

Jak zmienić rekurencję?

Problem?

Jak zmienić wartość parametru w wykonaniu rekurencyjnym bloku wielo niech bok zwiększa się o 10 a kąt maleje o 5 stopni. Co narysuje ten program?

Skoro za pomocą bloku wielo można narysować kwadrat – to można również utworzyć figurę przedstawioną na poniższym rysunku.

Długość rysowanego boku zmienia się- trzeba wprowadzić pewne zmiany w bloku. Utworzysz nowy blok wielospi z parametrami bok i kąt. Blok ten powinien rysować od najkrótszego boku np.: o długości 5. Następny bok narysowany po skręcie będzie o 5 dłuższy od poprzedniego i tak dalej, aż do narysowania najdłuższego boku, który będzie dotykać krawędzi. Są tu trzy charakterystyczne elementy do budowy skryptu rekurencyjnego:

warunek zakończenia, aż do zetknięcia z krawędzią;
krok do wykonania, narysowanie boku i wykonanie skrętu o kąt;
powtarzanie rekurencji „i tak dalej”.

Skąd skrypt będzie wiedział, że ma narysować bok dłuższy od poprzedniego? (Blok rysuje bok, którego wartość podajesz w wywołaniu. Jeśli przy, każdym kolejnym wywołaniu bok ma być dłuższy o 5 od poprzedniego, to należy zwiększyć długość boku w wywołaniu rekurencyjnym.

Zbuduj w Scratchu rekurencyjny blok wielospie z parametrami bok, kąt wybierz na początku parametry wywołania: bok 5, kąt 90. Jeśli chcesz się przyjrzeć ruchom duszka zwolnij jego działanie. (dodaj blok czekaj 0.5 s) To polecenie zatrzyma duszka na 0,5 sekundy.

Co się stanie jeśli blok czekaj przestawisz na koniec bloku, za wywołanie rekurencyjne? Tym razem duszek rysuje ale ma kłopoty z zakończeniem działania. Czy to możliwe, że blok dodany po wywołaniu rekurencyjnym zostanie zrealizowany.
Na końcu, za blokiem czekaj, dodaj blok zmień rozmiar o 5. Jak teraz wykonuje się skrypt? Jak powiększył się duszek?
Wywołuj blok wielospie dla rożnych kątów oglądaj otrzymane rysunki. Często są bardzo ładne.

Przedstaw działanie omawianych skryptów – uruchom opisany program korzystając z opisu na stronie czy w książce.