Plik punkty.txt zawiera 100 wierszy. W każdym wierszu znajdują się po dwie liczby całkowite z przedziału [-50, 50]. Pierwsza z nich oznacza współrzędną danego punktu, druga zaś współrzędną .
Napisz program, który dla punktów zapisanych w pliku punkty.txt wyliczy ich odległości od punktu . Zapisz te odległości zaokrąglone do dwóch miejsc po przecinku do pliku wynik.txt, w kolejności niemalejącej.
Odległość między dwoma punktami i wyliczamy ze wzoru:
Przykład 1
Dla danych:
Linia 1. 20 21.
Linia 2. minus 3 4.
Linia 3. 5 minus 12.
Linia 4. 8 15.
Linia 5. minus 6 minus 8.
20 21
-3 4
5 -12
8 15
-6 -8
wyniki powinny wyglądać następująco:
Linia 1. 5.
Linia 2. 10.
Linia 3. 13.
Linia 4. 17.
Linia 5. 29.
5
10
13
17
29
Do oceny oddajesz:
plik wynik.txt zawierający odpowiedź do zadania (odległości od punktu (0, 0) punktów zapisanych w pliku punkty.txt – odległości zapisane w kolejności niemalejącej),
plik(i) z komputerową realizacją zadania (kodem programu).
Twoim zadaniem jest opracowanie rozwiązania w wybranym przez siebie języku programowania: C++, Java lub Python. Odpowiedź do zadania dla danych z pliku znajdziesz pod omówieniem rozwiązania.
Rozwiązanie
Rozwiązanie zadania przedstawimy w postaci pseudokodu.
Na początku obliczymy odległości punktów z pliku z danymi od punktu (0,0). Następnie, za pomocą sortowaniasortowaniesortowania kubełkowego, posortujemy je niemalejąco i wpiszemy do pliku wynikowego, zaokrąglone do dwóch miejsc po przecinku.
Linia 1. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek.
Linia 2. punkty otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy ← wczytaj pierwszą liczbę z wiersza z pliku cudzysłów punkty kropka txt cudzysłów.
Linia 3. punkty otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy ← wczytaj drugą liczbę z wiersza z pliku cudzysłów punkty kropka txt cudzysłów.
Linia 4. przejdź do następnego wiersza.
Linia 6. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek.
Linia 7. odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy ← pierw otwórz nawias okrągły pot otwórz nawias okrągły punkty otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek 2 zamknij nawias okrągły plus pot otwórz nawias okrągły punkty otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy przecinek 2 zamknij nawias okrągły zamknij nawias okrągły.
Linia 9. maxi ← odległości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 10. mini ← odległości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 12. dla i znak równości 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek.
Linia 13. jeżeli odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maxi dwukropek.
Linia 14. maxi ← odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 15. jeżeli odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny mini dwukropek.
Linia 16. mini ← odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 18. r ← otwórz nawias okrągły maxi minus mini zamknij nawias okrągły prawy ukośnik 100.
Linia 20. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek.
Linia 21. d ← ułam otwórz nawias okrągły otwórz nawias okrągły odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy minus mini zamknij nawias okrągły prawy ukośnik r zamknij nawias okrągły.
Linia 23. jeżeli d znak równości 0 oraz odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy wykrzyknik znak równości mini dwukropek.
Linia 24. indeks podkreślnik kubełka ← całk otwórz nawias okrągły otwórz nawias okrągły odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy minus mini zamknij nawias okrągły prawy ukośnik r zamknij nawias okrągły minus 1.
Linia 25. w przeciwnym wypadku dwukropek.
Linia 26. indeks podkreślnik kubełka ← całk otwórz nawias okrągły otwórz nawias okrągły odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy minus mini zamknij nawias okrągły prawy ukośnik r zamknij nawias okrągły.
Linia 28. dopisz odległości otwórz nawias kwadratowy i zamknij nawias kwadratowy do kubełki otwórz nawias kwadratowy indeks podkreślnik kubełka zamknij nawias kwadratowy.
Linia 30. dla i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek 99 wykonuj dwukropek.
Linia 31. posortuj otwórz nawias okrągły kubełki otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 32. dla j znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek długość otwórz nawias okrągły kubełki otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły minus 1 wykonuj dwukropek.
Linia 33. zaokrąglij kubełki otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy do 2 miejsc po przecinku.
Linia 34. zapisz kubełki otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy w nowej linii w pliku cudzysłów wynik kropka txt cudzysłów.
dla i = 0, 1, ..., 99 wykonuj:
punkty[i][0] ← wczytaj pierwszą liczbę z wiersza z pliku "punkty.txt"
punkty[i][1] ← wczytaj drugą liczbę z wiersza z pliku "punkty.txt"
przejdź do następnego wiersza
dla i = 0, 1, ..., 99 wykonuj:
odległości[i] ← pierw(pot(punkty[i][0], 2) + pot(punkty[i][1], 2))
maxi ← odległości[0]
mini ← odległości[0]
dla i = 1, ..., 99 wykonuj:
jeżeli odległości[i] > maxi:
maxi ← odległości[i]
jeżeli odległości[i] < mini:
mini ← odległości[i]
r ← (maxi - mini) / 100
dla i = 0, 1, ..., 99 wykonuj:
d ← ułam((odległości[i] - mini) / r)
jeżeli d = 0 oraz odległości[i] != mini:
indeks_kubełka ← całk((odległości[i] - mini) / r) - 1
w przeciwnym wypadku:
indeks_kubełka ← całk((odległości[i] - mini) / r)
dopisz odległości[i] do kubełki[indeks_kubełka]
dla i = 0, 1, ..., 99 wykonuj:
posortuj(kubełki[i])
dla j = 0, 1, ..., długość(kubełki[i]) - 1 wykonuj:
zaokrąglij kubełki[i][j] do 2 miejsc po przecinku
zapisz kubełki[i][j] w nowej linii w pliku "wynik.txt"
Ważne!
W przedstawionym pseudokodzie użyliśmy funkcji pierw(), pot(), ułam() oraz całk():
pierw(x) – zwraca pierwiastek kwadratowy z x,
pot(a, b) – zwraca wartość liczby a podniesionej do potęgi b,
ułam(x) – zwraca część ułamkową liczby x,
całk(x) – zwraca część całkowitą liczby x.
Użyliśmy również funkcji posortuj(), która służy do posortowania danego kubełka z odległościami punktów. Na egzaminie maturalnym nie można korzystać z wbudowanych funkcji sortujących – należy zaimplementować dowolną z nich. My skorzystamy z algorytmu sortowania przez wstawianie. Przykładowa implementacja funkcji sortującej wygląda następująco:
Linia 1. funkcja posortuj otwórz nawias okrągły tab zamknij nawias okrągły dwukropek.
Linia 2. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka kropka n minus 1 wykonuj dwukropek.
Linia 3. pom ← tab otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 4. j ← i minus 1.
Linia 5. dopóki j zamknij nawias ostrokątny znak równości 1 oraz tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny pom wykonuj dwukropek.
Linia 6. tab otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy ← tab otwórz nawias kwadratowy j zamknij nawias kwadratowy.
Linia 7. j ← j minus 1.
Linia 8. tab otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy ← pom.
funkcja posortuj(tab):
dla i = 1, 2, .... n - 1 wykonuj:
pom ← tab[i]
j ← i - 1
dopóki j >= 1 oraz tab[j] > pom wykonuj:
tab[j + 1] ← tab[j]
j ← j - 1
tab[j + 1] ← pom
Odpowiedź
Odpowiedź do zadania dla danych z pliku punkty.txt:
RULNXFbuDUScs
Przycisk do pobrania pliku TXT z wynikiem zadania.