Problem 1

Po jednej stronie strumyka znajduje się Pan Żaba. Bardzo chce dostać się na drugą stronę do księżniczki. Strumyk jest zbyt szeroki, żeby go przeskoczyć, a woda płynie zbyt prędko, aby przepłynąć. Na szczęście w strumieniu leżą kamienie, po których żaba może przeskakiwać. Kamienie ułożone są w linii, a Pan Żaba ponumerował je, licząc od zera. Na kamieniach siedzą muchy. Będąc na danym kamieniu, Pan Żaba może przeskoczyć maksymalnie o tyle kamieni, ile jest much na kamieniu, z którego skacze.

Pan Żaba zawsze zaczyna od kamienia zerowego, a uznaje się, że udało mu się przejść przez strumyk, jeśli wskoczy na ostatni kamień. 

Należy ustalić, czy dla danego przypadku przeprawa z jednej strony strumyka na drugą jest możliwa.

Poszukaj rozwiązania dla przykładowego układu much na kamieniach:

R1FYFWwAjTtbJ

Ilustracja przedstawia strumyk płynący od prawej do lewej strony. Na pierwszym planie znajduje się brzeg, dalej rzeka i drugi brzeg. Pomiędzy jednym a drugim brzegiem na szerokości strumyka rozmieszczone są kamienie. Znajdują się na nich muchy. Na pierwszym dwie. Na drugim i na trzecim po trzy. na czwartym jedna. Na piątym zero, Natomiast na szóstym, siódmym i ósmym po jednej musze.

Następnie zmodyfikuj rozwiązanie, by działało również dla dowolnych innych układów kamieni i much.

W jaki sposób podejść do rozwiązania problemu?

Określenie problemu

Na początku upewnijmy się, że wiemy, jaki problem musimy rozwiązać. Zrozumienie problemu jest kluczowe, aby móc przejść do następnych etapów. Powinniśmy również wskazać, co jest znane (jakie mamy dane) i czego nie wiemy (co ma być wynikiem), a także jasno sformułować cel problemu – zatem na tym etapie opracowujemy również specyfikację problemu.

W przypadku problemu zaprezentowanego w tym e‑materiale chodzi o określenie, czy dla danego układu kamieni i much na nich Pan Żaba może przeskoczyć strumień (wskoczyć na ostatni kamień) i tym samym dostać się do księżniczki na drugim brzegu, czy nie może tego zrobić.

Specyfikacja problemu:

Dane:

• kamienie – tablica liczb naturalnych; liczby much na kolejnych kamieniach

Wynik:

• w jednym wierszu: komunikat Udało się! lub Nie udało się... zależnie od tego, czy Pan Żaba był w stanie przekroczyć strumień

Definicja modeli i pojęć

Tworzymy modele i pojęcia, które pomagają nam reprezentować i analizować problem. Modele mogą być np.: abstrakcyjnymi strukturami danych, algorytmami czy równaniami.

Analizowane zadanie jest pod tym względem proste – ułożone kolejno kamienie, na których mogą (ale nie muszą) znajdować się muchy, które można policzyć co do sztuki, łatwo powiązać z tablicamitablica jednowymiarowatablicami jednowymiarowymi. Pozycja Pana Żaby będzie reprezentowana przez indeks elementu tablicy. Co robić, kiedy rozwiązanie nie jest tak oczywiste? Czasem pomaga zwizualizowanie problemu na kartce papieru, jak w poniższym przykładzie.

2 muchy
3 muchy
3 muchy
1 mucha
0 much
1 mucha
1 mucha
1 mucha

Na tym etapie dzielimy również problem na podproblemy. Po podzieleniu głównego problemu na części możemy stwierdzić, że podproblemem jest określenie, czy Pan Żaba może wskoczyć na dany kamień, czyli czy na kamieniu, z którego skacze, znajduje się odpowiednia liczba much. Przypomnijmy, że może to zrobić, jeśli liczba much na kamieniu, na którym siedzi, jest większa lub równa odległości liczonej w kamieniach między obecnym kamieniem, a tym, na który chce skoczyć.

Możemy zatem sprawdzić dla każdego kamienia to, jak daleko Pan Żaba może z niego skoczyć.

Znalezienie rozwiązania

Analizujemy problem, szukamy sposobów jego rozwiązania i opracowujemy strategię. Możemy wykorzystać różne techniki, znane algorytmy czy modele matematyczne. Celem jest opracowanie spójnego planu działania, który prowadzi do rozwiązania problemu.

W naszym rozwiązaniu skupimy się na wyszukiwaniu najdalszego kamienia, na który może skoczyć Pan Żaba w danym momencie. Za każdym razem, gdy Pan Żaba przeskoczy na kolejny kamień, zaktualizujemy maksymalny zasięg skoku na podstawie liczby much na obecnym kamieniu oraz to, na którym kamieniu znajduje się Pan Żaba.

Gdy numer kamienia, na którym znajduje się Pan Żaba, będzie równy indeksowi ostatniego kamienia, Panu Żabie uda się przeskoczyć strumień.

Zaprogramowanie rozwiązania

Zapisujemy zaprojektowane rozwiązanie, wykorzystując język programowania, pseudokod lub listę kroków.

Programujemy algorytmy, struktury danych i inne elementy potrzebne do implementacji rozwiązania.

W naszym rozwiązaniu wykorzystamy tablicę kamienie, która będzie przechowywać informacje na temat tego, ile much znajduje się na kolejnych kamieniach – indeksy odpowiadają kamieniom, a wartości przechowywane przez tablicę odpowiadają liczbie much. Wprowadzimy również zmienne nr_kamienia, ile_kamieni oraz max_zasieg.

Pierwsza z nich przechowuje informację na temat tego, jaki jest indeks kamienia, na którym znajduje się Pan Żaba, druga – ile jest kamieni w strumieniu, a ostatnia – na jaki najdalszy kamień Pan Żaba może wskoczyć.

Zapiszemy również pętlę, w której będziemy sprawdzać, czy indeks kamienia, na którym znajduje się Pan Żaba jest mniejszy niż indeks ostatniego kamienia oraz mniejszy lub równy maksymalnemu zasięgowi. Jeśli warunek jest spełniony, Pan Żaba wskakuje na kolejny kamień.

Testowanie rozwiązania

Po napisaniu kodu należy przetestować działanie programu.

Działanie programu powinniśmy sprawdzić dla różnych przypadków.

W serii Zadanie z gwiazdką rozwiązania testujemy dla podanych danych. Ponieważ odpowiedź dla tych danych jest podana, mamy możliwość sprawdzenia, czy otrzymany wynik jest z nią zgodny. Nie jest to jednak gwarancja tego, że program poprawnie działa również dla innych przypadków.

W przypadku przedstawionego w tym e‑materiale problemu możemy wyróżnić kilka przykładowych przypadków.

Strumień da się przeskoczyć

Tablica przechowuje kilka elementów (liczb naturalnych), np. liczby 2, 6, 0, 4, 2, 0, 2, 4.

Panu Żabie uda się przeskoczyć przez strumień, ponieważ pozwala na to liczba much na poszczególnych kamieniach.

Przykładowa przeprawa Pana Żaby:

• Pan Żaba zaczyna od pierwszego kamienia (znajdują się na nim dwie muchy).

• Pan Żaba może przeskoczyć na drugi kamień lub trzeci.

• Na trzecim kamieniu nie ma much, więc wiemy, że Pan Żaba na niego nie wskoczy.

• Na drugim kamieniu jest sześć much – akurat tyle, by Pan Żaba mógł od razu wskoczyć na ostatni kamień i tym samym skończyć swoją przeprawę.

Przykładowy ciąg wejściowy:

2, 6, 0, 4, 2, 0, 2, 4

Wynik działania programu:

Udało się!

Strumienia nie da się przeskoczyć

Tablica przechowuje kilka elementów (liczb naturalnych), np. liczby $1, 3, 1, 1, 0, 0, 2, 0$.

Panu Żabie nie uda się przeskoczyć przez strumień, ponieważ nie pozwala na to liczba much na poszczególnych kamieniach.

Przykładowa przeprawa Pana Żaby:

• Pan Żaba zaczyna od pierwszego kamienia (znajduje się na nim jedna mucha).

• Pan Żaba przeskakuje na drugi kamień, bo tylko on jest w jego zasięgu.

• Na drugim kamieniu są trzy muchy. Może zatem przeskoczyć na kamień trzeci, czwarty oraz piąty.

• Nie wskoczy na kamień piąty, bo nie ma na nim much. Wskakuje na kamień czwarty, ponieważ jest na nim tyle samo much, co na kamieniu trzecim, ale jest dalej.

• Niestety, na kamieniu czwartym jest tylko jedna mucha, a na kamieniu piątym nie ma much, więc Pan Żaba nie może przekroczyć strumienia.

Przykładowy ciąg wejściowy:

1, 3, 1, 1, 0, 0, 2, 0

Wynik działania programu:

Nie udało się...

W strumieniu jest wyłącznie jeden kamień

Tablica przechowuje wyłącznie jeden element (liczbę naturalną), np. liczbę 7.

Panu Żabie uda się przeskoczyć przez strumień, ponieważ od razu znajduje się na ostatnim (a zarazem pierwszym) kamieniu. Zwróć uwagę na to, że nawet jeśli na kamieniu nie ma much, Pan Żaba przeskoczy przez strumień – za każdym razem zaczyna na pierwszym kamieniu. W tym przypadku jest to również ostatni kamień.

Przykładowy ciąg wejściowy:

7

Wynik działania programu:

Udało się!

W strumieniu nie ma kamieni

Tablica nie przechowuje żadnego elementu – Panu Żabie nie uda się przeskoczyć przez strumień, ponieważ nie może znaleźć się na ostatnim kamieniu (nie ma również kamienia, od którego mógłby zacząć przeprawę).

Wynik działania programu:

Nie udało się...

Słownik