Matura 2007. Zadanie 5.

Zadanie. (20 pkt)

System audio-tele zarejestrowała numery telefonów komórkowych osób, które telefonowały pod wskazany numer, aby otrzymać nagrodę. Wiele osób, licząc na zwiększenie prawdopodobieństwa otrzymania wygranej, dzwoniło wielokrotnie. W pliku tekstowym o nazwie telefony.txt znajduje si 1000 zarejestrowanych numerów telefonów (połączeń), w tym także wielokrotnie zapisane numery telefonów osób, które bardzo chciały wygrać.

Każdy numer telefonu umieszczony jest w jednym wierszu.

Korzystając z danych umieszczonych w pliku telefony.txt, wykonaj polecenia a) – h). Każdą odpowiedź do punktów a) – g) umieść w pliku o nazwie zad_6.txt poprzedzając ją oznaczeniem odpowiedniego punktu.

  1. Ile razy telefonowano z numeru 504 669 045?
  2. Z którego numeru telefonowano najczęściej i ile razy?
  3. Ile numerów telefonów pochodzi z grupy numeracyjnej rozpoczynającej si od 511?
  4. I nagroda będzie losowana spośród osób, w których numerze telefonu suma cyfr parzystych jest większa od 42. Ile osób weźmie udział w losowaniu?
  5. II nagroda będzie losowana spośród osób, w których numerze telefonu występuję przynajmniej cztery cyfry 1. Ile osób weźmie udział w losowaniu?
  6. III nagroda będzie losowana spośród osób, w których numerze telefonu ostatni cyfr jest 2, a mediana wszystkich cyfr wchodzących w skład numeru telefonu jest liczbą podzielną przez 3 bez reszty. Ile osób weźmie udział w losowaniu?
  7. Utwórz zestawienie zawieraj ce w pierwszej kolumnie numery telefonów, z których dzwoniono przynajmniej 2 razy, a w drugiej kolumnie odpowiadając liczbę połączeń z tego numeru telefonu.
  8. Wykonaj wykres kolumnowy do zestawienia z punktu g. Pamiętaj o prawidłowym i czytelnym opisie osi wykresu.

Matura 2010 (maj). Zadanie 1. Anagram

Matura 2010 (maj). Zadanie 1. Anagram

Anagram to słowo powstałe z innego słowa przez przestawienie liter. Przez słowo rozumiemy w tym zadaniu dowolny ciąg liter alfabetu łacińskiego.

Przykłady anagramów:
dla słowa: barok – korba, robak, arobk, rokab, orkab …
dla słowa: ranty – tyran, narty, ntyra, natyr, ytnar …
W pliku tekstowym anagram.txt znajduje si 200 wierszy zawierających po 5 słów w każdym wierszu. Słowa oddzielone są znakiem odstępu. Długość każdego ze słów wynosi od 1 do 20 znaków.

Przykład:
abcd cdba dbac cbad dcba
barbakan xle ala foto otof
smok ayszkm lampa ayszkm bakara
skok arabanta oko agnieba dyskietka
… …

Napisz program w wybranym przez siebie języku programowania, za pomoc którego wykonasz poniższe polecenia:

  1. Wyszukaj w pliku anagram.txt te wiersze, w których wszystkie słowa znajdujące się w danym wierszu mają taką samą liczbę znaków. Zapisz te wiersze w pliku odp_4a.txt.
  2. Wyszukaj w pliku anagram.txt wszystkie wiersze tekstu, w których wszystkie słowa są anagramami pierwszego słowa w danym wierszu. Zapisz te wiersze w pliku odp_4b.txt.

 

 

Zadanie 6. Szkoła.

Szkoła dysponuje danymi zawartymi w trzech plikach: uczniowie.txt, oceny.txt, przedmioty.txt.

  • Plik uczniowie.txt zawiera następujące dane o uczniach: idUcznia, nazwisko, imie, ulica, dom, idKlasy.
  • Plik oceny.txt zawiera dane o ocenach: idUcznia, ocena, data, idPrzedmiotu.
  • Plik przedmioty.txt zawiera dane o przedmiotach: idPrzedmiotu, nazwaPrzedmiotu, nazwisko_naucz, imie_naucz.

Korzystając z danych zawartych w plikach uczniowie.txt, oceny.txt, przedmioty.txt oraz z dostępnych narzędzi informatycznych wykonaj poniższe polecenia. Każdą odpowiedź umieść w pliku odp_6.txt, poprzedzając ją oznaczeniem odpowiedniego podpunktu od a) do f).
Czytaj dalej…


Matura 2005. Zadanie 4. Projekt.

Centrum Projektowe Solaris tworzy prototyp pojazdu kosmicznego, który poleci na Marsa. Upłynął właśnie termin realizacji zlecenia, a Solaris ma jeszcze przed sobą wykonanie wielu obliczeń. Z uwagi na fakt, że są to bardzo specjalistyczne obliczenia, oprogramowanie dla nich oferują tylko firmy D1 i D2. Cena licencji na oprogramowanie zależy od maksymalnego dopuszczalnego rozmiaru przetwarzanych danych N podanego w gigabajtach i wynosi:

  • 0.01N dla oprogramowania firmy D1,
  • 0.5* N w przypadku firmy D2.

Z uwagi na to, że upłynął już termin realizacji projektu, istotny jest również czas obliczeń, ponieważ Solaris ponosi opłaty karne za opóźnienia w realizacji. W przypadku programu D1 obliczenia wykonywane są w czasie f(N)=10m3+7m2+0.1m+0.1, gdzie m=0.0001N sekund. Natomiast program D2 jest pięciokrotnie wolniejszy, wymaga czasu 5f(N) sekund. Kary wyznacza się proporcjonalne do opóźnień. Przyjmujemy więc, że koszt obliczeń (kara za opóźnienie) jest równy jego czasowi. A zatem na koszt wyboru rozwiązania D1 składa się koszt opłat licencyjnych (0.01N) plus koszt obliczeń (f(N)). Podobnie liczymy koszt dla oprogramowania D2.

Matura 2015 (maj). Zadanie 5. Demografia.

W kolejnych wierszach pliku kraina.txt znajdują się dane demograficzne Edulandii, która składa się z 50 województw. Każde z województw znajduje się w jednym z 4 regionów: A, B, C lub D. Każdy wiersz zawiera oddzielone średnikami informacje o jednym województwie, w następującej kolejności: nazwa województwa, liczba kobiet w 2013 roku, liczba mężczyzn w 2013 roku, liczba kobiet w 2014 roku, liczba mężczyzn w 2014 roku.

Przykład:
w01D;1415007;1397195;1499070;1481105
w02D;1711390;1641773;1522030;1618733
w03C;1165105;1278732;1299953;1191621
w04D;949065;1026050;688027;723233

Nazwa każdego województwa zaczyna się literą „w”, za nią występuje dwucyfrowy numer województwa, a na końcu litera A, B, C lub D oznaczająca region, w którym to województwo się znajduje.

Korzystając z dostępnych narzędzi informatycznych, podaj odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wynik5.txt, a każdą odpowiedź poprzedź numerem oznaczającym to zadanie.

Dodawanie danych z pliku tekstowego do arkusza kalkulacyjnego.

Zadanie 1.
Wyznacz ludność (liczbę wszystkich mieszkańców) każdego z regionów A, B, C i D w roku 2013. Następnie sporządź wykres kolumnowy porównujący ludności tych regionów w roku 2013. Zadbaj o czytelność wykresu.

Rozwiązanie:

Pierwszą operację, którą należy wykonać rozwiązując zadanie jest sumowanie ludności w każdym województwie. Suma liczby kobiet oraz mężczyzn. Funkcja:

=SUMA(B2:C2)

Kolejnym krokiem jest wybranie z nazwy województwa nazwę regiony, oznaczony jest literą. Do tego należy wykorzystać funkcję tekstową PRAWY. Użyłem funkcji:

=PRAWY(A2;1)

Po wykonaniu tych czynności proponuje rozwiązanie problemu wykorzystując funkcję sum częściowych. Przed wykorzystaniem sum częściowych posortuj wiersze według regionów sposobem A-Z.

Arkusz teraz jest gotowy do użycia sum częściowych, które znajdują się na wstążce dane. Ustawiamy w następujący sposób, dla każdej zmiany, ustawiamy region, następnie sumujemy wartość sumy mieszkańców w każdym województwie w roku 2013.

Teraz ostania czynność tego zadania to utworzenie wykresu z danych, które już mamy. Wstawiam wykres kolumnowy zaznaczając komórki z regionu oraz roku 2013.

Zadanie 2.
Przeanalizuj dane i wybierz województwa, w których liczba kobiet w 2014 roku była większa niż w 2013 roku i jednocześnie liczba mężczyzn w 2014 roku była większa niż w 2013 roku. Podaj liczbę wszystkich takich województw w całym kraju oraz w każdym z regionów: A, B, C i D.

Zadanie 3.
Prognozując zmiany demograficzne w Edulandii, przyjmujemy, że tempo wzrostu populacji
w każdym województwie w kolejnych latach będzie takie samo jak w okresie 2013–2014.
Tempo wzrostu w danym województwie to iloraz
(2013)
(2014)
ludnosc
ludnosc , który zaokrąglamy w dół
do 4 miejsc po przecinku – ludnosc (r) to ludność w tym województwie w roku r. Ludność
dla roku r>2014 obliczamy wg wzoru:
ludnosc (r) = ludnosc (r – 1) • tempo_wzrostu
zaokrąglając w dół do liczby całkowitej.
Jeżeli w jakimś województwie w danym roku ludność jest ponaddwukrotnie większa niż stan
z roku 2013, to w tym województwie występuje efekt przeludnienia. Przyjmujemy wówczas,
że począwszy od następnego roku ludność danego województwa nie będzie się zmieniać.
Strona 5 z 8
MIN_2R
Na przykład dla województwa w01D mamy:
• Ludność w 2013 roku (mężczyzn i kobiet) wynosi 1 415 007 + 1 397 195 = 2 812 202
• Ludność w 2014 roku (mężczyzn i kobiet) wynosi 1 499 070 + 1 481 105 = 2 980 175
• Tempo wzrostu dla tego województwa jest równe = 1,0597
2 812 202
2 980 175 po zaokrągleniu
w dół do 4 miejsc po przecinku.
Liczba mieszkańców województwa w roku 2015 wyniesie:
2 980 175 * 1,0597 = 3 158 091 (po zaokrągleniu w dół do liczby całkowitej).
Dla województwa w01D ludność w roku 2025 przekroczy ponaddwukrotnie ludność
początkową (wyniesie 5 639 669) i od tego czasu nie będzie się w kolejnych latach zmieniać.
Wykonaj polecenia:
• Podaj liczbę wszystkich mieszkańców Edulandii w 2025 roku i wskaż, które województwo
będzie miało w tym roku najwięcej mieszkańców.
• Podaj liczbę województw, w których kiedykolwiek wystąpi efekt przeludnienia w latach
2014–2025 włącznie.
Do oceny oddajesz:
• plik tekstowy wynik5.txt zawierający odpowiedzi do poszczególnych zadań.
Odpowiedź do każdego zadania powinna być poprzedzona jego numerem.
• plik zawierający odpowiedź do zadania 5.1. o nazwie:
…………………………………………………………………………………………………………………………………
• plik(i) zawierający(e) komputerową realizację Twoich obliczeń:
…………………………………………………………………………………………………………………………………

Matura 2005. Zadanie 1. Szeregi nieskończone i funkcje elementarne.

Wartości funkcji elementarnych, takich jak sin, cos, log, są obliczane za pomocą komputera w sposób przybliżony. Często stosuje się w tym celu wzory, które mają postać nieskończonych sum. Na przykład prawdziwy jest następujący wzór na wartość logarytmu naturalnego z liczby 2:

W oparciu o powyższy wzór można zaprojektować i napisać program, który dla danej liczby ε (ε > 0) oblicza przybliżoną wartość ln 2, sumując jak najmniej wyrazów, aby różnica między dwoma ostatnimi przybliżeniami była mniejsza niż ε.

Wprowadźmy oznaczenie:

dla n ≥ 1

Wykonaj poniższe polecenia:

a) Wypełnij tabelę:

n ln
0 2/3
1 2/3 * ( 1 + 1/3 * 1/9 )
2 2/3 * ( 1 + 1/3 * 1/9 + 1/5 * 1/92)
3 2/3 * ( 1 + 1/3 * 1/9 + 1/5 * 1/92 + 1/7 *1/93 )

Poniżej podaj zależność pomiędzy wartościami ln i ln–1 dla każdego n=1, 2, …

 

Matura 2015. Zadanie 4. Liczby binarne.

W pliku liczby.txt znajduje się 1000 liczb naturalnych zapisanych binarnie. Każda liczba zapisana jest w osobnym wierszu. Pierwsze pięć wierszy zawiera następujące liczby:
11010100111
11110111111011101
1010100111010100
1101111111111111111111010100101010101001
1010110011001101010011110101010101010111
Każda liczba binarna zawiera co najwyżej 250 cyfr binarnych, co oznacza, że w wielu językach programowania wartości niektórych z tych liczb nie da się zapamiętać w pojedynczej zmiennej typu całkowitoliczbowego, np. w języku C++ w zmiennej typu int.
Napisz program, który da odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wynik4.txt, a każdą odpowiedź poprzedź numerem oznaczającym odpowiednie zadanie.

Zadanie 4.1.
Podaj, ile liczb z pliku liczby.txt ma w swoim zapisie binarnym więcej zer niż jedynek.

Przykład: Dla zestawu liczb:
101011010011001100111
10001001
1000000
101010011100
100010
wynikiem jest liczba 3 (3 podkreślone liczby mają w swoim zapisie więcej zer niż jedynek).

Rozwiązanie:

Sprawdzenie należy rozpocząć od policzenia dla każdej liczby binarnej ilość zer i jedynek. Porównamy ze sobą otrzymane wyniki.

#include <iostream>
#include <fstream>
#include <math.h>
#define N 1000
using namespace std;
int main()
{
  string t[N];
  fstream plik;
  plik.open("liczby.txt");
  if (plik.good()==false)
    cout << "Problem z plikiem!" << endl;
  else
    for(int i=0; i<N; i++)
      plik >> t[i];
  // zadanie 1
  int il_liczb=0;
  short il_zer, il_jedynek;
  for (int i=0; i<N; i++) {
    il_zer=0;
    il_jedynek=0;
    for (int j=0; j<t[i].length(); j++) {
      if (t[i][j] == '0') il_zer++;
      else il_jedynek++;
    }
    if (il_zer>il_jedynek) il_liczb++;
  }
  cout << il_liczb << endl;
  return 0;
}

Zadanie 4.2.
Podaj, ile liczb w pliku liczby.txt jest podzielnych przez 2 oraz ile liczb jest podzielnych przez 8.

Przykład:
Dla zestawu liczb:
101011010011001100000 (*), (**)
10001001
100100 (*)
101010010101011011000 (*), (**)
100011
trzy liczby są podzielne przez 2 (*) i dwie liczby są podzielne przez 8 (**).

Rozwiązanie:
Do rozwiązania tego zadania należy przeanalizować liczby binarne. Wiemy, kiedy na ostatnim miejscy liczby binarnej jest zero, to podana liczba jest  parzystą. Dlatego sprawdzamy ostatnią liczbę.

Kod źródłowy do tej części zadania:

#include <iostream>
#include <fstream>
#include <math.h>
#define N 1000
using namespace std;
int main()
{
  string t[N];
  fstream plik;
  plik.open("liczby.txt");
  if (plik.good()==false)
    cout << "Problem z plikiem!" << endl;
  else 
    for(int i=0; i<N; i++)
      plik >> t[i];
  int ile_parz=0;
  for (int i=0; i<N; i++)
    if (t[i][t[i].length()-1] == '0')
      ile_parz++;
  cout << ile_parz << endl;
  return 0;
}

 

 

Cyfra setek Cyfra dziesiątek Cyfra jedności
0, 2, 4, 6 lub 8 0, 4 lub 8 0 lub 8
1, 5 lub 9 6
2, 6 4
3, 7 2
1, 3, 5, 7 lub 9 0, 4 lub 8 4
1, 5 lub 9 2
2, 6 0 lub 8
3, 7 6

 Liczba jest podzielna przez 88, gdy liczba składająca się z trzech ostatnich cyfr dzieli się na 8.

Zadanie 4.3. (0–6)
Znajdź najmniejszą i największą liczbę w pliku liczby.txt. Jako odpowiedź podaj
numery wierszy, w których się one znajdują.
Przykład: Dla zestawu liczb:
101011010011001100111
10001001011101010
1001000
101010011100
1000110
najmniejsza liczba to: 1000110
największa liczba to: 101011010011001100111
Prawidłowa odpowiedź dla powyższego przykładu to: 5, 1.

Matura 2017 (maj). Zadania 2. Rekurencja

Matura 2017 (maj). Zadania 2. Rekurencja

Funkcja licz(x) przyjmuje jako argument dodatnią liczbę całkowitą x, natomiast jako wynik daje pewną liczbę całkowitą.

licz(x)
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik
w-1

Uwaga: div – dzielenie całkowite, mod – reszta z dzielenia całkowitego.

Zadanie 1.

Uzupełnij tabelę – podaj wartość licz(x) dla podanych argumentów x.

x licz(x)
11 2
13 2
21 1
32 -4

Obliczenia:

Rekurencja działa na zasadzie wywoływania funkcji dopóki x nie będzie równy 1. Na zielono zaznaczyłem kod który wykona się przy x = 11.

licz(11) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 11 div 2 = 5
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1

Zwróci nam wartość 5, ponieważ teraz w = 11 div 2 = 5. Teraz ponownie wywołujemy funkcje licz(x) z wartością x = 5.

licz(5) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 5 div 2 = 2
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1

Zwróci nam wartość 2, ponieważ teraz w = 5 div 2 = 2. Teraz ponownie wywołujemy funkcje licz(x) z wartością x = 2.

licz(2) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 2 div 2 = 1
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1

Zwróci nam wartość 1, ponieważ teraz w = 2 div 2 = 1. Teraz ponownie wywołujemy funkcje licz(x) z wartością x = 1, ale to już zwróci nam w = 1.

licz(1) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2)
jeżeli x mod 2 = 1
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1

Musimy wrócić do naszych funkcji licz(x) i wykonać dalszą część kodu, którą zaznaczę kolorem czerwonym, wracamy do funkcji licz(2). Pamiętamy że w = 1.

licz(2) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 2 div 2 = 1
jeżeli x mod 2 = 1 // 2 mod 2 = 0
podaj wynik w+1
w przeciwnym przypadku
podaj wynik w-1 // w = 1 – 1 = 0

Po wykonaniu tej funkcji w = 0, teraz wracamy do funkcji licz(5). 

licz(5) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 5 div 2 = 2
jeżeli x mod 2 = 1 // 5 mod 2 = 1
podaj wynik w+1 // w = 0 + 1 = 1
w przeciwnym przypadku
podaj wynik w-1

Po wykonaniu tej funkcji w = 1, teraz wracamy do funkcji licz(11).

licz(11) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 11 div 2 = 5
jeżeli x mod 2 = 1 // 11 mod 2 = 1
podaj wynik w+1 // w = 1 + 1 = 2
w przeciwnym przypadku
podaj wynik w-1

Po wykonaniu tej funkcji w = 2, teraz już nie mamy w pamięci żadnej funkcji licz(x), to wynik naszej funkcji zwraca wartość 2.

Pozostałe rozwiązania:

Zadanie 2.

Dana jest dodatnia liczba całkowita k. Jaka jest najmniejsza dodatnia liczba całkowita x, dla której obliczanie wartości licz(x) wymaga dokładnie k wywołań funkcji licz, licząc także pierwsze wywołanie licz(x)? Podkreśl prawidłową odpowiedź.

Przykład: obliczenie licz(13) wymaga dokładnie 4 wywołań funkcji licz.

A) x = k2
B) x = 2k–1
C) x = k+1
D) x = 2k

Przykład odpowiedzi nr 1:

Najmniejsza dodatnia liczba całkowita x, dla której dokładne będzie k wywołań funkcji licz() jest to liczba sprawdzając od początku jeden (1). Wywołanie funkcji licz(x) z wartością 1 wykona się dokładnie jeden raz, ponieważ: 

licz(1) 
jeżeli x = 1
podaj wynik 1
w przeciwnym przypadku
w ← licz(x div 2) // w = 11 div 2 = 5
jeżeli x mod 2 = 1 // 11 mod 2 = 1
podaj wynik w+1 // w = 1 + 1 = 2
w przeciwnym przypadku
podaj wynik w-1

W funkcji licz(1) wykona się tylko kod zaznaczony zielono i funkcja ta zwróci wynik 1. Następnie musimy sprawdzić dla jakiego k równe jest x, czyli kiedy x = k (1 = k).

Sprawdzamy dla x= 1: 

A)
x = k2
k = 1  ⇒ x = 1 ⇒ 1 = 1
B)
x = 2k–1 
k = 1  ⇒ x = 21-1  ⇒ x = 20  ⇒ 1 = 1 

C)
x = k+1
k = 0  ⇒ x = 0 + 1  ⇒ 1 = 1 (k musi być liczbą dodatnią całkowitą!!! To odpada!!!)
D) 
x = 2k
k = 0  ⇒ x = 20  ⇒ 1 = 1 (k musi być liczbą dodatnią całkowitą!!! To odpada!!!)

Mamy dwie odpowiedzi prawidłowe: A i B. Zastanawiając się, która odpowiedź jest prawidłowa i dlaczego jest to B, doszedłem do wniosku, iż musi to być to związane z liczbą binarną, dlatego postawiłem na odpowiedź B.

Przykład odpowiedzi nr 2 :

Jest to rozwiązanie, gdzie zostało założone, iż do sprawdzenia należy wybrać x ≠ 1. Padło na początek na liczbę x = 2 i tak dla tek liczby funkcja licz(2) wykona się dwa razy.

licz(2) ⇒ wywołań tej funkcji jest dokładnie 2 razy.

licz(2) ⇒ licz(1)

A)
x = k2
k = 2  ⇒ x = 2 ⇒ 2 = 4 ( to odpada ponieważ x = k2 )
B)
x = 2k–1 
k = 2  ⇒ x = 22-1  ⇒ x = 21  ⇒ 2 = 2  (ta odpowiedź jest prawidłowa)

C)
x = k+1
k = 2  ⇒ x = 2 + 1  ⇒ 2 = 3 (równanie to nie jest prawdziwe!!! To odpada!!!)
D) 
x = 2k
k = 2  ⇒ x = 22  ⇒ 2 = 4 (równanie to nie jest prawdziwe!!! To odpada!!!)

Odpowiedź jest prawidłowa, ale nie jest to najmniejsza dodatnia liczba całkowita. Tu moja uwaga, nie wiadomo co miał na myśli autor zadania.

Odpowiedź otrzymałem od Pana Jakuba. Dziękuje!!!

UWAGA!!! Jeśli ktoś ma bardziej racjonalne wyjaśnienie proszę napisać na kontakt@informatyka.dwojka.net. Dziękuję.

Zadanie 3.

Podaj najmniejszą liczbę całkowitą x większą od 100, dla której wynikiem wywołania licz(x) będzie 0.

Odpowiedź:

x = 135

Obliczenia:

W naszym przypadku podany algorytm jest to zamiana liczby dziesiętnej na liczbę binarną. W zadaniu tym należy wziąć po uwagę, kiedy otrzymamy wynik 0 (zero). Będzie to wtedy kiedy ilość zer i jedynej w liczbie binarnej będzie równa sobie. Kolejnym problem jest podanie liczy powyżej 10010, taka liczba zawiera 7 cyfr w zapisie binarnym. Szukamy liczby która w zapisie binarnym będzie miała parzystą ilość liczb, tj. w tym przypadku 8.

100000002 = 12810

Szukana najmniejsza liczba binarna zawierająca 8 cyfr, która składa się z 4 jedynek i 4 zer.

100001112 = 13510

Matura 2015 (maj). Zadanie 1. Problem telewidza

Matura 2015 (maj). 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
film 2: od 15:00 do 17:00
3 godziny
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.

Zadanie 1.

Dla 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 P = {film 5, film 2}
C P = {film 1, film 4, film 2}
D P = {film 1, film 4, film 2}

Zadanie 2.

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 / stacja Film i godziny jego emisji Czas trwania emisji filmu
TV1 film 1 (od …………………. do ………………….),
film 2 (od …………………. do ………………….)
………………….
………………….
TV2 film 3 (od …………………. do ………………….),
film 4 (od …………………. do ………………….)
………………….
………………….

Wynik działania algorytmu przy zastosowaniu strategii A:

P

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

Z

Dowód dla strategii B:

Telewizja / stacja Film i godziny jego emisji Czas trwania emisji filmu
TV1 film 1 (od …………………. do ………………….),
film 2 (od …………………. do ………………….)
………………….
………………….
TV2 film 3 (od …………………. do ………………….),
film 4 (od …………………. do ………………….)
………………….
………………….

Wynik działania algorytmu przy zastosowaniu strategii B:

P

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

Z

Dowód dla strategii C:

Telewizja / stacja Film i godziny jego emisji Czas trwania emisji filmu
TV1 film 1 (od …………………. do ………………….),
film 2 (od …………………. do ………………….)
………………….
………………….
TV2 film 3 (od …………………. do ………………….),
film 4 (od …………………. do ………………….)
………………….
………………….

Wynik działania algorytmu przy zastosowaniu strategii C:

P

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

Z