Matura z informatyki 2020 – lipiec, poziom rozszerzony

Przeanalizuj następujący algorytm:

Algorytm:

dla i = 1, 2, 3, … , n wykonuj
        P[i] ← 1
        S[i] ← 0
dla j = 2, 3, … , n wykonuj
        jeżeli P[j] = 1
                i ← j * j
                dopóki i ≤ n wykonuj
                        P[i] ← 0
                        i ← i + j
        S[j] ← S[j - 1] + P[j]

Ułamkami egipskimi nazywamy ułamki postaci 1m, gdzie m jest liczbą całkowitą większą od 1. Każdą dodatnią liczbę wymierną a < 1 można przedstawić w postaci sumy ułamków egipskich o różnych mianownikach. Takich różnych rozkładów może być kilka.

Jedna z metod rozkładu liczby wymiernej a na sumę ułamków egipskich jest następująca:

1. Szukamy najmniejszej liczby całkowitej n nie mniejszej od odwrotności a. Ułamek 1n jest największym ułamkiem egipskim w rozkładzie liczby a.

2. Liczbę 1n odejmujemy od a i otrzymujemy pewną różnicę r, która jest liczbą wymierną mniejszą od 1. Jeżeli r jest równe 0, to rozkład został znaleziony. W przeciwnym przypadku znajdujemy w ten sam sposób rozkład liczby r na ułamki egipskie, które dopisujemy do rozkładu liczby a.

Przykład:

Niech a = 45. Aby znaleźć największy ułamek egipski, który nie jest większy od a, szukamy najmniejszej liczby całkowitej nie mniejszej od odwrotności danego ułamka 1a = 54. Liczba 2 jest taką liczbą, zatem największym ułamkiem egipskim w rozkładzie liczby a jest 12.

W kolejnym kroku znajdujemy rozkład na ułamki egipskie liczby 45 - 12 = 310.

Ostatecznie otrzymujemy rozkład: a = 45 = 12 + 14 + 120.

void ul_egipt(int p, int q)
{
  If (p>0)
  {   int m=ceil(float (q)/p);
      cout<<m<<" ";
      ul_egipt(p*m-q,q*m);
  }
}

Oceń prawdziwość podanych zdań. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli jest fałszywe.

W każdym zadaniu punkt uzyskasz tylko za komplet poprawnych odpowiedzi.

f(n):
        jeżeli n = 0
                wynikiem jest 1
        w przeciwnym przypadku
                s ← 1
                dla i = 0, 1, ..., n - 1
                        s ← s + f(i)
                wynikiem jest s

SELECT Rezyserzy.nazwisko, Rezyserzy.imie, [1]
FROM Rezyserzy INNER JOIN Filmy ON [2]
GROUP BY [3];

=JEŻELI(MOD(A1;2)=0;JEŻELI(MOD(B1;2)=0;A1*B1/4;A1*B1);JEŻELI(MOD(B1;2)=0;A1*B1;(A1+B1)/2))

Plik identyfikator.txt zawiera 200 wierszy. W każdym wierszu jest zapisany identyfikator pewnego dokumentu, który składa się z serii (trzy wielkie litery alfabetu łacińskiego) oraz sześciu cyfr.

Napisz program(-y), w wyniku działania którego(-ych) otrzymasz odpowiedzi do poniższych zadań.

Uwaga: Plik identyfikator_przyklad.txt zawiera przykładowe dane (20 wierszy). Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.

KOK201272
PIP417543
MOS302203

NHO307984
SEH422297
MOS302203

Samochodowa jednostanowiskowa myjnia automatyczna Czyste auta jest otwarta od godziny 6.00 do 24.00. Klienci podjeżdżają do myjni, ustawiają się w kolejce i wybierają jeden z programów mycia. Poszczególne programy różnią się czasem realizacji. W myjni jest tylko jedno stanowisko, więc klienci muszą czekać, aż skończy się mycie poprzednich samochodów. Jeżeli czas oczekiwania przekracza 5 minut, klient rezygnuje z kolejki.

Plik myjnia.txt zawiera 144 wierszy danych z jednego dnia działania myjni. W każdym wierszu podano:

• po ilu minutach od przyjazdu poprzedniego klienta przyjechał dany klient (dla pierwszego klienta jest to liczba minut od otwarcia myjni);
• czas realizacji wybranego programu mycia – liczba naturalna z przedziału ⟨1; 15⟩;
• numer rejestracyjny – dwie duże litery i trzy cyfry.

Dane w wierszach pliku są rozdzielone średnikami.

Przykład:

3;5;NN792
12;13;FO434
1;10;GN103
7;2;EA828

Przedstawione dane oznaczają, że:

– pierwszy klient przyjechał 3 minuty po otwarciu myjni i miał myty samochód przez 5 minut, czyli mycie skończyło się 8 minut po otwarciu myjni,

– kolejny klient przyjechał 15 minut po otwarciu myjni i zakończył mycie samochodu 28 minut po otwarciu myjni,

– następny klient przybył 16 minut po otwarciu i musiałby czekać na mycie aż upłynie 28 minut po otwarciu myjni. Ponieważ czas oczekiwania na usługę przekraczał 5 minut (musiałby czekać 12 minut), to ten klient zrezygnował z kolejki,

– czwarty klient przybył 23 minuty po otwarciu i mycie jego samochodu zakończyło się 30 minut po otwarciu myjni (trwało 2 minuty, a zaczęło się po 28 minutach od otwarcia myjni).

Korzystając z dostępnych narzędzi informatycznych, znajdź i podaj odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wyniki5.txt, a każdą z nich poprzedź numerem odpowiedniego zadania.

Biuro badań opinii społecznych przeprowadziło ankietę wśród 280 mieszkańców różnych województw, dotyczącą między innymi zainteresowań oraz wykształcenia. Ankietowani mogli podać maksymalnie trzy rodzaje zainteresowań (każdy musiał podać przynajmniej jedno). Zbierano również informacje o dochodach ankietowanych oraz o środkach lokomocji, z których korzystają oni w różnych porach roku.

Dane uzyskane z ankiety zapisano w trzech plikach tekstowych. W każdym pliku pierwszy wiersz jest wierszem nagłówkowym, a dane w wierszach są rozdzielone znakami tabulacji.

W pliku dane_ankiet.txt znajdują się informacje na temat ankietowanych osób:

• Id – identyfikator ankietowanego (liczba),
• Nazwisko – nazwisko ankietowanego,
• Imie – imię ankietowanego,
• Wiek – wiek ankietowanego,
• Wyksztalcenie – wykształcenie ankietowanego,
• Dochod – dochód miesięczny ankietowanego,
• Wojewodztwo – nazwa województwa, z którego pochodzi ankietowany.

Fragment pliku dane_ankiet.txt:

Id  Nazwisko    Imie        Wiek  Wyksztalcenie  Dochod  Wojewodztwo
1   Adamczuk    Magdalena   69    wyzsze         3500    Pomorskie
2   Adamczyk    Urszula     41    wyzsze         2250    Slaskie
3   Adamowicz   Jakub       34    srednie        2550    Swietokrzyskie

W pliku zain.txt znajdują informacje na temat zainteresowań ankietowanych osób:

• Id – identyfikator ankietowanego,
• Zainteresowania – zainteresowania ankietowanego.

Fragment pliku zain.txt:

Id      Zainteresowania
14      polityka
254     muzyka
201     jezyki
147     gry komputerowe

W pliku lok.txt zapisano dane dotyczące preferowanych środków lokomocji, z których korzystają ankietowani w różnych porach roku:

• Id_a – id ankietowanego,
• Srod_lok – środek lokomocji, z którego korzysta ankietowany,
• Pora_roku – pora roku.

Fragment pliku lok.txt:

Id  Srod_lok    Pora_roku
1   rower       wiosna
1   rower       lato
1   rower       jesien
1   tramwaj     zima
2   samochod    wiosna
2   samochod    lato

Korzystając z dostępnych narzędzi informatycznych, znajdź i podaj odpowiedzi do poniższych zadań. Odpowiedzi zapisz w pliku wyniki6.txt, a każdą z nich poprzedź numerem odpowiedniego zadania.