В целочисленных координатах $%(x,y)$% вычислить все точки окружности с центром в целочисленных координатах $%(x_0, y_0)$% и натуральным радиусом $%R$%. (Необходимо придумать наиболее эффективный алгоритм вычисления этих точек относительно числа арифметических операций)

задан 10 Июл 18:06

изменен 10 Июл 18:07

10|600 символов нужно символов осталось
1

Достаточно найти все решения уравнения $%a^2+b^2=R$% в целых неотрицательных числах. Можно также положить $%a\le b$%, но это не даст экономии, если все решения потом всё равно надо будет выписать.

Зная все пары вида $%(a,b)$%, мы добавляем к ним симметричные пары вида $%\pm a,\pm b)$% (для любого набора знаков), и прибавляем их к $%(x_0,y_0)$%. Это даёт все значения для $%(x,y)$%.

Можно также заметить, что для $%R$% вида $%4k+3$% множество решений будет пусто, так как квадрат целого числа при делении на 4 даёт в остатке 0 или 1. Кроме того, если $%R$% делится на 4, то оба числа $%a$%, $%b$% должны быть чётными. Тогда задача сводится к поиску решений для $%R/4$% вместо $%R$%. Так мы делим на 4 столько раз, сколько возможно, и полученное новое число снова проверяем на предмет представления в виде $%4k+3$%. Скажем, если было $%R=112$%, то после двух делений на 4 получится значение 7, и в этом случае решений нет.

Таким образом, всё сводится к случаю, когда $%R$% даёт остаток 1 или 2 от деления на 4. Здесь можно составить массив из точных квадратов: 0, 1, 4, ... , $%n^2$%, где $%(n+1)^2 > R$%. Далее сравниваем этот массив с другим упорядоченным по возрастанию массивом $%R-n^2$%, ... , $%R-1$%, $%R$%, и при чтении обоих массивов один раз отыскиваем общие элементы. Если $%i$%-й элемент первого массива совпал с $%j$%-м элементом второго, то мы получили решение $%(a,b)=(i,n+1-j)$% (номера элементов в процессе чтения запоминаем, чтобы специально не искать).

ссылка

отвечен 10 Июл 19:08

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×166

задан
10 Июл 18:06

показан
112 раз

обновлен
10 Июл 19:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru