C++ OD PODSTAW DO MATURY

Działki - zadanie maturalne z roku 2019

(rozszerzenie, stara formuła)

Zadanie 3

Treść zadania

W rogu północno-zachodnim działki (czyli lewym górnym rogu mapy) trzeba wytyczyć kwadratowy plac, który nie może zawierać przeszkód terenowych (czyli zawiera wyłącznie pola puste oraz trawiaste).

Znajdź działkę, na której zmieści się taki plac o największej powierzchni. Jako odpowiedź podaj numer tej działki oraz długość boku placu. Jeśli jest więcej takich działek, podaj numery ich wszystkich.

Przykładowo z podanego rysunku można wytyczyć kwadratowy plac o boku o długości 4. Dla pliku przyklad.txt odpowiedź to: numer działki – 4, maksymalny bok – 7.

Omówienie i przykładowe rozwiązanie

Spróbuj rozwiązać zadanie samodzielnie. Tylko w taki sposób możesz przygotować się do matury. Poniżej znajdziesz przykładowe rozwiązanie wraz z omówieniem. Zaglądnij tam dopiero po uzyskaniu przez Ciebie wyników. Porównaj Twoje rozwiązanie z przykładowym. Życzę, aby Twoje było lepsze.

Proponuję przygotowanie funkcji, która zwróci liczbę odpowiadającą długości kwadratu wolnego od znaku "X". Funkcja jako argument przyjmie informacje o jednej działce zapisanej w tablicy dwuwymiarowej. Gdy uzyskamy długość boku kwadratu dla każdej działki, będzie można wyłonić maksymalną wartość i w taki sposób wyszukać interesujące nas działki.

Funkcja "ile" wykorzystuje pętlę while (Listing 1, linia 3), która obraca się nie więcej, niż trzydzieści razy, co odpowiada wymiarom działki. W pętli tej czytane są pola, których współrzędna Y (równa wartości iteratora i) lub współrzędna X (równa wartości iteratora j) jest równa wartości zmiennej "licz" pełniącej rolę iteratora pętli while.

W taki sposób zostanie najpierw przeczytany fragment tablicy oznaczony kolorem żółtym (Rysunek 1). Przy kolejnych obrotach pętli while (Listing 1, linia 3) zostaną przeczytane następne obszary tablicy bez powtarzania tych obszarów, które były już sprawdzone przy wcześniejszym obrocie pętli while.

Jeżeli zostanie znaleziony znak "X" (Listing 1, linia 6), proces sprawdzania zostaje przerwany i funkcja zwraca wartość iteratora pętli while, co jest równoznaczne z długością kwadratu wolnego od znaku "X".

W kolejnym kroku przeglądamy tablicę danych (Listing 2, linia 1 i 2) oraz zapisujemy dane do tablicy "dzialka". Gdy tablica zostaje zapełniona (Listing 2, linia 7) sprawdzamy, czy długość boku budowanego w aktualnie wyłonionej działce jest większa od aktualnie przyjętej wartości maksymalnej. Jeżeli jest większa (Listing 2, linia 8), modyfikujemy wartość zmiennej "maks". Czyścimy zawartość pomocniczej tablicy "nr_dzialek" (Listing 2, linia 11), w której przechowamy numery działek posiadających największy obszar kwadratowy wolny od znaku "X".

Następnie jako pierwszy element wspomnianej tablicy pomocniczej "nr_dzialek" wprowadzamy numer aktualnie badanej działki (Listing 2, linia 12). Zwiększamy też wartość zmiennej pomocniczej "ind" (Listing 2, linia 13), która oznacza numer indeksu dla pomocniczej tabeli "nr_dzialek".

Jeżeli funkcja ile() dla danej działki zwróci wartość równą do tej pory uznawanej za maksymalną (Listing 2, linia 15), numer działki zostaje dopisany do tablicy przechowującej numery działek o największym kwadracie (Listing 2, linia 16).

Działanie funkcji

Rysunek 1 - działanie funkcji

Klucz CKE

Zwróć uwagę na to, że inaczej rozwiązuje się zadanie z kluczem odpowiedzi, a inaczej, gdy nieznane są nam wyniki. Na maturze nie ma dostępu do klucza, dlatego zapoznanie się z kluczem odłóż na sam koniec Twoich ćwiczeń.

W nagłówku zdjęcie z Wenecji

Źródło: https://fshoq.com/free-photos/p/267/panorama-of-venice (publikowane na wolnych licencjach)