Zadanie 1.2, matura maj 2017, informatyka rozszerzona

4 pktotwartetrudne 28%Maj 2017

Darmowe konto pozwoli wrócić do niego później.

Zadanie

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

Polecenie

4 punkty

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)

Algorytm:

Korepetytor

Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.

Wypróbuj za darmo

5 rozmów · bez karty · Zaloguj się

Sprawdź się

Jak poszło?

Pokaż rozwiązanieUkryj rozwiązanie

Odpowiedź z klucza CKE

Przykładowe rozwiązania:

1. Algorytm o złożoności liniowej

```cpp

int max1,max2;

max1 = max2 = 0;

for(int i = 1; i <= n; ++i)

{

if(A[i] % p != 0)

{

if(A[i] > max1)

{

max2 = max1;

max1 = A[i];

}

else if(A[i] > max2)

max2 = A[i];

}

}

cout << max1 * max2;

```

2. Algorytm o złożoności kwadratowej

```cpp

int maxpole = 0;

for(int i = 1; i < n; ++i)

{

for(int j = i + 1; j <= n; ++j)

{

int pole = A[i] * A[j];

if(pole % p != 0)

{

if(pole > maxpole)

maxpole = pole;

}

}

}

cout << maxpole;

```

Schemat punktowania

4 pkt

za prawidłowe rozwiązanie o złożoności liniowej, w tym:

3 pkt

za poprawne wyznaczenie długości dwóch najdłuższych boków, w tym:

– 2 pkt – za wyznaczenie długości dwóch najdłuższych boków. Uwaga: za wyznaczanie długości dwóch najdłuższych boków, w tym tylko jednej poprawnej – 1 punkt.

– 1 pkt – za sprawdzanie podzielności przez p.

1 pkt

za wyznaczenie największego pola prostokąta o bokach różnej długości i uwzględnienie wyniku S = 0.

2 pkt

za prawidłowe rozwiązanie o złożoności innej niż liniowa, w tym:

1 pkt

sprawdzanie podzielności przez p.

1 pkt

za wyznaczenie największego pola prostokąta o bokach różnej długości oraz uwzględnienie wyniku S = 0.

0 pkt

za podanie błędnej odpowiedzi albo za brak odpowiedzi.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

Komentarz. Rozwiązanie liniowe polega na znalezieniu dwóch największych elementów nie podzielnych przez p. Rozwiązanie kwadratowe sprawdza wszystkie pary. Złożoność jest głównym kryterium oceny.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.