Punkty kratowe
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.
Spis treści
Czym są punkty kratowe
Definicja jest bardzo prosta i łatwa do zapamiętania:
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)\))
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
Spójrzmy na przykładowy rysunek:
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.
#include <iostream>
#include <cstdlib>
#include <math.h>
using namespace std;
int kratowe(float r)
{
int ilosc = 0;
// wzor to x^2 + y^2 = r^2
for (int x = 0; x<r; x++)
for (int y = 1; y<=r; y++)
if ((x*x + y*y) <= r*r)
ilosc++;
ilosc = ilosc * 4 + 1;
return ilosc;
}
int main()
{
float pkt;
cout << "Podaj promien R" << endl;
cin >> pkt;
cout << kratowe(pkt) << endl;
system("PAUSE");
return(0);
}
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\)):
#include <iostream>
#include <cstdlib>
#include <math.h>
using namespace std;
int kratowe(float r)
{
int ilosc = 0;
// wzór: Y = sqrt(R^2 - X^2)
for (int x = 0; x <= r; x++)
ilosc += sqrt(r*r - x*x);
ilosc *= 4; // ilość cwiartek
ilosc++; // dodajemy środek
return ilosc;
}
int main()
{
float pkt;
cout << "Podaj promien R" << endl;
cin >> pkt;
cout << kratowe(pkt) << endl;
system("PAUSE");
return(0);
}
