Zadanie 3
Matura z informatyki, maj 2025, poziom rozszerzony
Wymaganie: P.I.3) sprawdza poprawność działania algorytmów dla przykładowych danych. P.I.2) stosuje przy rozwiązywaniu problemów z różnych dziedzin algorytmy poznane w szkole podstawowej oraz algorytmy: a) na liczbach […]. P.II.1) projektuje i programuje rozwiązania problemów z różnych dziedzin […]. I.4) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. II.2) sprawnie posługuje się zintegrowanym środowiskiem programistycznym przy pisaniu, uruchamianiu i testowaniu programów.
Treść zadania
Zadanie 3. Dron
Tor lotu pewnego drona składa się z prostych odcinków. Lot rozpoczyna się w punkcie (0, 0), a kończy w punkcie (20000, 0). Dron poza startem i lądowaniem jest zawsze na wysokości większej od zera.
Plik dron.txt zawiera 100 wierszy, w których zapisano dane dotyczące ruchu drona. W każdym wierszu jest zapisana para liczb całkowitych rozdzielonych znakiem spacji. Pierwsza liczba oznacza przemieszczenie drona (odległość) w poziomie od ostatniej pozycji – jest to zawsze liczba dodatnia. Druga liczba oznacza przemieszczenie w pionie od ostatniej pozycji. Jeśli druga liczba jest dodatnia, to dron wykonał ruch w górę, jeśli ujemna – w dół, a jeśli równa 0 – nie zmieniał wysokości.
Przykład 1. Dla przykładowych danych:
3000 2000
2000 9000
5000 -7000
5000 4000
3000 6000
2000 -14000
dron znajduje się kolejno w punktach (3000, 2000), (5000, 11000), (10000, 4000), (15000, 8000), (18000, 14000) i (20000, 0) (w arkuszu tor lotu pokazano na wykresie).
Napisz program (lub kilka programów), który(-e) znajdzie(-dą) odpowiedzi dla podanych zadań. Każdą odpowiedź zapisz w pliku wyniki3.txt i poprzedź ją numerem oznaczającym zadanie.
Do Twojej dyspozycji jest plik dron_przyklad.txt zawierający 10 wierszy danych w opisanej postaci. Odpowiedzi dla pliku dron_przyklad.txt są podane pod każdym zadaniem. Pamiętaj, że Twój program musi ostatecznie zadziałać na pliku dron.txt zawierającym 100 wierszy danych.
Zadanie 3.1. (0–2)
Dla każdego przesunięcia [A, B] zapisanego w pliku dron.txt oblicz największy wspólny dzielnik (NWD) wartości bezwzględnych liczb A i B. Podaj liczbę par [A, B], dla których największy wspólny dzielnik wartości bezwzględnych liczb A i B jest większy od 1.
Uwaga: przyjmujemy, że NWD(A, 0) = A.
Odpowiedź dla pliku dron_przyklad.txt to 6.
Zadanie 3.2. (0–4)
Rozważmy wszystkie punkty, w których dron znajdował się po wykonaniu kolejnych ruchów (przesunięć). Dla danych z przykładu 1. będą to punkty: (3000, 2000), (5000, 11000), (10000, 4000), (15000, 8000), (18000, 14000) i (20000, 0).
a) Podaj, ile spośród wszystkich rozważanych punktów znajduje się wewnątrz kwadratu o wierzchołkach (0, 0), (0, 5000), (5000, 5000), (5000, 0). Nie liczymy punktów leżących na krawędziach kwadratu.
b) Spośród wszystkich rozważanych punktów znajdź i podaj trzy różne, takie, że jeden z nich jest środkiem odcinka o końcach w pozostałych dwóch. Jest tylko jedna taka trójka punktów.
Uwaga: punkty należące do szukanej trójki nie muszą być trzema kolejnymi punktami, do których przemieszczał się dron.
Odpowiedź dla pliku dron_przyklad.txt to:
a) 2
b) (14000, 3014), (16000, 2010), (18000, 1006)
![Wykres toru lotu drona dla przykładowych danych: łamana od punktu (0, 0) do (20000, 0) z opisanymi przemieszczeniami [poziomo, pionowo] na kolejnych odcinkach.](/zadania/informatyka/2025-maj-pr/zad-03-1.webp)
Źródło: arkusz CKE MINP-R0-100-2505. Otwórz oryginalny PDF
Rozwiązanie
Odpowiedzi z zasad oceniania CKE:
- 3.1. 40
- 3.2. a) 24; b) punkty (5832, 1801), (7410, 1990), (8988, 2179) — środkiem odcinka jest (7410, 1990).
Wczytanie danych i wyznaczenie punktów (wspólne dla obu zadań):
from math import gcd
ruchy = []
punkty = []
x, y = 0, 0
with open("dron.txt") as f:
for linia in f:
a, b = map(int, linia.split())
ruchy.append((a, b))
x += a
y += b
punkty.append((x, y))
3.1. math.gcd przyjmuje liczby ujemne i zwraca wynik nieujemny; gcd(a, 0) = a, zgodnie z uwagą w treści:
print(sum(1 for a, b in ruchy if gcd(abs(a), abs(b)) > 1))
3.2 a) Punkty ściśle wewnątrz kwadratu (bez krawędzi):
print(sum(1 for x, y in punkty if 0 < x < 5000 and 0 < y < 5000))
3.2 b) Dla każdej pary punktów liczymy środek odcinka i sprawdzamy, czy jest wśród punktów:
zbior = set(punkty)
for i in range(len(punkty)):
for j in range(i + 1, len(punkty)):
(x1, y1), (x2, y2) = punkty[i], punkty[j]
if (x1 + x2) % 2 == 0 and (y1 + y2) % 2 == 0:
s = ((x1 + x2) // 2, (y1 + y2) // 2)
if s in zbior and s != punkty[i] and s != punkty[j]:
print(punkty[i], s, punkty[j])
W 3.1 liczymy NWD wartości bezwzględnych (druga liczba bywa ujemna), a dla B = 0 przyjmujemy NWD(A, 0) = A — taka para też się liczy, jeśli A > 1. W 3.2 a) punkty na krawędziach kwadratu nie są liczone, więc nierówności muszą być ostre. W 3.2 b) punkty to pozycje po kolejnych ruchach (sumy przesunięć), a nie same przesunięcia; środek odcinka może mieć współrzędne niecałkowite — takie pary od razu odrzucamy. Szukana trójka nie musi składać się z kolejnych punktów lotu, więc trzeba sprawdzić wszystkie pary.
Strona arkusza CKE z treścią zadania
Rozwiązanie krok po kroku
Wspólne wczytanie danych
Trasa drona to ciąg odcinków: każdy wiersz pliku to przyrosty (Δx, Δy). Iteracyjnie kumulujemy pozycję bieżącą, zaczynając od (0, 0). Wszystkie podzadania korzystają z tej samej listy pozycji/ruchów.
Maksymalna wysokość
To max po współrzędnej y wszystkich punktów łamanej.
Długość trasy
Suma długości odcinków: dla każdego ruchu (Δx, Δy) długość to √(Δx² + Δy²). Sumujemy po wszystkich 100 odcinkach.
Zliczanie zmian kierunku
Iterujemy po znakach Δy (pomijając Δy = 0). Zliczamy momenty, w których znak zmienia się względem poprzedniego niezerowego odcinka.
Rozumiesz, jak to rozwiązać?
Przećwicz podobne typy zadań w aplikacji
matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „dron, geometria, NWD, środek odcinka, parsowanie pliku, śledzenie pozycji” zrobisz samodzielnie.
Otwórz matury-online.pl