Matura z informatyki 2018 – czerwiec, poziom rozszerzony

Zapisz w wybranej przez siebie notacji (w języku programowania lub w pseudokodzie) algorytm iteracyjny, który służy do obliczania wartości liczby Fₙ dla dowolnego n ≥ 1. Algorytm nie może używać tablic.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Uwaga: to zadanie otwarte – odpowiedź z klucza CKE jest jedynie przykładowa; istnieją również inne poprawne rozwiązania.

int main()
{
    int n, i, f1=1, f2=1, pom;
    cin>>n;
    for (int i=3; i<=n; i++)
    {
      pom=f1;
      f1=f2;
      f2=f2+pom;
     }
    cout<<f2;
}

Aby obliczyć F₄₅, wywołano najpierw funkcję iteracyjną, a potem – rekurencyjną. Okazało się, że czas trwania obliczeń realizowanych przez funkcję rekurencyjną był długi, podczas gdy funkcja iteracyjna prawie natychmiast podała wynik. Uzasadnij długi czas działania funkcji rekurencyjnej.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Drzewo wywołań rekurencyjnych zawiera wielokrotne wywołanie tych samych wyrazów co powoduje wielokrotne ich obliczanie. Im dalszy wyraz Fibonacciego jest obliczany, tym jest więcej takich powtórzeń. Co daje złożoność **wykładniczą** od n.

Aby przyśpieszyć rekurencyjne obliczanie wartości n-tego wyrazu ciągu Fibonacciego, można skorzystać z następujących wzorów, prawdziwych dla dowolnego całkowitego k ≥ 2:

F₂ₖ = (Fₖ₊₁)² - (Fₖ₋₁)²

F₂ₖ₋₁ = (Fₖ)² + (Fₖ₋₁)²

Zapisz w wybranej przez siebie notacji (w postaci listy kroków, w języku programowania lub w pseudokodzie) algorytm rekurencyjny, który służy do obliczania wartości liczby Fₙ dla dowolnego n ≥ 1 i korzysta z tych wzorów.

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Uwaga: to zadanie otwarte – odpowiedź z klucza CKE jest jedynie przykładowa; istnieją również inne poprawne rozwiązania.

kw(long int n)
{
    return n*n;
}
long int f(long int n)
{
    int i,k;
    if(n==1||n==2) return 1;
     else if (n%2==0)
        {
        i=n/2+1;
        k=n/2-1;
        return kw(f(i))-kw(f(k));
        }
        else {
            i=(n+1)/2;
            k=(n+1)/2-1;
            return kw(f(i))+kw(f(k));
        }
}

int main()
{
int n;
cin>>n;
cout << f(n)<< endl;     return 0;
}

Uwaga: Dopuszczamy zastosowanie przez zdającego funkcji potęgowania wbudowanej w język programowania

W sortowaniu przez scalanie wykorzystuje się scalanie dwóch ciągów uporządkowanych niemalejąco. Polega ono na tym, że porównujemy pierwsze elementy ciągów i mniejszy lub równy z nich przepisujemy do trzeciego ciągu, a w ciągu, z którego on pochodzi, przechodzimy do kolejnego elementu. Następnie znów porównujemy wskazywane elementy w obydwu ciągach i przepisujemy do trzeciego ciągu mniejszy lub równy z nich. Kontynuujemy to działanie do czasu wyczerpania elementów jednego z ciągów. Resztę elementów z drugiego ciągu przepisujemy do ciągu trzeciego.

W poniższym przykładzie wyczerpano już elementy ciągu drugiego. Wystarczy więc przepisać kolejno elementy 16 i 45 pierwszego ciągu do ciągu trzeciego, by zakończyć scalanie.

Do scalenia będziemy zawsze brali parę ciągów z odpowiadających sobie wierszy w plikach.

Napisz program, który utworzy plik wynik4_4.txt zawierający w kolejnych wierszach ciągi uporządkowane, będące wynikiem scalenia odpowiadających im co do kolejności ciągów z plików dane1.txt i dane2.txt. Liczby w ciągach wynikowych zapisz, rozdzielając je spacjami.

Dla danych z plików przyklad1.txt oraz przyklad2.txt wynikiem jest plik zawierający następujące wiersze:

3 3 9 9 12 12 12 14 14 19 19 26 26 32 32 33 33 33 36 36
2 6 8 9 15 16 16 17 17 18 24 27 29 35 35 36 41 41 46 54
3 9 12 12 16 21 23 25 27 29 31 33 33 38 38 46 48 48 50 54
5 8 13 15 22 22 27 31 36 39 45 46 49 52 55 56 57 64 70 70
1 1 2 2 8 8 8 9 9 10 10 18 18 22 22 22 32 32 34 34

Kliknij Pokaż odpowiedź, aby zobaczyć rozwiązanie z klucza CKE.

Temperatura wyrażana w skali bezwzględnej (skali Kelvina) w powiązaniu ze skalą Celsjusza opisywana jest wzorem: T[K]=273,15+T[ºC].

Wynik każdego pomiaru temperatury przedstaw w skali Kelvina zaokrąglony w dół do liczby całkowitej. Dla każdego czujnika podaj, które z otrzymanych zaokrąglonych wartości w skali Kelvina występują najczęściej.

Kliknij Pokaż odpowiedź, aby zobaczyć wzorcowe rozwiązanie z klucza CKE.

Podaj średnie wartości temperatury (w stopniach Celsjusza), zaokrąglone do dwóch miejsc po przecinku, odczytane przez czujnik nr 10 w poszczególnych miesiącach roku 2016. Przedstaw otrzymane wartości temperatury na wykresie słupkowym. Umieść na wykresie etykiety danych, opisy osi oraz tytuł wykresu.

Kliknij Pokaż odpowiedź, aby zobaczyć wzorcowe rozwiązanie z klucza CKE – zestawienie oraz gotowy wykres.

W wyniku awarii w laboratorium utracono wszystkie wyniki pomiarów z 2017 roku. Na podstawie zachowanych analiz stwierdzono, że w tych samych dniach miesiąca i o tych samych godzinach co w roku 2016 wyniki odczytów w 2017 roku zmieniły się następująco:

a) Wniosek I – w dniach od 5 do 10 każdego miesiąca odczyty czujnika1, czujnika2 i czujnika9 były niższe od tych w roku 2016 o 1,2°C.

b) Wniosek II – wszystkie odczytywane przez czujnik8 wartości w lipcu i sierpniu wzrosły o 7% w stosunku do odczytów z 2016 r. (w zaokrągleniu w dół do 2 miejsc po przecinku).

c) Wniosek III – w maju odczyty wszystkich czujników były dodatkowo wyższe o 0,9°C.

Odtwórz zestawienie temperatur czujnika1, czujnika2, czujnika8 i czujnika9 w roku 2017 w dniach i godzinach takich samych jak w roku 2016. Dla wymienionych czujników podaj pierwsze pomiary temperatury w °C z dni: 5-05-2017 oraz 7-07-2017 po zastosowaniu wniosku I i wniosku II oraz osobno po zastosowaniu wszystkich trzech wniosków.

Uwaga: wykonując zestawienie temperatur w roku 2017, przyjmij, że jeśli nie ma zastosowania żaden z wniosków I, II lub III, wartości temperatury są takie same jak w roku 2016.

Kliknij Pokaż odpowiedź, aby zobaczyć wzorcowe rozwiązanie z klucza CKE.

Utwórz zestawienie zawierające następujące informacje: imię, nazwisko, nr rejestracyjny samochodu, czas wypożyczenia (różnica między datą wypożyczenia i datą zwrotu – liczba dób), należność za wypożyczenie. Wiersze posortuj rosnąco według nazwiska klienta, a następnie – według imienia klienta i numeru rejestracyjnego samochodu. Podaj pierwszy i ostatni wiersz z uzyskanej tabeli.

Uwaga: dla daty wypożyczenia 2015-05-24 i daty zwrotu 2015-05-28 czas wypożyczenia to 4 doby.

Kliknij Pokaż odpowiedź, aby zobaczyć wzorcowe rozwiązanie z klucza CKE.

Dla każdej klasy samochodu podaj liczbę wypożyczeń samochodów tej klasy.

Kliknij Pokaż odpowiedź, aby zobaczyć wzorcowe rozwiązanie z klucza CKE.

Przygotuj zestawienie samochodów, które nie były wypożyczane. Podaj ich liczbę w podziale na klasy i miejscowości.

Kliknij Pokaż odpowiedź, aby zobaczyć wzorcowe rozwiązanie z klucza CKE.