Spotkanie 2.

Projektowanie prostych algorytmów

1. Skarpety. W szufladzie, do której nie możemy zajrzeć, znajduje się bardzo dużo (około 500) różnych par skarpet. Skarpetki są porozłączane i wymieszane między sobą. W jednym ,,ruchu” możemy (na ślepo) wybrać z tej szuflady jedną skarpetkę. Naszym celem jest podanie schematu postępowania w efekcie którego zostaniemy z dokładnie jedną parą pasujących do siebie skarpet.

Kolejne kroki dobrego algorytmu mogą wyglądać np. tak:
krok 1. WYCIĄGNIJ  skarpetę  z  szuflady
krok 2. JEŻELI wśród już wyjętych nie ma pary, TO WRÓĆ do krok 1
krok 3. ODŁÓŻ znalezioną parę
krok 4. SCHOWAJ pozostałe skarpety do szuflady

A oto nieco inny sposób:
krok 1. WYCIĄGNIJ  pierwszą skarpetę  z  szuflady
krok 2. WYCIĄGNIJ  drugą skarpetę  z  szuflady
krok 3. JEŻELI nie jest to para, TO SCHOWAJ obie skarpety i WRÓĆ do krok 1
krok 4. ODŁÓŻ znalezioną parę

I jeszcze jedna możliwość:
krok 1. WYCIĄGNIJ  skarpetę  z  szuflady
krok 2. JEŻELI  szuflada nie jest pusta, TO WRÓĆ do krok 1
krok 3. WYBIERZ  parę spośród wszystkich skarpet
krok 4. ODŁÓŻ wybraną parę
krok 5. SCHOWAJ pozostałe skarpety do szuflady

Zadanie. Omów słabe i mocne strony każdego z tych algorytmów. Który z nich wg Ciebie jest najlepszy, a który najgorszy? Co to znaczy, że algorytm jest ,,lepszy” lub ,,gorszy”?

2. Wyrównywanie tekstu. Uruchamiamy edytor tekstu (Word lub Writer z pakietu OpenOffice). Napiszmy w pustym dokumencie jakieś krótkie zdanie – np. Dzisiaj jest kiepska pogoda. Zobaczmy jak działa operacja wyśrodkowania tego tekstu.

Zadanie. Zastanów się jakie informacje są niezbędne aby poprawnie wyśrodkować ten tekst. Jak myślisz, jaki algorytm wykonuje tutaj edytor. Spróbuj zapisać ten algorytm w kolejnych krokach zaznaczając co tworzy dane/obiekty wejściowe, a co wyjściowe. Tak samo spróbuj przeanalizować operację wyjustowania dłuższego tekstu w tym edytorze.

3. Znajdowanie hasła. Bawimy się w następującą grę. Bierzemy gruby słownik (leksykon lub encyklopedię), z którego  pewna osoba wybiera i zapamiętuje jedno z haseł. Zadaniem pozostałych jest odkrycie, które hasło zostało wybrane. W tym celu można zadawać pytania osobie znającej hasło ale tylko takie, na które można odpowiadać TAK lub NIE. Osoba ta odpowiada na te pytania zgodnie z prawdą. Jeżeli drużynie uda się odkryć hasło po zadaniu mniej niż 17 pytań – wygrywa; jeśli nie – wygrywa osoba, która hasło wybierała.

Zadanie (w grupach 3-4 osobowych)
Zagrajcie w tę grę. Następnie spróbujcie podać jakikolwiek sposób postępowania dla grupy, która odgaduje hasło.

Zadanie domowe
Jeżeli programujesz w Scratchu, to w grę podobną do tej z hasłami można zagrać z komputerem. W pliku Scratch – Odgadnij liczbę! znajduje się prosta gra na Scratcha. Duszek losuje liczbę z zakresu od 1 do 200 i naszym zadaniem jest ją odgadnąć w jak najmniejszej liczbie prób. Każda nieudana próba komentowana jest podpowiedzią, czy podana przez nas wartość jest mniejsza czy większa od wybranej przez komputer. Im mniejsza liczba prób, tym lepiej. Spróbuj obmyślić taki sposób gry, aby Twoja liczba prób była zawsze mniejsza niż 9.

Uwaga! Do programowania w Scratchu można posłużyć się wygodną (w ustawieniach dostępny jest język polski) i bezpłatną aplikacją typu on-line, dostępną pod adresem: https://scratch.mit.edu/projects/editor/?tutorial=getStarted
W aplikacji tej można też otworzyć powyższy plik .sb3

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *