Matura 2017 (maj). Zadanie 1. Prostokąt

Dane są:

liczba całkowita n większa od 1
zbiór A zawierający n dodatnich, różnych liczb całkowitych
liczba pierwsza p

Zadanie 1.

Dla danych z każdego wiersza w tabeli oblicz największe pole powierzchni prostokąta, które nie jest podzielne przez p, a długości sąsiednich boków tego prostokąta są różne (nie może on być kwadratem) i należą do zbioru A. Zapisz pole tego prostokąta w kolumnie S. Jeżeli taki prostokąt nie istnieje, jako wynik podaj liczbę 0 (zero).

Rozwiązanie:

Krok 1. 

Szukając największe pole powierzchni prostokąta, które nie jest podzielne przez p rozpocząć należy od odrzucenia liczb podzielnych przez liczbę p.

15, 12, 10, 6, 5, 1
6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18
4, 34, 16, 8, 6, 22, 14, 12, 2, 7

Krok 2.

Wybieramy dwie największe liczby spośród pozostałych, wykonujemy iloczyn, wynik sprawdzamy czy nie est podzielny przez p.

12*6=72
18*12=216
7*—– brak drugiej liczby

Zadanie 2. 

Zapisz (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) algorytm obliczający największe pole powierzchni prostokąta, które nie jest podzielne przez p, a długości sąsiednich boków tego prostokąta należą do zbioru A i są różne.
Przy ocenie brana będzie pod uwagę złożoność obliczeniowa Twojego algorytmu.

Uwaga:
W zapisie algorytmu możesz wykorzystywać tylko następujące operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie całkowite i obliczanie reszty z dzielenia.

Specyfikacja:

Dane:

n – liczba całkowita większa od 1
A[1..n] – tablica zawierająca n różnych, dodatnich liczb całkowitych
p – liczba pierwsza

Wynik:

S – największe pole powierzchni prostokąta, które nie jest podzielne przez p,
a długości sąsiednich boków tego prostokąta są różne i zawarte w tablicy A;
jeśli nie można zbudować takiego prostokąta, wynikiem powinno być 0 (zero)

Rozwiązanie:

#include <iostream>
#define N 11
#define P 7

using namespace std;

int main()
{
    int tab[N]={6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18};
    int x=0,y=0;
    for (int i=0; i<N; i++) {
        if (tab[i]%P!=0) {
            if (tab[i] > x ) x = tab[i];
        }
    }
    for (int i=0; i<N; i++) {
        if (tab[i]%P!=0) {
            if (tab[i] > y && tab[i] < x ) y = tab[i];
        }
    }
    if (x*y>0)
        cout << "Pole prostokata = " << x << " * " << y << " = " << x*y << endl;
    else
        cout << "Wynik = 0 " << endl;
    return 0;
}

Matura 2018 (maj). Zadanie 2. Krajobraz

W pewnym paśmie górskim znajduje się n szczytów, które będziemy przedstawiać jako punkty w układzie kartezjańskim na płaszczyźnie. Wszystkie punkty leżą powyżej osi OX, tzn. druga współrzędna (y) każdego punktu jest dodatnia.

W punkcie (0,0) stoi obserwator. Jeśli dwa szczyty A i B mają współrzędne (x_A, y_A) oraz (x_B, y_B), to mówimy, że:

• szczyt A jest dla obserwatora widoczny na lewo od B, jeśli x_A/y_A < x_B/y_B;
• szczyt B jest widoczny na lewo od A, jeśli x_A/y_A > x_B/y_B.

Wiemy, że żadne dwa szczyty nie leżą w jednej linii z obserwatorem, a zatem dla obserwatora te szczyty nie zasłaniają się nawzajem. Ilustrację przykładowego położenia szczytów można zobaczyć na poniższym rysunku:

W tym przykładzie, patrząc od lewej do prawej strony, obserwator widzi kolejno szczyt D, szczyt A, szczyt B i szczyt C.

Współrzędne szczytów dane są w dwóch tablicach X[1..n] oraz Y[1..n] – szczyt numer i ma współrzędne (X[i], Y[i]).

Zadanie 1. 

Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który znajdzie i poda współrzędne skrajnie lewego szczytu, tzn. widocznego dla obserwatora na lewo od wszystkich pozostałych szczytów.

Specyfikacja:

Dane:

n – liczba całkowita dodatnia
X[1..n] – tablica liczb całkowitych
Y[1..n] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.
Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.

Wynik:

x, y – współrzędne skrajnie lewego szczytu spośród tych opisanych w tablicach X i Y.

Algorytm:

#include <iostream>
using namespace std;
int main()
{
int n=4;
int X[n]={1,3,2,-2};
int Y[n]={3,4,1,2};
int x,y;
for (int i=0; i<n-1; i++)
  if (float(X[i])/float(Y[i]) < float(X[i+1])/float(Y[i+1])) {
    x = X[i];
    y = Y[i];
  }
cout << x << " " << y << endl;
return 0;
}

Zadanie 2.

Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który przestawi elementy tablic X i Y tak, aby szczyty były uporządkowane w kolejności, w której obserwator widzi je od lewej do prawej strony. Aby otrzymać maksymalną ocenę, Twój algorytm powinien mieć złożoność czasową kwadratową lub mniejszą. Algorytm może używać wyłącznie instrukcji sterujących, operatorów arytmetycznych, operatorów logicznych, porównań i przypisań do zmiennych. Zabronione jest używanie funkcji bibliotecznych dostępnych w językach programowania.

Specyfikacja:

Dane:

n – liczba całkowita dodatnia
X[1..n] – tablica liczb całkowitych
Y[1..n] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.
Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.

Wynik:

X[1..n], Y[1..n] – tablice zawierające współrzędne danych szczytów, uporządkowanych w kolejności, w której obserwator widzi je od lewej do prawej strony.

Algorytm:

#include <iostream>
using namespace std;
int main()
{
 int n=4;
 int X[n]={1,3,2,-2};
 int Y[n]={3,4,1,2};
 for (int j=0; j<n-1; j++)
   for (int i=0; i<n-1; i++) { 
     if (float(X[i])/float(Y[i]) > float(X[i+1])/float(Y[i+1])) {
       swap(X[i],X[i+1]);
       swap(Y[i],Y[i+1]);
     }
   }
 for (int i=0; i<n; i++) {
   cout << "X[" << i << "]= " << X[i] << " ";
   cout << "Y[" << i << "]= " << Y[i];
   cout << endl;
 }
return 0;
}

Matura 2018 (maj). Zadanie 1. Analiza algorytmu

Rozważamy następujący algorytm:

Dane:

n – liczba całkowita dodatnia

Wynik:

p – liczba całkowita dodatnia

p ← 1
 q ← n
 dopóki p < q wykonuj
 s ← (p+q) div 2
 (*) jeżeli s*s*s < n wykonaj
 p ← s+1
 w przeciwnym wypadku
 q ← s

Uwaga: zapis div oznacza dzielenie całkowite.

Zadanie 1.

Podaj wynik działania algorytmu dla wskazanych w tabeli wartości n.

Miejsce na obliczenia.

Algorytm:

#include <iostream>

using namespace std;

int main()
{
 cout << "Podaj n = ";
 int n, p=1;
 cin >> n;
 int q=n;
 int s;
 while (p<q) {
   s = (p+q)/2;
   if (s*s*s<n)
     p=s+1;
   else
     q=s;
 }
 cout << "p = " << p << endl;
 return 0;
}

Zadanie 2.

Podaj najmniejszą oraz największą liczbę n, dla której wynikiem działania algorytmu będzie p = 10.

Miejsce na obliczenia.

Najmniejsza liczba n to 9*9*9+1=730, ponieważ musi być spełniony warunek s³<n. Największa liczba n to 10*10*10=1000, ponieważ musi być spełniony warunek s³<n.

Odpowiedź: Najmniejsza liczba to 730, największa liczba to 1000.

Zadanie 3. 

Dokończ zdanie. Wybierz i zaznacz właściwą odpowiedź spośród podanych. Dla każdej liczby całkowitej n > 1 instrukcja oznaczona w algorytmie symbolem (*) wykona się

A. mniej niż 2*log₂n razy.
B. więcej niż n/2, ale mniej niż n razy.
C. więcej niż n+1, ale mniej niż 2n razy.
D. więcej niż n² razy.

Komentarz:

Odpowiedź A ponieważ, 2*log₂n -> 2 * log₂64 = 2 * 6 = 12. Jest to mniej niż 12.

log₂64=x
2^x = 64
2⁶ = 64