Co to jest algorytm? Czyli gra w jajka.

Algorytm to ciąg instrukcji koniecznych do wykonania zadania. Bla, bla, bla. A można to wytłumaczyć lepiej. Na przykład grą w zrzucanie jajek.

Pierwsze zajęcia o algorytmach wcale nie muszą być ani trudne, ani nudne. A jednak często są nudne i trudne jednocześnie. Nie musi tak być, co pokazuję w dzisiejszym wpisie. Proponuję w nim wprowadzać pojęcie algorytmu na przykładzie (interaktywnej) gry w jajka. To dość znana zagadka, której utrudnienie pojawiło się kiedyś na Olimpiadzie Informatycznej. Spokojnie jednak: całość powinny być w stanie zrozumieć nawet średnio ambitni uczniowie szkoły podstawowej.

Gra w jajka

Pewna firma zajęła się produkcją genetycznie zmodyfikowanych jajek z nano-powłoką, która znacznie zwiększa ich wytrzymałość na stłuczenie. Firma ta chce uczciwie zareklamować swój produkt i konkretnie podać, jaka jest rzeczywista wytrzymałość ich produktu. Zostało Ci powierzone zadanie wyznaczenia tej wytrzymałości. Do tego celu masz trzy identyczne jajka oraz stupiętrowy wieżowiec. Pierwsze jajko zrzucasz z setnego piętra i niestety się zbiło (a więc wytrzymałość jajka to mniej niż 100 pięter). Pozostały Ci jeszcze dwa jajka. Możesz samodzielnie zadecydować, z którego piętra je zrzucasz. Po każdym zrzuceniu jajka otrzymujesz informację, czy przetrwało, czy się zbiło. Jeżeli jajko przetrwało, możesz użyć go ponownie do kolejnych prób, ale jeżeli się zbiło, to zostało Ci o jedno jajko mniej.

Nieco bardziej precyzyjnie: możesz założyć, że istnieje pewna graniczna wartość (numer piętra), że zrzucanie z tego piętra lub niżej powoduje przetrwanie jajka, zaś zrzucenie jajka z choćby o jednego piętra wyżej powoduje jego zbicie. Celem gry jest ustalić tę wartość graniczną, którą roboczo nazwiemy wytrzymałością jajka. Chcemy to zrobić w jak najmniejszej liczbie prób (zrzutów).

Co to jest ten algorytm?

Uczniom można wytłumaczyć najpierw zasady gry, a potem pozwolić im grać. Kilka minut nieudanych prób, powinny w końcu zaowocować wymyśleniem pewnego (suboptymalnego rzecz jasna) rozwiązania. Rozwiązaniem jest właśnie algorytm - taki inteligentny sposób wyboru pięter, żeby osiągnąć cel ustalenia wytrzymałości jajek. Uważam, że znacznie lepiej jest zacząć od czegoś intuicyjnego i na końcu tylko dodać, że: To co robiliśmy, to było właśnie projektowanie algorytmów. Dużo lepszy pomysł niż tłumaczenie “na sucho”, które dobrego ucznia nie zaciekawi, a które do słabego ucznia nie dotrze.

Jak wygrać w tę grę?

Grę można rozwiązać optymalnie w 14 ruchach.

Spróbujmy najpierw zrozumieć co znaczy powyższe zdanie. Łatwo zorientować się po chwili interakcji z grą, że wytrzymałość jajek dobierana jest przez grę złośliwie:

• gra wie, jaką informację udało się zdobyć graczowi i nie pozwala mu zgadywać (jeżeli ze zdobytych przez gracza nie wynika jednoznaczne piętro, to próba zgadnięcia jakiejkolwiek wartości zawsze skończy się porażką),
• gra dobiera swoje odpowiedzi dla gracza (czyli czy jajko się zbiło, czy przerwało próbę) w sposób taki, który maksymalizuje liczbę prób, niezbędnych do ustalenia odpowiedzi.

Innymi słowy: to wcale nie jest tak, że gra na początku ustala wytrzymałość jajek, a potem uczciwie odpowiada graczowi zgodnie z tą nieznaną mu wartością. Gra zapamiętuje natomiast pytania, które zadał gracz i udziela odpowiedzi, które są niesprzeczne z wcześniej udzielonymi.

Jeżeli więc mówię, że grę można wygrać optymalnie w czternastu ruchach to mam na myśli:

• że istnieje strategia dla gracza, która niezależnie od złośliwości gry i doboru jej odpowiedzi, gwarantuje, że uzyskamy odpowiedź wykonując co najwyżej 14 zrzutów jajek,
• dla każdej strategii gracza, istnieje taki sposób odpowiadania mu przez grę, że wymusi to zadanie co najmniej 14 pytań.

Udowodnię oba te fakty.

Algorytm na 14 ruchów

Zacznijmy najpierw od pokazania, że 14 ruchów wystarczy. Kluczowa obserwacja jest taka, że ponieważ mamy tylko dwa jajka, to jeżeli stracimy pierwsze z nich, to ostatnim jajkiem trzeba już próbować piętra po kolei. Przykładowo: jeżeli sprawdziliśmy, że pierwsze jajko nie zbiło się na wysokości $20$ pięter, a zbiło się na wysokości $40$ pięter, to drugim jajkiem musimy spróbować wszystkie piętra $21, 22, \ldots, 39$, po kolei. Jeżeli którekolwiek z nich zostanie pominięte, to gra może nam złośliwie odpowiedzieć (i oczywiście zrobi to!), że ostatnie jajko się zbiło. Wtedy zostajemy z przedziałem co najmniej dwóch możliwości na wytrzymałość jajek, a nie mamy już jajek do dalszego próbowania. Gra pozwoli nam wpisać jakąś liczbę jako wytrzymałość jajka, ale niezależnie co tam wpiszemy, otrzymamy zwrotkę, że jest to zła odpowiedź (i że to ta inna, też możliwa odpowiedź była poprawna).

Wiemy już jak należy działać z ostatnim jajkiem. Pytanie co zrobić z pierwszym? Chciałoby się je zrzucić z jak najwyższego piętra, żeby w razie, gdyby się nie zbiło, odsiało nam to jak najwięcej pięter (jajko ma wtedy co najmniej taką wytrzymałość, jak piętro, z którego próbowaliśmy). Z drugiej strony, jeżeli zrzucimy zbyt wysoko, gra odpowie nam, że jajko się zbiło i wtedy zostaniemy zmuszeni do zrzucania drugiego jajka co jedno piętro, co wymusi dużą liczbę ruchów.

Pierwsze jajko zrzucamy więc z piętra numer $14$. Jeżeli jajko się zbije to super, bo potrzeba nam jeszcze trzynastu dodatkowych ruchów drugim jajkiem (zrzuty z pięter $1, 2, 3, \ldots, 13$), żeby wyznaczyć jego wytrzymałość. Razem 14 ruchów, tak jak obiecałem. A jeżeli się nie zbije to zostało nam jeszcze $86$ potencjalnych wytrzymałości jajek do sprawdzenia.

Gdyby jajko się nie zbiło, wtedy kolejna próba tym samym jajkiem jest z piętra numer $27 = 14 + 13$. Jeżeli jajko się zbije to również fajnie, bo wtedy wiemy, że wytrzymałość jajka jest gdzieś między $14$ a $26$ i da się to ustalić drugim jajkiem w dwanaście prób jakie nam jeszcze zostały (na razie wykonaliśmy dwie pierwszym jajkiem). A jeżeli jajko się nie zbije to też dobrze, bo zostało nam już tylko $73$ potencjalne piętra, które mogą stanowić wytrzymałość jajka.

Gdyby pierwsze jajko nadal było całe, kolejna próba będzie z piętra $39 = 14 + 13 + 12$, jeszcze kolejna z piętra $50 = 14 + 13 + 12 + 11$ i tak dalej. Ostatecznie, ponieważ $14 + 13 + 12 + \ldots + 3 + 2 + 1 = 15 \cdot 7 = 105 > 100$, pierwsze jajko się kiedyś zbije, a wtedy drugim jajkiem doprowadzimy do sukcesu, za każdym razem nie przekraczając czternastu ruchów.

Pokazaliśmy, że istnieje algorytm, który rozwiązuje zadanie wykonując 14 ruchów.

Brak algorytmu na 13 ruchów

Gdyby chcieć mieć strategię, która gwarantuje nie przekroczenie limitu trzynastu ruchów, trzeba by pierwsze jajko zrzucić z piętra $13$ lub niżej. Istotnie, gdyby spróbować pierwsze jajko zrzucić z wyższego piętra, gra mogłaby nam odpowiedzieć, że jajko się zbiło. A wtedy w pozostałych dwunastu ruchach nie da się już ustalić na pewno wytrzymałości, mając do dyspozycji już tylko ostatnie jajko.

Analogicznie można pokazać, że gdyby to pierwsze jajko się nie zbiło, to wtedy druga próba pierwszym jajkiem może być z piętra co najwyżej $13 + 12 = 25$, trzecia próba z piętra $13 + 12 + 11 = 36$, i tak dalej. A ponieważ $13 + 12 + 11 + \ldots + 1 = 91$, to jeżeli będziemy tak próbować, gra może nam ciągle odpowiadać nie zbiło się. A wtedy po trzynastu próbach będziemy dopiero na piętrze numer $91$ i nie uda się nam ustalić wytrzymałości jajek bez dodatkowych prób.

Scenariusz lekcji i podsumowanie

Byłbym za tym, żeby wprowadzenie do tego czym jest algorytm realizować za pomocą następującego scenariusza:

• tłumaczymy uczniom zasady gry w jajka,
• pozwalamy im pograć (przegrać) w grę,
• po wyczuciu modelu, formalizujemy model (np. tłumaczymy jak działa złośliwy adwersarz, z którym mamy do czynienia i co próbujemy optymalizować - liczbę ruchów) ,
• próbujemy formalizować myśli uczniów (naprowadzając ich np. na strategię zrzucania pierwszego jajka co $10$ pięter, a drugiego jajka po kolei - uczniowie są w stanie sami wymyślić coś podobnego, może z inną stałą niż $10$),
• pozwalamy w końcu wygrać grę (żeby uczniowie odnieśli i poczuli jakiś sukces),
• mówimy, że to co wymyślili to był właśnie algorytm.

W tym miejscu 45-minutowa lekcja zapewne się kończy. Dopiero na drugich zajęciach można wrócić do tej gry, próbować zapisywać algorytmy formalnie (np. najpierw w postaci sztywnej listy kroków, bez pętli). Kiedyś można ten sam algorytm przepisać na schemat blokowy, program lub cokolwiek innego. A później: wprowadzając pętle można zapisać to czyściej, bez umieszczania żadnych innych stałych.

Na lekcję matematyki można by zaproponować wyprowadzenie “zgadniętej” wartości $14$, dla wejściowej wysokości wieżowca równej $100$ (lub sformalizowanie pomysłu, żeby dojść do tego, że jest ona rzędu $\sqrt{2N}$). Ale to już dla ambitniejszych. A dla mniej ambitnych… no cóż: to co zrobiliśmy i tak jest dużo mądrzejsze niż tłumaczenie, że algorytm to taki przepis postępowania, a instrukcja warunkowa to na przykład jeżeli chcesz babkę kakaową, to dorzuć kakao do ciasta. Uczniowie dostają konkretny, interaktywny i ciekawy przykład zamiast wykładu o niczym. Mniej ambitni również powinni być bardziej zadowoleni. A co Wy o tym myślicie?