Алгоритм нахождения количества квадратов в данном круге

Вот мой рисунок: CLICK

Мне нужно написать программу, которая найдет количество квадратов (1×1), которые мы можем нарисовать в круг заданного радиуса. Квадраты можно только нарисовать полностью и поместить как блоки lego — один на другой. В некоторых случаях вершины квадратов могут лежать на окружности.

Примеры: для 1 — 0, для 2 — четыре, для 3-16 квадратов, для 4-32, для 5-52.

Я написал что-то, но он не работает нормально для 5+ (я имею в виду — радиус больше 5). Здесь это идет: CLICK. В моем коде r — радиус круга, сумма — сумма всех квадратов, а высота — высота треугольников, которые я пытаюсь «нарисовать» в круге (используя теорему Пифагора).

Теперь какая-нибудь помощь? Мой алгоритм хоть верный? Должен ли я что-то изменить?

0

Решение

Есть Круговая проблема Гаусса это дает формулу для подсчета целых точек внутри круга данного радиуса. Вы можете использовать эту логику для подсчета квадратов, которые лежат в круге.

N = 4 * Sum[i=1..R] (Floor(Sqrt((R^2-i^2)))

пример:

R = 3
i=1   n1 = Floor(Sqrt(9-1))~Floor(2.8)=2
i=2   n2 = Floor(Sqrt(9-4))~Floor(2.2)=2
i=3   n2 = Floor(Sqrt(9-9))=0
N=4*(n1+n2+n3)=16
2

Другие решения

Первый выкл — круг с радиусом 5 подходит для 60 квадратов 1×1, а не 52. Моя ставка была бы, если бы кто-то не считал очки {[3,4], [3, -4], [4,3], [4, -3], [- 4,3], [- 4, -3], [- 3,4], [- 3, -4]} при рисовании на бумаге и подсчете от руки, будучи неуверенными, правы ли они на круге или просто вне его. Они точно на круге.

второй — Ответ MBo привел меня сюда — я иногда ищу в StackOverflow задачу на круг Гаусса, чтобы узнать, предложил ли кто-нибудь какой-нибудь новый, забавный алгоритм.

В третьих — вот код:

int     allSquares=0,
squaredRadius=radius*radius,
sideOfQuarterOfInscribedSquare=(int)(long)(radius/sqrt(2));
for(int x=sideOfQuarterOfInscribedSquare+1;
x<radius;
x++){
allSquares+=(long)sqrt(squaredRadius-x*x);
}
allSquares= allSquares*8+4*sideOfQuarterOfInscribedSquare*sideOfQuarterOfInscribedSquare;
return allSquares;

То, что он делает, это просто подсчитывает квадраты внутри одной восьмой круга, за пределами вписанного квадрата. Извините за мое хипстерское форматирование и слишком подробные имена переменных.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector