Намиране на броя цели числа в сферата с радиус R и измерение D, центрирано в Origin [duplicate] - c ++, алгоритъм, геометрия, изчислителна геометрия, теория на числата

Пиша компютърна програма / алгоритъм заброят на броя цели числа в сферата с радиус R и размер D центрирана в началото. По същество, ако имаме сфера с измерение 2 (кръг) и радиус 5, определям всички цели решения на неравенството X ^ 2 + Y ^ 2 ≤ 25. Вместо да броим всяка възможна целочислена точка, има ли ефективен начин да броим точките? Използвайки симетрия?

Отговори:

Да предположим, че измерението е 3 и R е радиусът. За z = 0, възможните координати x, y са точките в кръг с радиус R, а за всеки z, x, y "s са точките в кръг с радиус sqrt (R * R - z * z) , възможните стойности на z са -r, .. 0, 1, .. r където r е най-малкият цяло число по-малко от R. Забележете, че броят за z и -z ще бъде същият.

Когато стигнем до измерение 1, питаме колко числа отговарят на | i | <R, и това е 1 + 2 * r

Така:

int ncip( int dim, double R)
{
int i;
int r = (int)floor( R);
if ( dim == 1)
{   return 1 + 2*r;
}
int n = ncip( dim-1, R); // last coord 0
for( i=1; i<=r; ++i)
{   n += 2*ncip( dim-1, sqrt( R*R - i*i)); // last coord +- i
}
return n;
}

Е, използвайки симетрия, винаги можете просто да преброите всички цели решения на положителната страна и след това да обърнете компонентите. Така че, в случай на вашия кръг (D = 2, R = 5), трябва просто да намерите
{X, Y ∈ N: X 2 + Y 2 ≤ R}. След това създайте комбинациите (X, Y), (X, Y), (-X, Y), (-X, -Y)
Това ви оставя само (1/2)^д решения за намиране.

Също така можете да приближите кръг с радиус R като квадрат с радиус R / √2, така че всички комбинации от числа, по-малки или равни на тези, могат автоматично да се добавят.