SZUKAJ NA TYM BLOGU

Zadanie 1. Prostokąt (0–6) ()

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

Zadanie 1.1. (0–2)

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

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 – 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)

Przykładowe rozwiązania:

int A[] = {7, 5, 11, 33};
int n = 4;
int p = 3;

Przykładowe rozwiązania CKE poprawione

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

int max1,max2;
max1 = 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];
  }
}
cout << max1 * max2;

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

int maxpole = 0;
for(int i = 0; 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;

Poziom wykonania zadania: 1.1. - 85%; 1.2. - 28%;

Przypisy

  1. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2017/formula_od_2015/informatyka/MIN-R1_1P-172.pdf
  2. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2017/formula_od_2015/zasady_oceniania/MIN-R1-N.pdf
  3. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Informacje_o_wynikach/2017/sprawozdanie/Sprawozdanie%202017%20-%20Informatyka.pdf

Przykładowe rozwiązania w pseudokodzie

max1 ← 0
max2 ← 0
dla i = 1, 2, ..., n
  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]
wypisz max1 * max2


maxpole ← 0
dla i = 1, 2, ..., n
  dla j = i + 1, i + 2, ..., n
    pole ← A[i] * A[j]
    jeżeli pole modulo p ≠ 0
      jeżeli pole > maxpole
        maxpole ← pole
wypisz maxpole

Przykładowe rozwiązania w Python

max1 = 0
max2 = 0
for i in range(n):
    if A[i] % p != 0:
        if A[i] > max1:
            max2 = max1
            max1 = A[i]
        else:
            if A[i] > max2:
                max2 = A[i]
print(max1 * max2)


maxpole = 0
for i in range(n):
    for j in range(i + 1, n):
        pole = A[i] * A[j]
        if pole % p != 0:
            if pole > maxpole:
                maxpole = pole
print(maxpole)