Obliczanie objętości N - wymiarowej kuli

kolnierz
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 16 paź 2007, o 16:49
Płeć: Mężczyzna
Lokalizacja: Żagań
Podziękował: 3 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: kolnierz »

Witam!
Jestem jeszcze świeży jeżeli chodzi o programowanie, i mam pewien problem z zadaniem, w którym mamy napisać program zliczający punkty o współrzędnych całkowitych należące do kuli w n wymiarze ( mamy go podać z klawiatury ) i o podanym promieniu. I tak dla pierwszego wymiaru łatwo zauważyć ze zawsze będzie to 2*promień+1 (czyli punkt środka) dla drugiego wymiaru ułożyłem pętle równiez poprawnie zliczającą punkty:

Kod: Zaznacz cały

for(int i=0; i<=promien; i++)
    for(int j=0; j<=promien; j++)
        if(i*i+j*j<=promien*promien) 
            n++;
n=4*n-4*promien-3;

gdzie n, jest liczbą tych punktów, jednak już przy 3 wymiarze nie jest tak łatwo i pewnie dalej będzie jeszcze trudniej, dlatego moje pytanie jest takie czy istnieje jakiś sprytny wzór na wyliczenie takich rzeczy, a jeżeli nie to prosiłbym o jakieś wskazówki które wniosłyby coś do tematu.

Z góry dziękuję!

Oczywiście piszę w c++.
spajder
Użytkownik
Użytkownik
Posty: 735
Rejestracja: 7 lis 2005, o 23:56
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 2 razy
Pomógł: 133 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: spajder »

Kula (w każdym wymiarze) jest zdefiniowana jako zbiór punktów, których odległość od środka jest równa conajwyżej promieniowi (nierówność może być ostra lub nieostra). Przy metryce kartezjańskiej wychodzi:

\(\displaystyle{ P \in K_A^r \Leftrightarrow |PA| < r \Leftrightarrow \sqrt{\sum\limits_{i=1}^{n}\left(P_i - A_i\right)^2} < r}\)

oznaczenia mam nadzieję jasne (jak nie to dopiszę).
kolnierz
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 16 paź 2007, o 16:49
Płeć: Mężczyzna
Lokalizacja: Żagań
Podziękował: 3 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: kolnierz »

\(\displaystyle{ \left|PA \right|}\) to odległość od środka, tak? czyli powinienem stworzyć pętle wyliczającą odległość każdego punktu od środka? tylko, że to będzie miało bardzo dużą złożoność, nie da się działać np. rekurencyjnie i obliczać odległości w jakiś sprytniejszy sposób?
abc666

Obliczanie objętości N - wymiarowej kuli

Post autor: abc666 »

Ja bym jeszcze proponował liczyć od góry, tzn od brzegu kuli, bo jeśli punkt dalszy należy to i bliższy. Poza tym zauważ że przy n-tym wymiarze konieczne do sprawdzenia jest tylko \(\displaystyle{ \left( \frac{1}{4} \right) ^{n-1}}\) część przestrzeni z uwagi na symetrię kuli + ewentualne punkty na "brzegu" tej części.


edit do n-1 oczywiście, a dla n=1 \(\displaystyle{ \frac{1}{2}}\)
kolnierz
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 16 paź 2007, o 16:49
Płeć: Mężczyzna
Lokalizacja: Żagań
Podziękował: 3 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: kolnierz »

No to teoretycznie każdy wyższy wymiar to jedna petla for więcej, tak? teraz np. w 3 wymiarze powinno działać to tak że:

Kod: Zaznacz cały

         for(int i=0; i<=promien; i++)
         for(int j=0; j<=promien; j++)
         for(int k=0; k<=promien; k++) // to będą kombinacje punktów
         if(i*i+j*j+k*k<=promien) n++; 
         ilosc_pkt=8*n;

Tylko jak to w ten sposób napisałem to np. dla promienia 1 tych punktów powinno być 7, a mi wychodzi inaczej. Trzeba odjąć te które będą się powtarzały, czyli np. 0,0,0 będzie 8 razy. Ale jak znaleźć resztę takich.
abc666

Obliczanie objętości N - wymiarowej kuli

Post autor: abc666 »

Jednak pomysł z liczeniem tak małej części jest zły, ponieważ wchodzą kąty inne niż proste.

Co do rekurencji to można to zrobić tak: kulę "tniemy" w punktach całkowitych otrzymując kule z mniejszego wymiaru. Np. dla n=2 przekroje przez punkty całkowite (np. poziomo) dają nam kule wymiaru 1 czyli odcinki dla których już łatwo policzyć liczbę punktów. Dodatkowo trzeba jeszcze liczyć promień tych kul mniejszego wymiaru.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: Zordon »

takie rzeczy sie liczy rekurenycjnie np. badając wszystkie punkty kratowe hipersześcianu zawierającego taką kulę
kolnierz
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 16 paź 2007, o 16:49
Płeć: Mężczyzna
Lokalizacja: Żagań
Podziękował: 3 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: kolnierz »

Ja ten program właśnie wysłałem zagnieżdżając kolejne for'y. np. dla 10 wymiaru zlicza te punkty w najbardziej trywialny sposób:

Kod: Zaznacz cały

for(int i=-promien; i<=promien; i++)
                            for(int j=-promien; j<=promien; j++)
                            for(int k=-promien; k<=promien; k++)
                            for(int r=-promien; r<=promien; r++)
                            for(int s=-promien; s<=promien; s++)
                            for(int f=-promien; f<=promien; f++)
                            for(int q=-promien; q<=promien; q++)
                            for(int e=-promien; e<=promien; e++)
                            for(int t=-promien; t<=promien; t++)
                            for(int g=-promien; g<=promien; g++)
                                    if(i*i+j*j+k*k+r*r+s*s+f*f+q*q+e*e+t*t+g*g<=promien*promien) n++;
Testerka przyjęła, ale mi nie podoba się, że działa to tak nieprzyzwoicie długo. Teraz nie będę mógł odpisywać, bo mam sprawę do załatwienia, później przeczytam wasze posty bo nie wierze że nie można tego zrobić szybciej i prościej...
abc666

Obliczanie objętości N - wymiarowej kuli

Post autor: abc666 »

No ale czego liczysz od dołu a nie od góry?
kolnierz
Użytkownik
Użytkownik
Posty: 46
Rejestracja: 16 paź 2007, o 16:49
Płeć: Mężczyzna
Lokalizacja: Żagań
Podziękował: 3 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: kolnierz »

No pisałeś ze od góry , ale nie bardzo wiedziałem jak to pojechałem tak trywialnie. Wiem, że to nie ładne i jest ogromna złożoność, ale naprawdę nie miałem lepszego pomysłu.
abc666

Obliczanie objętości N - wymiarowej kuli

Post autor: abc666 »

rekurencyjnie

Kod: Zaznacz cały

pro(R,n) {
   return sqrt(R*R-n*n);
}

ile(N,R) {
   if(N == 1) {
      return 2*floor(R)+1;
   } else {
      tmp=ile(N-1,R); //zliczamy punkty z "koła wielkiego kuli"
      //zliczamy punkty z mniejszych kul, dalej od środka
      for(i=1;i<=R;i++) {
         tmp+=2*ile(N-1,pro(R,i));
      }
      return tmp;
   }
} 
Dumel
Użytkownik
Użytkownik
Posty: 2000
Rejestracja: 19 lut 2008, o 17:35
Płeć: Mężczyzna
Lokalizacja: Stare Pole/Kraków
Podziękował: 60 razy
Pomógł: 202 razy

Obliczanie objętości N - wymiarowej kuli

Post autor: Dumel »

tak się przypadkiem złożyło że też to świństwo (no to może troche przesada) dzisiaj musiałem napisać
zrobiłem tak:

Kod: Zaznacz cały

void zliczaj(int N, int R, int* suma, int mnoznik)
{
        if(N==0)
           *suma=*suma+mnoznik;
        else
        {
                zliczaj(N-1, R, suma, mnoznik);

                double x=sqrt((double)R);
                for(int i(1); i<=x; ++i)
                zliczaj(N-1, R-i*i, suma, mnoznik*2);
        }
}
na poczatku wywolujemy

Kod: Zaznacz cały

zliczaj(N,r*r, suma, 1);
ODPOWIEDZ