Zadanie 1.2. (0-4)
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
A[1 n] - tablica zawierająca n różnych, dodatnich liczb całkowitych
p
Wynik:
S
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)
MIN_1R
Algorytm
Wypełnia
egzaminator
Nr zadania
1.1.
1.2.
Maks. liczba pkt.
2
4
Uzyskana liczba pkt.
MIN_1R
Zadanie 1.2. (0-4)
III. Rozwiązywanie problemów
i podejmowanie decyzji […],
z zastosowaniem podejścia algorytmicznego.
i podejmowanie decyzji […], stosowanie
podejścia algorytmicznego.
Zdający:
rozwiązywania problemu;
\nrozwiązania sytuacji problemowej i zapisuje
go w wy branej notacji;
a) algorytmy na liczbach całkowitych;
Schemat punktowania
4 p. - za prawidłowe rozwiązanie o złożoności liniowej, w tym:
3 p. - za poprawne wyznaczenie długości dwóch najdłuższych boków, w tym
2 p. - 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 p. - za sprawdzanie podzielności przez p.
1 p. - za wyznaczenie największego pola prostokąta o bokach różnej długości i uwzględnienie
wyniku S = 0 - 1 punkt
2 p. - za prawidłowe rozwiązanie o złożoności innej niż liniowa, w tym
1 p. - sprawdzanie podzielności przez p.
1 p. - za wyznaczenie największego pola prostokąta o bokach różnej długości oraz
uwzględnienie wyniku S = 0.
0 p. - za podanie błędnej odpowiedzi albo za brak odpowiedzi.
Przykładowe rozwiązania:
1.Algorytm o złożoności liniowej
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;
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;
Algorytm liniowy O(n) - jednokrotne przejście tablicy z aktualizacją dwóch największych elementów niepodzielnych przez p:
\nmax1 ← 0
max2 ← 0
dla i = 1, 2, , n wykonuj:
jeżeli A[i] mod p ≠ 0:
jeżeli A[i] > max1:
max2 ← max1
max1 ← A[i]
w przeciwnym razie jeżeli A[i] > max2:
max2 ← A[i]
S ← max1 * max2
Wynik: jeśli max2 = 0 (mniej niż 2 liczby spełniają warunek) → S = 0. W przeciwnym razie S = max1 · max2.
\nKluczowa własność (z zad. 1.1): liczba pierwsza p dzieli a·b ⟺ p|a lub p|b. Więc szukamy DWÓCH NAJWIĘKSZYCH RÓŻNYCH elementów A, które nie są podzielne przez p.
\nW jednym przejściu pętli utrzymujemy dwa zmienne:
\nmax1 - największa dotąd zaobserwowana liczba niepodzielna przez p,max2 - druga co do wielkości.Przy nowym elemencie A[i] (jeśli niepodzielny przez p):
\nGdy max2 = 0, to znaczy że istnieje co najwyżej jedna liczba niepodzielna przez p → S = 0 (max1 * 0 = 0).
\nPython:
```python
def max_pole(A, p):
max1, max2 = 0, 0
for x in A:
if x % p != 0:
if x > max1:
max2 = max1
max1 = x
elif x > max2:
max2 = x
return max1 * max2
print(max_pole([7, 5, 11, 33], 3)) # 77
print(max_pole([4, 34, 16, 8, 6, 22, 14, 12, 2, 7], 2)) # 0
Pascal:
```pascal
function MaxPole(A: array of LongInt; n, p: LongInt): LongInt;
var i, max1, max2: LongInt;
begin
max1 := 0; max2 := 0;
for i := 0 to n - 1 do
if A[i] mod p <> 0 then
begin
if A[i] > max1 then
begin
max2 := max1;
max1 := A[i];
end
else if A[i] > max2 then
max2 := A[i];
end;
MaxPole := max1 * max2;
end;
C++:
```cpp
long long maxPole(int A[], int n, int p) {
long long max1 = 0, max2 = 0;
for (int i = 0; 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];
}
}
}
return max1 * max2;
}
Reference - Dwa największe elementy w tablicy:\n
- Algorytm liniowy O(n): jedna pętla, dwie zmienne max1, max2.
- Aktualizacja: gdy x > max1, przesuń max1→max2, max1=x; w innym razie gdy x > max2, max2=x.
- Alternatywa: posortuj (O(n log n)) i weź dwa pierwsze - dłużej.
- W naszym zadaniu dodatkowy filtrA[i] mod p ≠ 0.
Klucz CKE (zadanie 1.2, max 4 pkt):\n
- 4 pkt - algorytm o złożoności liniowej w pełni poprawny, w tym:
- 2 pkt - wyznaczenie długości dwóch najdłuższych boków (1 pkt - tylko jednej)
- 1 pkt - sprawdzanie podzielności przez p (mod p ≠ 0)
- 1 pkt - uwzględnienie różnych długości boków i przypadku S = 0
- 2 pkt - rozwiązanie o złożoności gorszej niż liniowa (np. O(n²) - dwie pętle, lub O(n log n) - sortowanie + wybór)
- 0 pkt - błędne lub brak