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.

Dodaj komentarz

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