Spotkanie 23.

Omówienie zadań z zawodów CMI – część III

Zadanie Zabawy w labiryncie

Zadanie jest niezbyt trudnym ćwiczeniem sprawdzającym umiejętność posługiwania się czujnikiem dotyka koloru i przemieszczania duszka w układzie współrzędnych. Ruch o jedno pole polega na zmianie odpowiedniej współrzędnej (dla ruchu lewo-prawo: współrzędna x, dla ruchu góra-dół: współrzędna y) pozycji Bajtusia o wartości \pm30. Oczywiście w programie pojawi się kilka instrukcji warunkowych powiązanych ze wspomnianymi czujnikami dotyku koloru i przy odczycie kolejnych kroków z listy DANE. Kolory w czujnikach należy pobrać (tzw. pipetą) z przygotowanej w szablonie planszy. Badanie, czy Bajtuś może wykonać dany ruch można zaprogramować robiąc małe ,,oszustwo”: duszek wchodzi na dane pole (nie wiedząc jeszcze czy taki ruch jest dozwolony), sprawdza czy nie dotyka koloru zielonego (kłujący ostrokrzew) a jeśli tak, to cofa się do wcześniejszej pozycji.

Aby zwiększyć czytelność rozwiązania wygodnie jest posłużyć się swoimi blokami (podprogramami), które będą np. realizowały ruch w danym kierunku. Przykładowy blok (wybieramy sekcję Moje bloki, a później klikamy przycisk Utwórz blok i podajemy jego nazwę) dla ruchu na dół może wyglądać tak jak pokazano poniżej.

Ćwiczenie 8. W analogiczny sposób przygotuj bloki realizujące ruch Do_góry, W_lewo oraz W_prawo.

Ważnym elementem programu jest zakończenie ruchu Bajtusia gdy tylko osiągnie on pole czerwone. Można (podobnie jak robiliśmy to w zadaniu Miękkie lądowanie) wykorzystać zmienną flagową u_celu. Jej wartość będzie równa na początku zero, a gdy tylko duszek dotrze do pola czerwonego, to zmieniamy jej wartość na 1.

Główna pętla programu powinna wykonywać się co najwyżej tyle razy ile wynosi długość listy DANE ale powinna się zakończyć gdy tylko będzie spełniony warunek u_celu = 1. Jeżeli bieżącą pozycję na liście DANE oznaczymy zmienną poz, to można zastosować instrukcję w postaci

Zadanie 6. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Zabawy w labiryncie.

Przykładowe rozwiązanie jest zawarte w poniższym pliku.
Zabawy w labiryncie (plik .sb3)


Zadanie Kółko brydżowe

Na początku wyjaśnijmy na czym polega zadanie. Wejściowa lista DANE zawiera liczby (w losowej kolejności) oznaczające poziom zaawansowania (ocenę umiejętności) gry w brydża uczniów pana Bajtosława. Jeśli dwójka uczniów o umiejętnościach a oraz b tworzy drużynę (do gry w brydża bowiem potrzeba dwóch par graczy), to jej poziom gry wynosi \min\{a,b\} czyli jest mniejszą z wartości a lub b. Nauczyciel Bajtosław chciałaby aby przy 4-osobowych stolikach do gry zasiadło jak najwięcej jego uczniów ale w taki sposób, aby przy każdym stoliku obie tworzące go drużyny miały jednakową siłę gry. Należy napisać program, który tę największą liczbę ,,sprawiedliwych” stolików obliczy.

Spróbujmy najpierw na konkretnych danych ręcznie obliczyć kilka przykładów.

Ćwiczenie 9. W jaki sposób utworzyć największą możliwą liczbę stolików do turnieju, gdy poszczególnie uczniowie reprezentują niżej podane poziomy gry?
  • 7, 9, 3, 4, 5, 3, 3, 7, 9, 9, 7, 7
  • 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5
W pierwszym przypadku można uzyskać maksymalnie 2 ,,sprawiedliwe” stoliki, utworzą je np. drużyny (3, 3) i (3, 4) oraz (7, 9) i (7, 9).
W drugim przypadku dostaniemy 3 stoliki: (1, 1) i (1, 2), kolejny stolik (2, 3) i (2, 3) i ostatni: (4, 4) i (4, 5).


Widać z tych przykładów, że o wiele wygodniej zestawia się odpowiednie pary drużyn, gdy informacje o uczniach są uszeregowane – np. od najmniejszej do największej siły gry. Dobrym pomysłem może więc być takie ustawienie wartości z listy DANE, aby one też tworzyły uporządkowany ciąg liczb. Operację taką nazywa się w informatyce sortowaniem.

Ćwiczenie 10. Zastanów się w jaki sposób posortować liczby podane w liście DANE. Spróbuj napisać odpowiedni program, który dla dowolnej tablicy wykona taką operację.

Jest wiele różnych sposób wykonania operacji sortowania na danej liście liczb. Jeden z łatwiejszych polega na wybraniu największej liczby z listy i przeniesieniu jej na koniec, z kolei starą wartość z ostatniej pozycji listy wstawiamy w miejsce gdzie było znalezione maksimum. Następnie całą operacją powtarzamy ale już z listą krótszą o jedną pozycję: wybieramy największą liczbę zamieniamy są z liczbą z końca tej krótszej listy (czyli z pozycją z miejsca przedostatniego w liście wyjściowej). Powtarzając ten krok tyle razy ile wynosiła początkowa długość całej listy (a nawet o jeden raz mniej), dostaniemy posortowaną (czyli uporządkowaną rosnąco) listę liczb.

Przykładowy program sortujący Sortowanie (plik .sb3)Pobierz

Zastanówmy się teraz, w jaki sposób można optymalnie tworzyć zespoły tak, aby zmaksymalizować liczbę ,,sprawiedliwych” stolików. Załóżmy na chwilę, że najsłabszy poziom gry wśród wszystkich uczniów wynosi 1. Zauważmy, że jeśli jedynka jest tylko jedna, to uczeń taki nie będzie mógł usiąść przy żadnym stoliku – możemy więc go odrzucić zmniejszając listę DANE. Przy co najmniej dwóch osobach grających na poziomie 1, można utworzyć dwie drużyny (1, ktoś1) oraz (1, ktoś2), które dadzą obsadę jednego pełnego stolika. Oczywiście należy rozsądnie wybrać uczniów ktoś1 i ktoś2. Wydaje się, że najlepiej jest wybierać je spośród kolejnych względem jednakowej siły gry grup uczniów, których jest nieparzyście wiele. W ten sposób znów zmniejszymy długość listy DANE o 4 pozycje. Powtarzamy całą procedurę do momentu aż na liście będą mniej niż 4 liczby – z nich już się żadnego stolika nie obsadzi.

Ćwiczenie 11. Opisaną metodę działając krok po kroku zastosuj do obu powyższych przykładów i do przykładu podanego w treści zadania.

Zauważmy jeszcze, że same wartości liczbowe poziomu gry poszczególnych uczniów nie są istotne – ważna jest liczba ile jest uczniów na konkretnym poziomie umiejętności oraz uszeregowanie ich od najsłabiej do najlepiej grających. Można więc w kolejnym etapie rozwiązania (po posortowaniu) utworzyć nową listę, która te krotności będzie zawierała. Przykładowo, dla listy danych (już uporządkowanych rosnąco):

3, 3, 4, 5, 7, 7, 7, 7, 9, 9, 9

otrzymamy zupełnie nową listę krotności: 2, 1, 1, 4, 3 (bo są dwie trójki, jedna czwórka, jedna piątka, cztery siódemki i trzy dziewiątki).

Ćwiczenie 12. Napisz program, który dla posortowanej listy DANE wypełni nową (początkowo pustą) listę utworzy KROTNOŚCI w opisany powyżej sposób.

Teraz algorytm jest już łatwy do napisania: analizujemy pierwszy element z listy krotności – jeśli jest on równy 1, to go odrzucamy i zajmujemy się następnym. Jeśli jest większy od jeden, to szukamy dwóch kolejnych nieparzystych wartości na liście i je zmniejszamy o 1, a pierwszą wartość zmniejszamy od 2. W ten sposób tworzymy jeden ,,sprawiedliwy” stolik brydżystów. Jeśli nieparzystych wartości już na liście nie ma, to do kolejnych stolików dobieramy osoby od końca listy (kolejne najsilniejsze).

Zadanie 7. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Kółko brydżowe.

Dodaj komentarz

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