Matura 2017 (nowa) - zadanie 1 (Prostokąt)

Zadanie 1.1 (2 punkty)

Proste zadanie na rozgrzewkę. Należało wpisać trzy liczby będące polami powierzchni największych prostokątów, mających boki o różnych długościach wybranych ze zbioru A. Pole to ma dodatkowo nie być podzielne przez liczbę pierwszą p. Z tego wynika, że żaden z boków nie może być podzielny przez p i nie ma możliwości aby iloczyn dowolnych dwóch liczb niepodzielnych przez p dał wartość podzielną przez p. W poniższej tabeli przekreśliłem liczby ze zbioru A podzielne przez p. Do obliczenienia wyniku z pozostałych wybieramy dwie największe liczby, których iloczyn daje odpowiedź.

Zbiór A p S - pole szukanego prostokąta
15, 12, 10, 6, 5, 1 5 72 (12 x 6)
6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18 7 216 (18 x 12)
4, 34, 16, 8, 6, 22, 14, 12, 2, 7 2 0

 

Zadanie 1.2 (4 punkty)

W tym zadaniu należy skonstruować algorytm obliczający pole największego prostokąta spełniającego warunki. Dla utrudnienia ograniczono liczbę operacji arytmetycznych, które można użyć. Dodatkowo przy ocenie będzie brana pod uwagę złożoność obliczeniowa.

Algorytm ten można napisać na dwa sposoby. Najprostsza wersja do napisania to mnożenie każdej liczby z każdą, sprawdzanie czy iloczyn nie jest podzielny przez p i szukanie z nich maksa. Jest bardzo prosty a największą trudnością jest nieuwzględnienie dwukrotnie w iloczynie tego samego odcinka. Niestety złożoność tego algorytmu jest taka sobie (kwadratowa), więc na pewno nie można za niego uzyskać maksymalnej liczby punktów.

Lepszym rozwiązaniem jest znalezienie dwóch najdłuższych boków o długości niepodzielnej przez p i zwrócenie ich iloczynu. Algorytm taki ma złożoność liniową. Przykładowym rozwiązaniem może być:

maks1 ← 0

maks2 ← 0

dla i=1 ... n

    jeżeli A[i] mod p ≠ 0

        jeżeli A[i] > maks1

            maks2 ← maks1

            maks1 ← A[i]

        w przeciwnym razie jeżeli A[i] > maks2

            maks2 ← A[i]

zwróć wynik maks1 • maks2

gdzie operacja mod oznacza resztę z dzielenia.

W powyższym rozwiązaniu zmienne maks1 i maks2 oznaczają kolejno najdłuższy i drugi co długości bok niepodzielne przez p. Jeżeli nie ma takich dwóch boków, to przynajmniej jedna z tych zmiennych pozostanie równa 0, dzięki temu ich iloczyn będzie równy 0 i otrzymamy poprawny wynik oznaczający brak prostokąta spełniającego warunki zadania. Nie mam jednak bladego pojęcia jak może nastąpić podział punktów. W tym rozwiązaniu jest kilka niezależnych rzeczy, które warto punktować (bo można zrobić je z błędem):

  • sprawdzanie podzielności przez p
  • znalezienie najdłuższego boku
  • znalezienie drugiego co do długości boku
  • obliczenie pola
  • podanie jako wynik "0" w przypadku braku prostokąta spełniającego warunki zadania
  • złożoność obliczeniowa

Jak w 4 punktach zostanie zmieszczone te 6 czynności - nie wiem. Pewnie jakoś będą pogrupowane. Analizując potencjalne rozwiązanie kwadratowe punkty można przydzielać za:

  • sprawdzanie podzielności przez p
  • znalezienie największego iloczynu
  • podanie jako wynik "0" w przypadku braku prostokąta spełniającego warunki zadania
  • złożoność obliczeniowa - tutaj oczywiście zero, ale za rozwiązanie kwadratowe nie można otrzymać wszystkich punktów

 

Na dzisiaj starczy. Jutro zadanie 2.