Условие
Та же задача, но количество операций должно быть порядка
. (В предыдущем решении, как можно
подсчитать, порядка
n операций.)
Решение
Нас интересуют точки решётки (с целыми
координатами) в первом квадранте, попадающие внутрь круга
радиуса
. Интересующее нас множество (назовём
его
X) состоит из объединения вертикальных столбцов
убывающей высоты.
Идея решения состоит в том, чтобы " двигаться вдоль его
границы", спускаясь по верхнему его краю, как по
лестнице. Координаты движущейся точки обозначим <k,l>.
Введём ещё одну переменную s и будем поддерживать
истинность такого условия:
<k,l> находится сразу над k-ым столбцом;
s — число точек в предыдущих столбцах.
Формально:
- l — минимальное среди тех
l≥0, для
которых <k,l> не принадлежит X;
- s — число пар натуральных
x,y, для
которых
x < k и
<x,y> принадлежит X.
Обозначим эти условия через (И).
k := 0; l := 0;
while <0,l> принадлежит X do begin
| l := l + 1;
end;
{k = 0, l - минимальное среди тех l >= 0,
для которых <k,l> не принадлежит X}
s := 0;
{инвариант: И}
while not (l = 0) do begin
| s := s + l;
| {s - число точек в столбцах до k-го включительно}
| k := k + 1;
| {точка <k,l> лежит вне X, но, возможно, её надо сдвинуть
| вниз, чтобы восстановить И}
| while (l <> 0) and (<k, l-1> не принадлежит X) do begin
| | l := l - 1;
| end;
end;
{И, l = 0, поэтому k-ый столбец и все следующие пусты, а
s равно искомому числу}
Оценка числа действий очевидна: сначала мы движемся вверх
не более чем на
шагов, а затем вниз
и вправо — в каждую сторону не более чем на
шагов.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.29 |
