Алгоритм нахождения количества квадратов в данном круге
Вот мой рисунок: CLICK
Мне нужно написать программу, которая найдет количество квадратов (1×1), которые мы можем нарисовать в круг заданного радиуса. Квадраты можно только нарисовать полностью и поместить как блоки lego — один на другой. В некоторых случаях вершины квадратов могут лежать на окружности.
Примеры: для 1 — 0, для 2 — четыре, для 3-16 квадратов, для 4-32, для 5-52.
Я написал что-то, но он не работает нормально для 5+ (я имею в виду — радиус больше 5). Здесь это идет: CLICK. В моем коде r — радиус круга, сумма — сумма всех квадратов, а высота — высота треугольников, которые я пытаюсь «нарисовать» в круге (используя теорему Пифагора).
Теперь какая-нибудь помощь? Мой алгоритм хоть верный? Должен ли я что-то изменить?
Решение
Есть Круговая проблема Гаусса это дает формулу для подсчета целых точек внутри круга данного радиуса. Вы можете использовать эту логику для подсчета квадратов, которые лежат в круге.
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
Другие решения
Первый выкл — круг с радиусом 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;
То, что он делает, это просто подсчитывает квадраты внутри одной восьмой круга, за пределами вписанного квадрата. Извините за мое хипстерское форматирование и слишком подробные имена переменных.