Spotkanie 3.

Projektowanie prostych algorytmów – c.d.

Zadanie rankingowe. Każdy otrzymuje początkowo 15 punktów i każdy przystępuje do gry z poprzedniego spotkania: Scratch – Odgadnij liczbę! (plik .sb3) Liczba punktów dodanych każdemu do rankingu to 15 minus liczba wykorzystanych pytań w grze. Uwaga: jest tylko jedno podejście!

4. Autobus. W pewnym autobusie jest 100 miejsc siedzących, przy czym siedzenia są ustawione jedno za drugim i nie ma miejsc podwójnych (każdy pasażer siedzi sam). Można powiedzieć, że siedzenia są ustawione w ,,kolejce” – jej początek znajduje się przy jedynym wejściu do autobusu (i przy stanowisku kierowcy), a koniec – miejsce o numerze 100 – na samym tyle pojazdu. Wszyscy jeżdżący tym autobusem znają dobrze zasady panujące w pojeździe i stosują się do nich. A brzmią one tak:

  • jeśli autobus jest pusty, to zajmij pierwsze miejsce przy wejściu,
  • jeżeli autobus nie jest pusty, to zajmij takie wolne miejsce siedzące, które jest położone możliwie najdalej od najbliższego zajętego już miejsca; jeśli takich miejsc jest więcej niż jedno, to wybierz to które znajduje się bliżej wejścia do pojazdu.

Zadanie. Podaj numery miejsc jakie zajmie pierwszych 5 pasażerów. Spróbuj przewidzieć, które miejsce byłoby w takim autobusie zajmowane jako ostatnie, przez setnego pasażera. A gdyby autobus miał 200 miejsc siedzących, to jaki numer miałoby miejsce zajmowane jako ostatnie?

Pasażerowie będą zajmować kolejne miejsca o numerach:

    \[1,\quad 100,\quad 50,\quad 75, \quad 25,\quad 13,\quad \ldots\]

Jako ostatnie zostanie zajęte miejsce o numerze 99, a w autobusie mającym 200 miejsc – ostatnie będzie zajmowane miejsce numer 199.



5. Reszta. Musimy zaprogramować automat z napojami tak, aby potrafił wydawać resztę. Dla ułatwienia będziemy zakładać, że maszyna dysponuje wyłącznie monetami o nominałach 1 gr, 10 gr, 20 gr, 50 gr, 1 zł, 2 zł i 5 zł ale każdej z tych monet jest dużo. Chcemy jednak, aby podczas wydawania reszty, automat podawał jak najmniejszą liczbę monet. Przykładowo: jeśli reszta wynosiłaby 7 zł 26 gr, to oczekujemy dokładnie dziewięciu monet: jednej pięciozłotówki, jednej dwuzłotówki, jednej monety 20-groszowej i sześć grosików.

Zadanie. Zaplanuj algorytm, który dla podanej kwoty, nie przekraczającej 50 zł, poda w jakich monetach można tę kwotę wypłacić i liczba użytych monet będzie możliwie mała.

Ze względu na sposób działania typowego schematu postępowania rozwiązującego powyższy problem, algorytmy takie nazywane są algorytmami zachłannymi.



Do graficznego przedstawienia algorytmu służą m.in. schematy blokowe. Poniżej prosty przykład takiego schematu:

Każdy element schematu swoim kształtem informuje o roli jaką pełni w algorytmie. Podstawowe kształty to: prostokąt – czyli blok operacyjny (obliczeniowy), równoległobok – operacje wejścia/wyjścia (wprowadzenie danych, wypisywanie komunikatów, wyników obliczeń), romb – blok decyzyjny, prostokąty ,,owalne” tworzą tzw. bloki graniczne (rozpoczęcie i zakończenie/wstrzymanie) działania algorytmu.

Zadanie domowe. Zainteresowanych zachęcam do odwiedzenia strony: https://www.mauthor.com/present/6300670723489792
gdzie znajduje się przykładowy skrócony test z konkursu informatycznego Bóbr. Wersja testu z możliwością sprawdzenia odpowiedzi: https://www.mauthor.com/present/6709353706029056

Dodaj komentarz

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