Zadanie 1.1, matura maj 2015, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Problem telewidza
W Problemie telewidza mamy program telewizyjny, zawierający listę filmów emitowanych w różnych stacjach telewizyjnych jednego dnia. Telewidz zamierza obejrzeć jak najwięcej filmów w całości. Jedyne ograniczenie jest takie, że telewidz może oglądać co najwyżej jeden film (stację telewizyjną) jednocześnie. Zakładamy, że jednego dnia wszystkie filmy są różne.
Program telewizyjny emisji filmów w 4 stacjach telewizyjnych:
| Telewizja / stacja | Film i godziny jego emisji | Czas trwania emisji filmu |
|---|---|---|
| TV1 | film 1: od 9:00 do 12:00 | 3 godziny |
| TV1 | film 2: od 15:00 do 17:00 | 2 godziny |
| TV2 | film 3: od 11:00 do 16:00 | 5 godzin |
| TV3 | film 4: od 12:00 do 14:00 | 2 godziny |
| TV4 | film 5: od 11:30 do 12:30 | 1 godzina |
Dla programu podanego powyżej telewidz jest w stanie obejrzeć aż trzy filmy, np.: film 1, film 4, film 2. Przyjmujemy, że telewidz nie traci w ogóle czasu na przełączanie pomiędzy stacjami (np. o godz. 12:00 z TV1 na TV3). Innymi słowy, czasy emisji filmów 1 i 4 nie kolidują ze sobą.
Rozważ następujący algorytm wyboru filmów do obejrzenia przez telewidza, w którym w kroku 2. stosuje się jedną z czterech strategii opisanych w tabeli 1.
Specyfikacja:
Dane: T – zbiór filmów z programu telewizyjnego z godzinami emisji i czasami ich trwania
S – strategia z tabeli 1.
Wynik: P – zbiór filmów, które obejrzy telewidz.
Algorytm:
Krok 1. Zainicjuj P jako zbiór pusty.
Krok 2. Dopóki T zawiera jakieś filmy, wykonuj:
• stosując strategię S, wybierz ze zbioru T film x i usuń go z T
• dodaj film x do zbioru P
• usuń ze zbioru T wszystkie filmy, których czasy emisji kolidują z czasem emisji filmu x.
Krok 3. Zakończ wykonywanie algorytmu i wypisz wszystkie filmy ze zbioru P.
Tabela 1. Cztery strategie (S) w Problemie telewidza:
| Strategia A | Wybierz film, który trwa najdłużej, a jeśli jest takich więcej, to wybierz z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów, wybierz dowolny z nich. |
| Strategia B | Wybierz film, który trwa najkrócej, a jeśli jest takich więcej, to wybierz z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów, wybierz dowolny z nich. |
| Strategia C | Wybierz film, który się najwcześniej zaczyna, a jeśli jest takich więcej, to wybierz z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów, wybierz dowolny z nich. |
| Strategia D | Wybierz film, który się najwcześniej kończy, a jeśli jest takich więcej, to wybierz z nich ten, który się najpóźniej zaczyna. Jeśli jest więcej takich filmów, wybierz dowolny z nich. |
Przykład: Dla podanego programu telewizyjnego zastosowanie w kroku 2. strategii A daje wynik P = {film 3}, czyli telewidz obejrzy tylko jeden film.
Polecenie
2 punktyDla podanego programu telewizyjnego podaj wyniki wykonywania algorytmu po zastosowaniu strategii B, C i D:
| Strategia S | Zawartość zbioru P po zakończeniu wykonywania algorytmu |
|---|---|
| B | |
| C | |
| D |
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
strategia B: P={film 5, film 2}
strategia C: P={film 1, film 4, film 2}
strategia D: P={film 1, film 4, film 2}
Schemat punktowania
za podanie poprawnych odpowiedzi dla trzech strategii.
za podanie poprawnych odpowiedzi dla dwóch strategii.
za odpowiedź niepełną lub błędną albo za brak odpowiedzi.