Matura z informatyki 2011 – maj, poziom rozszerzony

Opisana poniżej funkcja rekurencyjna wyznacza, dla liczby naturalnej n > 0, długość napisu uzyskanego przez sklejenie binarnych reprezentacji liczb naturalnych od 1 do n − 1.

Funkcja sklej(n)

krok 1. jeśli n = 1, to podaj 0 jako wynik i zakończ działanie
krok 2. jeśli n parzysta, to wynikiem jest n − 1 + 2 · sklej(n / 2)
krok 3. jeśli n nieparzysta, to wynikiem jest n − 1 + sklej((n − 1) / 2) + sklej((n + 1) / 2)

Wykonaj polecenia a)–c):

#include <iostream>

using namespace std;

int main()
{
  int n;
  int * s;

  cin >> n;

  s = new int[n+1];

  s[1] = 0;

  for(int i=2;i<=n;++i)
  {
    if(i%2 == 0)
      s[i] = i-1+2*s[i/2];
    else
      s[i] = i-1+s[(i-1)/2]+s[(i+1)/2];
  }

}

Dana jest następująca specyfikacja oraz algorytm obliczania potęgi o wykładniku naturalnym:

Algorytm:

krok 1.   p := 1, b := a
krok 2.   dopóki n > 0 wykonuj:
              a) jeśli n mod 2 ≠ 0, to p := p * b
              b) b := b * b
              c) n := n div 2

Uwaga: n div 2 oznacza wynik dzielenia całkowitego n przez 2, a n mod 2 oznacza resztę z dzielenia całkowitego n przez 2.

Podpunkty a) – h) zawierają po cztery odpowiedzi, z których każda jest albo prawdziwa, albo fałszywa. Zdecyduj, które z podanych odpowiedzi są prawdziwe (P), a które fałszywe (F). Zaznacz znakiem X odpowiednią rubrykę w tabeli.

krok 1.   suma := 1, i := 2
krok 2.   dopóki i <= n, wykonuj
              a. j := i, p := 1
              b. dopóki j >= 1, wykonuj:
                     (i)  p := p * i
                     (ii) j := j − 1
              c. suma := suma + p, i := i + 1

Firma „Zielone Miasto" podpisała umowę na utrzymanie trawników dużej aglomeracji od dnia 1 kwietnia do 30 października 2011 roku. Zadaniem firmy jest:

• wywożenie z miasta skoszonej trawy,
• koszenie trawników.

1 kwietnia 2011 roku rano zgromadzone było 10 000 m³ skoszonej trawy. Firma dysponuje 30 samochodami do wywozu skoszonej trawy z miasta. Objętość zgromadzonej trawy zmienia się codziennie w następujący sposób:

• przed południem (zaczynając od 1 kwietnia) każdy samochód firmowy wywozi 15 m³ skoszonej trawy z miasta,
• w ciągu każdego dnia kosi się 600 m³ trawy,
• w nocy objętość zgromadzonej trawy zmniejsza się o 3%. Ubytek trawy zaokrąglamy w dół do całkowitej liczby m³. Na przykład, jeśli wieczorem zgromadzono 60 m³ trawy, to w nocy jej objętość zmniejszy się o 1 m³, co odpowiada liczbie 3% · 60 m³ zaokrąglonej w dół do liczby całkowitej.

Korzystając z dostępnych narzędzi informatycznych, wykonaj poniższe polecenia. Odpowiedzi umieść w pliku zadanie4.txt, poprzedzając je literami oznaczającymi odpowiednie podpunkty.

Pewien klub kynologiczny przechowuje w plikach tekstowych informacje o swoich członkach i ich psach. Informacje przechowywane w wierszach w każdym z plików są rozdzielone średnikami.

W pliku osoby.txt każdy wiersz zawiera informacje o członkach klubu: id_osoby, imię, nazwisko, nr telefonu.

Przykład:

o001;Adam;Roztoka;501358358
o002;Adam;Komarnicki;337234875

Plik psy.txt zawiera informacje dotyczące psów i ich właścicieli: id_psa, rasa, wiek, płeć, liczba zdobytych medali, id_osoby.

Przykład:

1;wyżeł węgierski krótkowłosy;4;samica;1;o059
2;owczarek niemiecki;2;samica;2;o064
3;chihuahua;3;samiec;4;o097

Wykorzystując dane zawarte w tych plikach oraz dostępne narzędzia informatyczne, wykonaj poniższe polecenia. Odpowiedzi zapisz w pliku zadanie5.txt, poprzedzając je literami oznaczającymi odpowiednie podpunkty.

W pliku liczby.txt, w oddzielnych wierszach, znajduje się 1000 liczb zapisanych w systemie dwójkowym o długościach zapisów od 2 do 16 cyfr (0 lub 1).

Napisz program, którego wykonanie da odpowiedzi do poniższych podpunktów. Odpowiedzi zapisz w pliku zadanie6.txt, a każdą odpowiedź poprzedź literą oznaczającą ten podpunkt.