Darmowe konto pozwoli wrócić do niego później.
Polecenie
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:
Darmowe konto pozwoli wrócić do niego później.
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 liniowy (optymalny):
Znajdź największy element max1 nie podzielny przez p.
Znajdź drugi największy element max2 nie podzielny przez p.
Jeśli max1 i max2 istnieją i są różne, wynikiem jest max1 × max2, inaczej 0.
Algorytm kwadratowy:
Dla każdej pary elementów (i, j) gdzie i < j: oblicz iloczyn A[i] × A[j], jeśli nie jest podzielny przez p i jest większy od dotychczasowego maksimum, zapamiętaj go.
Wynikiem jest największy znaleziony iloczyn lub 0.
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; 2 pkt – za wyznaczenie długości dwóch najdłuższych boków (jeśli tylko jeden poprawny: 1 pkt); 1 pkt – za sprawdzanie podzielności przez p.
za prawidłowe rozwiązanie o złożoności innej niż liniowa, w tym: 1 pkt – sprawdzanie podzielności przez p; 1 pkt – wyznaczenie największego pola oraz uwzględnienie wyniku S = 0.
za podanie błędnej odpowiedzi albo za brak odpowiedzi.
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.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.