Zadanie 1.2, matura maj 2017, informatyka rozszerzona
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 punktyZapisz (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.
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
za prawidłowe rozwiązanie o złożoności liniowej, w tym:
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.
za wyznaczenie największego pola prostokąta o bokach różnej długości i uwzględnienie wyniku S = 0.
za prawidłowe rozwiązanie o złożoności innej niż liniowa, w tym:
sprawdzanie podzielności przez p.
za wyznaczenie największego pola prostokąta o bokach różnej długości oraz uwzględnienie wyniku S = 0.
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.