Zadanie 1.2, matura maj 2015, informatyka rozszerzona

3 pktotwartetrudne 36%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

3 punkty

Zastosowana strategia S w algorytmie jest optymalna, jeśli dla każdego programu telewizyjnego wynik algorytmu (zbiór P) zawiera największą możliwą liczbę filmów, które może obejrzeć telewidz.

Uwaga: Strategia A nie jest optymalna, ponieważ telewidz może obejrzeć trzy filmy: film 1, film 4 oraz film 2.

Dla strategii A, B i C podaj w przygotowanych tabelach przykłady programów telewizyjnych, z emisją czterech filmów w dwóch stacjach, będące dowodami, że żadna z tych strategii nie jest optymalna.

Dla każdej strategii i podanego dla niej programu telewizyjnego podaj wynik działania algorytmu oraz przykład ilustrujący, że telewidz może obejrzeć więcej filmów, jeżeli nie używa tej strategii.

Wskazówka. Podaj takie godziny emisji czterech filmów, aby telewidz był w stanie obejrzeć np. trzy lub więcej filmów, podczas gdy zastosowanie algorytmu z odpowiednią strategią daje rozwiązanie zawierające co najwyżej dwa filmy.

Dowód dla strategii A:

Telewizja / stacjaFilm i godziny jego emisjiCzas trwania emisji filmu
TV1film 1 (od do )
TV1film 2 (od do )
TV2film 3 (od do )
TV2film 4 (od do )

Wynik działania algorytmu przy zastosowaniu strategii A:

P:

Liczniejszy zbiór filmów, które może obejrzeć widz:

Dowód dla strategii B:

Telewizja / stacjaFilm i godziny jego emisjiCzas trwania emisji filmu
TV1film 1 (od do )
TV1film 2 (od do )
TV2film 3 (od do )
TV2film 4 (od do )

Wynik działania algorytmu przy zastosowaniu strategii B:

P:

Liczniejszy zbiór filmów, które może obejrzeć widz:

Dowód dla strategii C:

Telewizja / stacjaFilm i godziny jego emisjiCzas trwania emisji filmu
TV1film 1 (od do )
TV1film 2 (od do )
TV2film 3 (od do )
TV2film 4 (od do )

Wynik działania algorytmu przy zastosowaniu strategii C:

P:

Liczniejszy zbiór filmów, które może obejrzeć widz:

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 A

Telewizja/kanałFilm i godziny jego emisji
TV1film 1 (od 10:00 do 12:00), film 2 (od 12:00 do 14:00)
TV2film 3 (od 10:00 do 11:00), film 4 (od 11:00 do 12:00)

Wynik algorytmu: P={film 1, film 2}

Większy zbiór: P={film 3, film 4, film 2}

Strategia B

Telewizja/kanałFilm i godziny jego emisji
TV1film 1 (od 11:30 do 12:30), film 2 (od 15:00 do 16:00)
TV2film 3 (od 10:00 do 12:00), film 4 (od 12:00 do 14:00)

Wynik algorytmu: P={film 1, film 2}

Większy zbiór: P={film 3, film 4, film 2}

Strategia C

Telewizja/kanałFilm i godziny jego emisji
TV1film 1 (od 09:00 do 14:00), film 2 (od 15:00 do 16:00)
TV2film 3 (od 10:00 do 12:00), film 4 (od 12:00 do 14:00)

Wynik algorytmu: P={film 1, film 2}

Większy zbiór: P={film 3, film 4, film 2}

Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

Schemat punktowania

3 pkt

za podanie dla trzech strategii programu telewizyjnego, poprawnego dla nich wyniku algorytmu oraz poprawnego większego zbioru filmów, który może obejrzeć.

2 pkt

za podanie dla dwóch strategii programu telewizyjnego, poprawnego dla nich wyniku algorytmu oraz poprawnego większego zbioru filmów, który może obejrzeć.

1 pkt

za podanie dla jednej strategii programu telewizyjnego, poprawnego dla niej wyniku algorytmu oraz poprawnego większego zbioru filmów, który może obejrzeć.

0 pkt

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

Uwaga: sprawdzenie poprawności odpowiedzi wymaga zasymulowania działania algorytmu na podanym przez ucznia przykładzie oraz sprawdzenia, czy podany większy zbiór jest poprawny.

Komentarz. Sprawdzenie poprawności odpowiedzi wymaga zasymulowania działania algorytmu na podanym przez ucznia przykładzie oraz sprawdzenia, czy podany większy zbiór jest poprawny.

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.