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.1. (2 pkt)
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).
| Zbiór A | p | S – pole szukanego prostokąta lub 0 (zero), jeśli nie można zbudować takiego prostokąta |
| 7, 5, 11, 33 | 3 | 77 |
| 15, 12, 10, 6, 5, 1 | 5 | |
| 6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18 | 7 | |
| 4, 34, 16, 8, 6, 22, 14, 12, 2, 7 | 2 |
odp: 12x6=72, 18x12=216, 0
Zadanie 1.2. (4 pkt)
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)
odp:
patrz omówienie - algorytm liniowy szukający dwóch dwóch niepodzielnych przez p, różnych maksimów