Spotkanie 24 – ostatnie…

Szyfry…

Komputery świetnie nadają się do wykorzystywania jako maszyny szyfrujące. Szyfrowanie wiadomości, jak wiemy, może być świetną zabawą, a czasami jest wręcz koniecznością (jak np. przy wrażliwych transakcjach bankowych).

Różnych rodzajów szyfrów jest bardzo dużo – my spróbujemy przedstawić kilka z nich i przy okazji spróbujemy zaprząc komputer (pisząc stosowny program), aby nam w tym pomógł.

GA-DE-RY-PO-LU-KI

Ten rodzaj szyfrowania zna każdy zuch! Wiadomość do zakodowania analizujemy litera po literze i gdy natrafimy na literkę pasującą do którejś pary hasła GA-DE-RY-PO-LU-KI, to zamieniamy ją na drugą literę z tej pary. Jeśli litera (znak) nie pojawia się w haśle, to nie zmieniamy jej. Przykładowo słowo: cukierek zaszyfrowane w ten sposób brzmi: clikdydi.

Ćwiczenie 1. Zakoduj opisaną metodą zdanie: Nikt prawie nie wie, dokąd go zaprowadzi droga, póki nie stanie u celu. Rozkoduj (zdeszyfruj) hasło: Ngjełlżdj tywg tg ypbptg, itóydj skę wcgud nkd zgczrng.

To jest dość wygodny sposób szyfrowania, a jego dodatkowymi dwiema zaletami są: 1. jeśli napiszemy program, który pozwoli nam łatwo kodować wiadomości (program szyfrujący), to jednocześnie otrzymamy program deszyfrujący do odczytywania zakodowanych przekazów (dlaczego?); 2. Możemy zmieniać klucz! Kluczem może być dowolne słowo (zdanie) o długości parzystej, w którym litery nie powtarzają się – np. SK-RZ-YŻ-OW-AN-IE. Dobrze w roli takich haseł spisują się tzw. panagramy – czyli zdania (wypowiedzi), w których każda litera alfabetu pojawia się dokładnie jeden raz – np. Pędź już i skleć z tych form główną baśń. Oczywiście takie hasło należy podzielić na 16 par sąsiadujących liter i pominąć wszystkie odstępy pomiędzy wyrazami.

Przykładowo, zaszyfrowana tym ostatnim kluczem pewna wiadomość, wygląda tak: Ókćtkysf ulky o mpsbhc hćgfóżlsb. Źebylłf ąbelit ul rtz hćpkyf. Spróbujcie ją odkodować.

Pomocny w wykonaniu powyższych ćwiczeń może być program napisany w Scratchu. Wykorzystuje on listę o nazwie KLUCZ do przechowywania ustalonego hasła kodującego (każda litera hasła jest osobnym elementem listy). Gdy podamy treść do zakodowania (lub zdekodowania), to program sprawdza całą tą treść znak po znaku i wyszukuje odpowiednią literę na liście – gdy ją znajduje, to zmienia ją zgodnie z regułami szyfrowania; jeśli nie – pozostawia bez zmian.

Gotowy szyfrator w Scratchu. Szyfrator (plik .sb3)Pobierz
KODY ASCII

W Pythonie lub C/C++ do tworzenia programów obsługujących szyfry możemy wykorzystać standardowy mechanizm w jaki komputery zapamiętują ciągi znaków. Niemal każdy znak/symbol dostępny z klawiatury komputera ma swój kod liczbowy – jest to tzw. kod ASCII (czyt. aski). Przykładowo wielka litera B ma swój kod ASCII równy 66, zaś znakowi tylda ~ odpowiada kod ASCII o wartości 126. Używając funkcji ord() lub chr() w Pythonie można łatwo sprawdzić jaki kod ASCII ma dany znak:

print(ord('B'))
print(ord('~'))
print(chr(176))

Tak naprawdę wspomniane kody ASCII to standard już nieco przestarzały i obecnie funkcjonują (działające na podobnej zasadzie) standardy, które obsługują znacznie więcej znaków. Zestaw ASCII ma ich tylko 128 (czyli poprawne wartości kodów do liczby od 0 do 127 włącznie). Jednak nazwa ASCII tak się zadomowiła w informatycznym żargonie, że do tej pory jest najczęściej używanym terminem w odniesieniu do kodowania znaków (choć często jest to nieścisłe określenie).

Takie naturalne przyporządkowanie znak-liczba daje wygodny sposób manipulacji i tworzenia szyfrów. Przykładowo tzw. szyfr Cezara polegający na przesunięciu zestawu liter alfabetu o stałą ustaloną wartość. Przykładowo (rozważamy alfabet łaciński bez polskich znaków charakterystycznych – tzw. diakrytycznych), jeżeli przesunięcie ma wynosić 3 znaki, to każdej literce A będzie odpowiadać literka D (A\to B\to C\to D), literce G odpowiadać będzie J (G\to H\to I\to J), zaś końcowe litery alfabetu przejdą na początkowe: znakowi Y będzie przyporządkowany znak B (Y\to Z\to A\to B). Każdorazowo dokonujemy przesunięcia o 3 litery.

Ćwiczenie 2. Zaszyfruj szyfrem Cezara z przesunięciem 10 (całego alfabetu języka polskiego) następującą wiadomość: Głupota jest początkiem mądrości.

Zadanie. Napisz w Pythonie program do kodowania wiadomości szyfrem Cezara. Na początek możesz wykorzystać wspomniane wyżej funkcje chr() i ord() i działać tylko na 26-literowym alfabecie łacińskim. Zakodowaną wiadomość (bez wartości przesunięcia) możesz pozostawić w komentarzu \ddot\smile

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.

Spotkanie 22.

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

Zadanie Tak i wspak

Zadanie to jest swego rodzaju ćwiczeniem dotyczącym manipulowania listami w Scratchu. Program, który mamy napisać powinien całą listę DANE skopiować do pustej listy WYNIKI – tyle, że w odwrotnej kolejności: element ostatni ma trafić na miejsce pierwsze, element przedostatni na miejsce drugie itd. aż element z pozycji pierwszej trafi na pozycję ostatnią. Naturalnym narzędziem będzie więc użycie jednej pętli. Będzie ona odpowiedzialna za przeglądanie listy DANE w kolejności od ostatniego do pierwszego jej elementu i kopiowanie tych elementów do listy WYNIKI w zwykłej kolejności.

Potrzebujemy zmiennej, która będzie wskazywała na kolejne (w jednej liście – od końca, w drugiej – od początku) elementy obu list. Nazwijmy ją numer. To, co koniecznie trzeba zauważyć, to związek pomiędzy obiema pozycjami na listach i zmienną numer. Dobrze jest sobie to zilustrować w postaci tabeli. Jeśli długość listy DANE jest równa N, to mamy następującą sytuację:

Tabela DANE (od końca do pocz.)NN-1N-221
Tabela WYNIKI (od pocz. do końca)123N-1N

Widać teraz, że jeśli bieżącą pozycją na liście DANE jest wartość numer, to odpowiada jej pozycja (N+1-numer) na liście WYNIKI. W naszym przypadku zamiast N możemy użyć gotowej wartości długość DANE. Główna instrukcja kopiująca może więc wyglądać np. tak:

Zadanie 3. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Tak i wspak.

Gotowy program – przykładowe rozwiązanie zadania.


Zadanie Kocia korespondencja

Zadanie jest podobne do poprzedniego. Tym razem jednak, poza odwróceniem kolejności elementów listy DANE, trzeba rozbić te elementy na pojedyncze znaki i też odwrócić ich kolejność. Schematycznie więc trzeba będzie wykorzystać dwie zagnieżdżone (czyli jedna wystąpi wewnątrz drugiej) pętle.

Na początek spróbujmy zrobić następujące ćwiczenie.

Ćwiczenie 6. Napisz program, program, który rozbije jeden dany wyraz na poszczególne litery (znaki) i wpisze je odwrotnej kolejności (od końca) do początkowo pustej tablicy WYNIKI. Wyraz może być przypisany do zmiennej na początku programu. W rozwiązaniu należy użyć poleceń (sekcja wyrażenia): długość słowo oraz litera nr z słowo.

Zmienna słowo zawiera wyraz do rozbicia i odwrócenia; wcześniej czyścimy listę WYNIKI. Używamy też zmiennej znak, która zmienia się kolejno od wartości N do 1, gdzie N jest długością wprowadzonego wyrazu. Główna pętla, która wykonuje się N-krotnie, kopiuje jedną literę (z pozycji znak) do listy WYNIKI i zmniejsza o jeden wartość zmiennej znak.


Mając rozwiązanie zadania Tak i wspak i odpowiedź do ostatniego ćwiczenia, wyjściowe zadanie nie powinno już teraz sprawić dużego kłopotu.

Zadanie 4. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Kocia korespondencja.

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


Zadanie Poczekalnia

Zbierzmy najpierw wszystkie spostrzeżenia, które mogą być przydatne podczas projektowania algorytmu. Nietrudno zauważyć, że wejściowa lista DANE powinna być długości parzystej: na każdego pacjenta (Zwykłego lub Priorytetowego) musi przypadać jedno przyjęcie do Gabinetu. Zatem dla listy DANE długości 2N lista WYNIKI będzie miała długość o połowę mniejszą (czyli N).

Wyobraźmy sobie teraz cały proces obsługi opisany w zadaniu. Ustalmy dodatkowo, że przychodnia dysponuje dwiema odrębnymi poczekalniami – dla obu rodzajów pacjentów. Osoba przychodząca do lekarza (Z lub P) od razu udaje się do właściwej poczekalni i jeśli następuje przyjęcie do gabinetu (G), to sprawdza się, czy poczekalnia dla pacjentów priorytetowych jest pusta, czy nie. Jeśli nie – do lekarza przyjmowany jest kolejny oczekujący pacjent P, a jeśli jest pusta, to lekarz przyjmuje kolejnego pacjenta Zwykłego. To oznacza, że w naszym programie też możemy wykorzystać dwie kolejki (listy) dla poszczególnych rodzajów pacjentów. Listy te będą przechowywać numer danego pacjenta, czyli liczbę oznaczającą który z kolei jest to pacjent odwiedzający tego dnia przychodnię (numeracja ta jest wspólna dla wszystkich pacjentów). Te właśnie liczby należy później wypisać do listy WYNIKI.

Ćwiczenie 7. Utwórz dwie puste listy (poczekalnie) POCZ_Z i POCZ_P, a następnie utwórz zmienną numer. Dla listy DANE takiej jak w zadaniu, napisz program, który wypełni listy-poczekalnie numerami kolejnych pacjentów (tzn. ignorujemy na razie elementy G z listy wejściowej).

Główna pętla powtórz służy do przejrzenia całej listy DANE, musi się więc wykonać tyle razy ile wynosi długość tej listy. Przeglądamy elementy od początku używając zmiennej wpis. Gdy napotkamy wartość Z lub P (wyrażenie warunkowe jeżeli), to zwiększamy o jeden zmienną numer i wpisujemy ją do odpowiedniej poczekalni. Całość może wyglądać tak jak poniżej.


Ostateczne rozwiązanie oczywiście nie może ignorować wezwań lekarza do gabinetu (G). Przy przeglądaniu listy DANE należy wyodrębnić odpowiednie zachowanie się programu gdy napotka taki właśnie wpis. I tu są dwie możliwości:
  • poczekalnia POCZ_P nie jest pusta – wtedy należy przyjąć pacjenta z tej właśnie grupy o najniższym numerze (bo ten pojawił się w tej grupie oczekujących najwcześniej) i usunąć go z poczekalni;
  • poczekalnia POCZ_P jest pusta – wtedy należy przyjąć pacjenta o najniższym numerze z drugiej poczekalni i go stamtąd usunąć.

      Pustość poczekalni (listy) sprawdzamy wyrażeniem warunkowym jeżeli długość POCZ_P > 0. Ten fragment kodu powinien więc wyglądać tak:

      Zadanie 5. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Poczekalnia.

Spotkanie 21.

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

Najbliższe dwa spotkania poświęcimy zadaniom z pierwszego etapu zawodów CMI, który zakończył się 10. kwietnia. Kolejne istotnie elementy rozwiązania danego problemu będą przedstawione w postaci ćwiczeń tak, aby każdy z Was mógł ,,poskładać” wszystko w całość i raz jeszcze zmierzyć się z tymi zadaniami. Przypominam, że treści zadań są dostępne na wpisie spotkanie 19.

Zadanie Skarb piratów
Wypiszmy główne założenia:
  • znamy liczbę piratów p\geqslant 2,
  • znamy: liczbę sztuk złota z\geqslant 0, liczbę sztuk srebra s\geqslant 0 i liczbę sztuk klejnotów k\geqslant 0,
  • mamy obliczyć ile łupów każdego rodzaju otrzymają piraci i ile ich przypadnie Długiemu Johnowi.
Piraci ustalili, że dobra mają być – w miarę możliwości – dzielone po równo, a ewentualne reszta dodatkowo przypada hersztowi. Ewentualne wątpliwości wyjaśnia przykład: przy p=10 piratach i s=61 sztukach srebra każdy pirat otrzyma po 6 sztuk srebra i jeszcze pozostałą ostatnią część dostanie Długi John.

Ćwiczenie 1. Oblicz po ile sztuk łupów każdego rodzaju otrzymają piraci i ich herszt dla danych: p=12, z=103, s=72 i k=1001.

Wykonujemy dzielenie z resztą: 103:12=8 i reszta 7 – piraci otrzymają po 8 sztuk złota, a herszt razem 8+7=15 sztuk złota.
Podobnie dla srebra: 72:12=6 i reszta 0 – wszyscy (także Długi John) otrzymają po 6 sztuk srebra.
Klejnoty: 1001:12=83 i 5 reszty, zatem piraci dostaną po 83 klejnoty, a szef dostanie ich 83+5=88 sztuk.

W scratchu należy więc zaprogramować dzielenie z resztą i odpowiednie wartości wpisać do lity WYNIKI. Resztę z takiego dzielenia uzyskamy dzięki komendzie

Gorzej jest z szybkim otrzymaniem całkowitego ilorazu. Działanie dzielenia dostępne w wyrażeniach zwraca zawsze dokładną wartość ilorazu w postaci liczby dziesiętnej. Należy więc zadbać o to, aby dzielenie było wykonalne bez reszty. W tym celu od danej liczby bogactw (np. klejnotów k) odejmujemy odpowiednią resztą i dopiero dzielimy. Czyli potrzebujemy wyrażenia postaci

Ćwiczenie 2. Powyższy fragment programu oblicza wynik dzielenia całkowitego (bez reszty) dla danych wartości k i p – tyle klejnotów powinni otrzymać piraci. A jak obliczyć liczbę klejnotów dla Długiego Johna?

Sprawę załatwia polecenie


Zadanie 1. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Skarb piratów.

Nie najlepsze – ale działające – rozwiązanie wygląda tak.


Zadanie Miękkie lądowanie

Zadanie polega na zaprogramowaniu poszczególnych obiektów (dwóch chmur i trzech kotów), aby zachowywały się zgodnie z wytycznymi podanymi w treści. Zaczniemy od skryptów dla chmur – są one zupełnie takie same w obu przypadkach. Aby zagwarantować zgodność z narzuconymi wymogami, na początku ustawiamy ich kierunek na 90 stopni. Później – wykorzystujemy już wbudowany w Scratcha mechanizm wykrywania brzegu obszaru roboczego i odbijania. Wystarczy tylko ustawić odpowiedni styl obrotu na wartość nie obracaj.

Ćwiczenie 3. Zaprogramuj obie chmury (działając na dołączonym do zadania szablonie) aby w pętli typu zawsze przesuwały się z krokiem 5 i odbijały od lewego i prawego brzegu zgodnie z warunkami zadania (bez obrotów).

Odpowiedź do ćwiczenia – pierwszy element rozwiązania zadania.


Spadanie kotów można uzyskać zmniejszając ich współrzędne y (np. za pomocą polecenia zmień y o -5). Oczywiście nie możemy tego robić bez końca, a jedynie do momentu, w którym duszek osiągnie dolny brzeg. Można więc wykorzystać pętlę z warunkiem: powtarzaj aż dotyka krawędź. Z drugiej strony takie warunkowanie może być nieskuteczne, gdy początkowa pozycja duszka jest np. zbyt wysoka i kotek zahacza o górną krawędź obszaru roboczego. Można więc powyższy warunek zastąpić takim: powtarzaj aż pozycja y < -155.

Ćwiczenie 4. Wykorzystując powyższe uwagi napisz skrypt dla Procka, dzięki któremu kotek będzie spadał aż do dolnego brzegu.

Poniżej – obie możliwości.


Pozostaje jeszcze nauczyć koty co mają zrobić przy spotkaniu z chmurami. Gdy postąpimy naiwnie dodając instrukcję warunkową z czujnikiem: jeżeli dotyka Chmura to – obróć o 180 stopni, to w efekcie przy kolizji z odpowiednią chmurą duszek zacznie ,,migać” co jest spowodowane tym, że szerokość chmury jest większa od 5, więc kolizja jest obsługiwana przez kilka kroków duszka i za każdym razem obraca się on o 180 stopni. Aby wyeliminować ten efekt, można użyć zmiennej (tzw. flagowej), której jednym zadaniem będzie pamiętanie o tym, czy taka kolizja już wystąpiła (wartość zmiennej równa 1) czy jeszcze nie (wartość równa 0 – to też będzie wartość początkowa). Jeżeli zmienną tą nazwiemy Drap1 (kolizja Drapka z Chmurą 1), to odpowiedni fragment programu mógłby wyglądać tak:

W zadaniu musimy zaprogramować takie zachowanie każdego kota przy ewentualnym spotkaniu z obiema chmurami – ten sposób będzie więc wymagał użycia aż sześciu zmiennych (trzy koty razy dwie chmury).

Ćwiczenie 5. W podobny sposób jak powyżej, dodaj obsługę kolizji Drapka i drugiej chmury. Przetestuj działanie programu przy różnych początkowych ustawieniach Drapka i chmur (chmury nie muszą się poruszać).

Ostatnim etapem jest zatrzymanie chmur zaraz po lądowaniu ostatniego kota. Tu też można użyć trzech zmiennych flagowych (dla każdego kota osobna zmienna, np. DrapLeci, MruLeci, ProcLeci), które będą określały czy dany kot już wylądował (wartość równa 1) czy jeszcze spada (wartość początkowa równa 0). Wtedy – po zdefiniowaniu wszystkich trzech takich zmiennych – do pętli w programach obu chmur należy dorzucić warunek: powtarzaj aż DrapLeci=0 i MruLeci=0 i ProcLeci=0. Sprawi to, że chmury zatrzymają się gdy tylko do dolnej krawędzi dotrze ostatni kot.

Zadanie 2. Wykorzystując powyższe wskazówki – rozwiąż oryginalne zadanie z zawodów Miękkie lądowanie.

Przykładowe rozwiązanie jest zawarte w poniższym pliku.
Miękkie lądowanie (plik .sb3)


Spotkanie XX.

Kiedy mogą przydać się listy?

Chodzi oczywiście o listy (tablice) służące do przechowywania informacji w pamięci komputera – a nie o listy pisane do kogoś (chociaż w czasie pracy zdalnej i narzuconego odosobnienia, powrót do pisania tradycyjnych listów może całkiem miłym zajęciem).

Niniejsze zajęcia będą poświęcone kilku przykładom mniej lub bardziej typowym przykładom zadań algorytmicznych, w których listy mogą być bardzo przydatne.

Przykład 1. Chcemy napisać program, który po wczytaniu ocen danego ucznia, obliczy ich średnią i wypisze jej wartość na ekranie komputera.

Spróbujmy zaplanować rozwiązanie najpierw przy użyciu Scratcha, a później Pythona. W Scratchu dane wejściowe (czyli oceny) najwygodniej przechowywać używając listy.

Lista OCENY i obsługujący ją program.

Pokazany fragment programu, używając pętli, oblicza sumę wszystkich ocen zawartych na liście OCENY i zapamiętuję są w zmiennej o nazwie suma_ocen. Oczywiście, aby dokończyć trzeba tę sumę jeszcze podzielić przez liczbę wszystkich ocen na liście.

Ćwiczenie 1. Dokończ powyższy program tak, żeby duszek wyświetlał (blok powiedz) wartość obliczonej średniej przez 10 sekund.

Jeśli się zastanowimy, to tak naprawdę przechowywanie wszystkich ocen w pamięci komputera nie jest konieczne – można je wprowadzać już po uruchomieniu programu, a w przygotowanej zmiennej możemy pamiętać sumę wszystkich podanych liczb. Schemat dla takiego programu w Pythonie może wyglądać np. tak.

  • podaj liczbę ocen ucznia (zmienna n)
  • podaj kolejne oceny i zapamiętaj ich sumę (zmienna suma_ocen)
  • wypisz średnią na ekranie.

Oczywiście należy pamiętać o specyficznej składni Pythona (np. o tym, że wszystkie wprowadzane dane są traktowane jako zmienne znakowe i trzeba dokonać ich konwersji na wartości typu liczbowego).

n = int(input("Podaj liczbe ocen: "))
suma_ocen = 0
for k in range(n):
    ocena = int(input("kolejna ocena: "))
    suma_ocen = suma_ocen + ocena
print("Obliczona srednia wynosi",suma_ocen/n)

Ćwiczenie 2. Napisz – w Scratchu lub w Pythonie – program, który dla wprowadzonych ocen ucznia wypisze krótki raport informujący o tym ile było ocen pozytywnych (a więc od stopnia dopuszczającego wzwyż), a ile negatywnych (niedostatecznych).

Przykład 2. Listy mogą też być wykorzystane do pamiętania jakiejś wielkości, która zmienia się w czasie działania programu, bo wykonywane są na niej jakieś operacje (mówimy wtedy, że jest to zmienna dynamiczna, w odróżnieniu od zmiennej statycznej – jaką była lista ocen w poprzednim przykładzie). Spróbujemy napisać program, który będzie symulował grę Taśma, którą poznaliśmy na spotkaniu X.

Ćwiczenie 3. Przypomnij sobie zasady gry Taśma. Zastanów się, w jaki sposób lista mogłaby być odpowiednikiem planszy do tej gry.

Tym razem napiszemy najpierw odpowiedni program w Pythonie. Schemat działania będzie następujący:

  • wczytanie wielkości planszy
  • ustawienie początkowych wartości zmiennych roboczych
  • główna pętla programu: naprzemienne ruchy grających, sprawdzanie czy gra już się nie zakończyła
  • wyświetlenie komunikatu o zwycięzcy
n = int(input("Podaj wielkosc planszy: "))
zajete = 0          # zmienna ta przechowuje ile pol jest 
                    # juz wykorzystanych, dopoki (zajete < n), 
                    # gra toczy sie nadal
                    
plansza = [0]*n     # pusta plansza - lista dlugosci n 
blad = 1            # zmienna pomocnicza 

def ruch(X):
    global blad, zajete, plansza 
    blad=1 
    while blad==1:
        A = int(input("Ruch gracza "+X+": "))
        if A<0 or A>n-1 :
            print("Pole poza plansza - podaj inne.")
        elif plansza[A]!=0 :
            print("Pole zajete - podaj inne.")
        else :
            blad = 0
            plansza[A]=1
            zajete = zajete + 1
            if A>0 and plansza[A-1]==0 :
                plansza[A-1]=1
                zajete = zajete + 1
            if A<n-1 and plansza[A+1]==0 :
                plansza[A+1]=1
                zajete = zajete + 1
        if zajete == n :
            print("Wygral gracz: "+X+"!")
                
while zajete < n:
    ruch("A")
    if zajete < n:
        ruch("B")

Uwaga. Ze względu na przejrzystość kodu, w programie powyżej została wykorzystana tzw. funkcja ruch(), która jest taka sama dla obu graczy – pozwala to uniknąć powielenia tego samego fragmentu ciągu instrukcji. Słowo global sprawia, że wymienione po nim zmienne można używać wewnątrz funkcji tak samo jak poza jej obrębem. W przeciwnym razie komputer utworzyłby nowe zmienne o tych samych nazwach ale ich wartości nie były widoczne poza blokiem dotyczącym instrukcji def. Drugą sprawą jest to, że dla planszy o długości n gracze podając numery poszczególnych pól muszą używać wartości od 0 do n – 1. Wynika to z faktu, że taka jest numeracja kolejnych elementów listy w Pythonie (i w wielu innych językach programowania).

Zadanie. Wykorzystując wcześniej utworzoną listę, spróbuj zaprojektować w Scratchu program symulujący grę Taśma.