P-Programowanie

Punkty kratowe

6 stycznia 2013, kategoria: Matura z informatyki

Punkty kratowe – to pojęcie przysporzyło sporych kłopotów wszystkim uczniom na egzaminie maturalnym. Szczerze mówiąc punkty kratowe nie są zbyt popularne, nie omawia się ich na lekcjach matematyki w szkole średniej. Ich obliczanie jest proste, jednak wiele osób polegało już na wstępie – kombinowali w zły sposób od samego początku, skutkiem czego albo brakowało czasu albo program działał źle.

Czym są punkty kratowe

Punkt kratowy to punkty należący do układu kartezjańskiego, którego współrzędne są liczbami całkowitymi [np. (0,0), (1,0), (2,1) itd.]

Biorąc pod uwagę powyższą definicję, stwierdzamy że punkty kratowe to przecięcia osi X,Y dla liczb całkowitych w układzie współrzędnych

Ilość punktów kratowych w okręgu o promieniu R

punkty-kratowe

Chcąc obliczyć ilość punktów kratowych znajdujących się w danym okręgu o promieniu R, trzeba skorzystać ze wzoru na okręg w układzie współrzędnych.

{(x-a)}^{2}+{(y-b)}^{2}={r}^{2}

Liczby (a,b) to środek okręgu. Ponieważ nasz okręg zawsze zaczyna się od (0,0) można uprościć wzór:

{x}^{2}+{y}^{2}={r}^{2}

Teraz wystarczy podstawić do wzoru odpowiednie liczby. Promień jest stały, otrzymamy go w treści zadania. Współrzędne X,Y to współrzędne odpowiednich punktów kratowych. Jest sens sprawdzać tylko punkty, które są liczbami całkowitymi.

Zamiast równania można zbudować nierówność:

{x}^{2}+{y}^{2}\leq {r}^{2}

W przypadku kiedy jest ona spełniona, punkt kratowy o współrzędnych (x,y) leży wewnątrz okręgu o promieniu r.

Rozwiązanie pierwsze (2 pętle for dla jednej ćwiartki)

Licząc punkty kratowe dla danego R, można podstawiać liczby bezpośrednio do wzoru podanego wyżej. X, Y osiągniemy dzięki dwóm zagnieżdżonym pętlom for. Nie ma sensu sprawdzać X,Y dla liczb większych od promienia R. Oczywiste jest, że jeżeli promień wynosi 4, a X wynosi 5, to nie ma prawa być tam żadnego punktu kratowego.

W pętli liczymy punkty kratowe tylko dla jednej ćwiartki, następnie mnożymy przez 4 oraz dodajemy 1  (pkt 0,0). Ważne! Pierwsza pętla będzie działać od 0 do R. Druga pętla musi działać od 1 do R. Są 4 ćwiartki i 4 osie. Jeżeli liczymy pkt dla jednej ćwiartki i mnożymy razy 4, to liczymy też tylko jedną oś! Dlatego współrzędna X zaczyna się od 0, a Y od 1.

Rozwiązanie drugie(1 pętla for dla jednej ćwiartki)

Można nieco przekształcić nasz wzór i wyznaczyć z niego Y:

y=\sqrt{r^2-x^2}

Podstawiając za X liczby od 0 do R, Y będzie przyjmował ilość punktów kratowych leżących na danej prostej. Wynik sumujemy i mnożymy razy 4, oraz dodajemy 1 (środek 0,0):

Komentarze:

Użytkownik Mateusz napisał/a:

14 lutego 2013


Hmm, nie jestem pewny czy jak liczysz sobie od 1 do r pierwiastkiem to wynik będzie poprawny.
No ale mniejsza. Tak czy siak podałeś rozwiązanie w czasie (r log2 r). Co moim zdanie nie dostanie maksymalnej ilości pkt.
Istnieje bowiem rozwiązanie liniowe po r. Tzn korzystamy z tego wzoru co masz podane, jednak zakladamy ze na poczatku mamy k = r+1 elementow.
Teraz jedziemy od 1 do r i sprawdzamy czy k spelnia nasze rownanie jesli jest za duze to zmniejszamy go o 1. Gdy k spelni warunek to dodajemy go do wyniku. Drugim plusem tego rozwiazania jest to ze nie bawimy sie we float i mamy pewnosc ze wynik sie nam nie zepsuje. Dla lepszej intepretacji masz kod:
http://bpaste.net/show/77313/

Użytkownik Arek napisał/a:

19 lutego 2013


„…No ale mniejsza. Tak czy siak podałeś rozwiązanie w czasie (r log2 r). Co moim zdanie nie dostanie maksymalnej ilości pkt…
Istnieje bowiem rozwiązanie liniowe po r…”

uuuhuu, zawiało bezrobociem i słomianym zapałem

Użytkownik Karol napisał/a:

19 lutego 2013


Liczy się klucz odpowiedzi. Nie mam czasu szukać klucza do arkusza, ale jestem pewien że przejdzie dowolne rozwiązanie dające poprawny wynik. Jak na poziom matury z inf zadanie było za trudne. Wzór wpadł mi do głowy jako pierwszy. Można by się pomartwić co się dzieje w przypadku ultra dużego promienia koła, gdy największy okręg przechodzi praktycznie przez 3 punkty na raz.

Na maturze przeważnie oceniają złożoność czasową algorytmów sortowania, aby czasem maturzysta nie wymyślił jakiegoś dziadostwa sortującego 10 liczb przez 10 minut, tylko trzymał się gotowych sprawdzonych „wzorców”, choć może wzorzec to za mocne określenie na kilka znanych algorytmów.

Użytkownik AAaaa napisał/a:

03 czerwca 2014


Algorytm z pierwiastkiem moim zdaniem jest błędny!!!

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0

Zachęcam Cię do polubienia bloga na facebooku! Dając lajka wspierasz moją pracę - wszystkie artykuły na blogu są za darmo!