Zadanie 1.1, matura maj 2015, informatyka rozszerzona

2 pktotwartełatwe 81%Maj 2015

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 / stacjaFilm i godziny jego emisjiCzas trwania emisji filmu
TV1film 1: od 9:00 do 12:003 godziny
TV1film 2: od 15:00 do 17:002 godziny
TV2film 3: od 11:00 do 16:005 godzin
TV3film 4: od 12:00 do 14:002 godziny
TV4film 5: od 11:30 do 12:301 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 AWybierz 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 BWybierz 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 CWybierz 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 DWybierz 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 punkty

Dla podanego programu telewizyjnego podaj wyniki wykonywania algorytmu po zastosowaniu strategii B, C i D:

Strategia SZawartość 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.

Wypróbuj za darmo

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

2 pkt

za podanie poprawnych odpowiedzi dla trzech strategii.

1 pkt

za podanie poprawnych odpowiedzi dla dwóch strategii.

0 pkt

za odpowiedź niepełną lub błędną albo za brak odpowiedzi.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.