Całkowite punkty w okregu

2015-12-01 15:58
Studentpascala
0

Witam. Chciałbym uzyskać jakieś wskazówki dotyczące programu do którego nie wiem jak się zabrać.
Treść:
Podaj ilość punktów całkowitych należących do okręgu o promieniu r . Środek okręgu to (0,0). Promień wpisywany z klawiatury.

Po przemyśleniach i wyrysowaniu sobie tego graficznie na papierze wpadłem na pomysł ( o ile wgl jest dobry) ze po wprowadzeniu promienia, można ten duży okrąg podzielić na małe i zaliczać ich punkty. A do zaliczania punktów użyłbym 2 pętli jedna do x a druga w niej do y. Sęk w tym ze nie mam pomysłu jak to napisać i chciałbym uzyskać jakieś wskazówki.

P.s jestem początkujący, ale dużo rzeczy rozumiem.

Pozostało 580 znaków

2015-12-01 16:04
0

A skąd te punkty?


programowanie, smallworld, grafika, fotografia

Pozostało 580 znaków

2015-12-01 16:05
misiakufal_not_logge
0

jeśli środek to 0,0 i masz promień r to przelatujesz po forze(X) w forze(y) współrzędne X i Y w zakresie -r/2; r/2 i mając w tej sposób współrzędne sprawdzasz czy odległosć danego punktu od punktu 0,0 jest mneijsza lub równa r.

Pozostało 580 znaków

2015-12-02 10:51
0

Może stary artykuł Krashana się Tobie przyda :) Jest tam troszkę inne podejście do tematu: http://teleinfo.pb.edu.pl/krashan/articles/elipsy/


Ogólnie na prace domowe mam stawki zaporowe. Czasem coś o programowaniu znajdzie się na mojej stronie

Pozostało 580 znaków

2015-12-02 14:27
msm
2

Domyślam się że chodzi o koło a nie okrąg. Więc:

Rozwiązanie O(n^2):

result = 0;
for x in [-r; r]:
    for y in [-r; r]:
        if inside_circle(x, y):
           result++
return result;

Gdzie inside_circle to funkcja sprawdzająca czy dany punkt leży w szukanym kole (to trywialne i wynika bezpośrednio z równania koła).

Rozwiązanie O(n):

result = 0
for x in [-r; r]:
    result += vertical_points(x) * 2 - 1
return result

Gdzie vertical_points(x) to funkcja mówiąca jak wiele całkowitych punktów znajduje się w kole dla danej współrzędnej x, powyżej osi OX:

443fd308d2.png
(zaawansowana ilustracja przykładowa, tutaj vertical_points(1) = 6, vertical_points(2) = 5, vertical_points(3) = 5, vertical_points(4) = 4, vertical_points(5) = 2).

Jak tą funkcję zdefiniować (bez pętli)?

x^2+y^2<=r^2
y^2<=r^2-x^2    // tylko y >= 0
y <= sqrt(r^2-x^2)

(przy czym wynikiem jest floor(y), bo bierzemy pod uwagę tylko punkty całkowite).

PS. Wszystkie przykłady dla kół o środku w (0, 0), ale bardzo prosto to uogólnić do dowolnie położonych kół.

PPS. Obie funkcje można przyśpieszyć o stałą, zauważając że wystarczy wyliczyć ilośc punktów w ćwiartce/połowie koła, i pomnożyć razy cztery/dwa. Ale komplikowało to rozwiązanie (trzeba pilnować żeby dwa razy nie policzyć jednego punktu) więc nie zostało tu zaimplementowane.

PPPS. Czy da się to zrobić w czasie lepszym niż O(n) - nie wykluczam, ale nie mam pomysłu z głowy od razu.
Może np. jakiś matematyk potrafiłby znaleźć na to bezpośredni wzór, bez żadnych petli.

edytowany 4x, ostatnio: msm, 2015-12-02 14:33
Ad PPS, żeby się nie trzeba było pilnować: 4*(ilość w ćwiartce bez osi) + 4*floor(r) + 1. - bogdans 2015-12-02 16:51

Pozostało 580 znaków

2015-12-02 14:40
1

Może by potrafił. https://en.wikipedia.org/wiki/Gauss_circle_problem


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 1x, ostatnio: bogdans, 2015-12-02 15:03

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0