Обобщение "алгоритма счета"

Рассмотрим теперь класс (n, k, 1)-алгоритмов, действующих на отрезке AB (Рис.1).

Первый шаг 'оптимального' (n, k, 1)-алгоритма
Рисунок 1. Первый шаг "оптимального" (n, k, 1)-алгоритма.

Что означает (n, , 1)-алгоритм? Напомним, что ограничение S º 1 означает, что "индикаторные элементы" движутся вдоль отрезка AB только в одном возможном направлении от точки A к точке B. Это означает, что если ИЭ на некотором шаге оказывается справа от измеряемой точки X, то этот ИЭ "выбывает из игры", то есть не может быть использован в дальнейшем в процессе измерения. Ярким примером ограничения S º 1 является рассмотренный выше "алгоритм счета".

Мы не хотели бы утомлять нашего читателя тонкостями математических рассуждений и приведем окончательный результат для этого случая. Доказано, что функция "эффективности" F(n, k) выражается через биномиальные коэффициенты, то есть:

(1)

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

 012345...n
0111111...1
1123456...F(n, 1)
2136101521...F(n, 2)
31410203556...F(n, 3)
415153570126...F(n, 4)
5162156126252...F(n, 5)
...........................
k1F(1, k)F(2, k)F(3, k)F(4, k)F(5, k)...F(n, k)

Действие "оптимального" (n, k, 1)-алгоритма может быть продемонстрировано с помощью "арифметического квадрата". Действительно, для заданных n и k значение функции F(n, k) находится на пересечении n-го столбца и k-й строки "арифметического квадрата". Координаты точек приложения k ИЭ на отрезке AB (точки C1, C2, ..., Cj, Cj+1, ... , Ck) относительно точки A (Рис.1) находятся в n-м столбце "арифметического квадрата", то есть:

AC1 = 1, AC2 = F(n, 1), ..., ACj = F(n, j-1), ACj+1 = F(n, j), ... , ACk = F(n, k-1).(2)

Если после первого шага алгоритма j ИЭ оказываются слева от точки X, а оставшиеся (k - j) ИЭ - справа от точки X, "интервал неопределенности" относительно точки X уменьшается до отрезка CjCj+1. Длина этого отрезка равна F(n - 1, j). Этот биномиальный коэффициент находится на пересечении (n - 1)-го столбца и j-й строки "арифметического квадрата". Чтобы получить биномиальный коэффициент F(n - 1, j), мы должны сдвинуться от начального коэффициента F(n, k) на один столбец влево и (k - j) строк вверх.

На втором шаге мы начинаем рассматривать точку Cj как новое начало координат. При этом 2-й шаг состоит в приложении j ИЭ к некоторым точкам D1, D2, ... , Dj нового "интервала неопределенности" CjCj+1. Координаты точек D1, D2, ... , Dj относительно точки Cj, то есть нового начала координат, находятся в (n - 1)-м столбце "арифметического квадрата", то есть

CjD1 = 1, CjD2 = F(n - 1, 1), CjD3 = F(n - 1, 2), ..., CjDj = F(n - 1, j-1).(3)

Этот процесс заканчивается, когда будут "исчерпаны" либо все измерительные шаги алгоритма, либо все "индикаторные элементы".

В качестве примера рассмотрим "оптимальный" (3, 3, 1)-алгоритм (Рис. 2).

'Оптимальный' (3, 3, 1)-алгоритм
Рисунок 2. "Оптимальный" (3, 3, 1)-алгоритм.

"Оптимальный" (3, 3, 1)-алгоритм состоит из 3-х шагов и использует 3 ИЭ. Заметим, что число F(3, 3) = 20, которое находится на пересечении 3-го столбца и 3-й строки "арифметического квадрата", и равно длине исходного "интервала неопределенности" для данного алгоритма.

Первый шаг алгоритма на отрезке [0, 20] состоит в приложении 3 "индикаторных элементов" к точкам 1, 4, 10 (Рис. 2). На основании "показаний" ИЭ может возникнуть 4 ситуации после первого шага (1-а, 1-b, 1-c, 1-d).

Второй шаг.

1-a. Для этой ситуации процесс измерения заканчивается, так как все ИЭ находятся справа от точки X.

1-b. Для этой ситуации мы имеем только 1 ИЭ, который прикладывается к точке 2.

1-c. Для этой ситуации мы имеем 2 ИЭ, которые прикладываются к точкам 5 и 7.

1-d. Для этой ситуации мы имеем 3 ИЭ. В этом случае точка 10 есть новое начало координат и три ИЭ прикладываются к точкам 1, 3, 6 относительно нового начала координат. Просуммировав эти числа с числом 10, мы можем получить координаты точек приложения ИЭ на следующем шаге: 11, 13, 16.

После второго шага может возникнуть следующие ситуации: [1,2], [2,4], [4,5], [5,7], [7,10], [10,11], [11,13], [13,16], [16,20]. Заметим, что для ситуаций [1,2], [4,5], [10,11] процесс измерения заканчивается на втором шаге.

Третий шаг.

Для ситуаций [2,4], [5,7] и [11,13] третий шаг состоит в приложении 1-го IE к точкам 3, 6, 12 соответственно.

Для ситуаций [7,10] и [13,16] третий шаг состоит в приложении 2-х ИЭ к точкам 8, 9 или 14, 15 соответственно.

Для ситуации [16,20] третий шаг состоит в приложении 3-х ИЭ к точкам 17, 18, 19.

Какое значение может иметь "оптимальный" (n, k, 1)-алгоритм для математики? Важно подчеркнуть, что "оптимальный" (n, k, 1)-алгоритм есть широкое обобщение "алгоритма счета", который исторически лежит в основе элементарной теории чисел, созданной пифагорейцами. И возможно, мы можем использовать алгоритм измерения, основанной на "арифметическом квадрате", для дальнейшего развития теории чисел?