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

Еще раз рассмотрим "двоичный" алгоритм измерения в рамках модели "Индикаторных элементов". В общем случае "двоичный" алгоритм состоит из n шагов и использует только 1 "индикаторный элемент", движение которого на отрезке AB подчиняется условиям S=0. Мы будем называть такой алгоритм (n, 1, S)-алгоритмом.

Мы можем обобщить "двоичный" алгоритм, если увеличим число "индикаторных элементов" от 1 до k, где k принимает значения из множества {1, 2, 3, ...}. Тогда мы можем рассматривать (n, k, 0)-алгоритмы, которые являются обобщением (n, 1, 0)-алгоритма, то есть "двоичного" алгоритма измерения.

В этом случае первый шаг (n, k, 0)-алгоритма на отрезке AB состоит в приложении k "индикаторных элементов" к точкам отрезка AB, как показано на Рис.1.

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

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

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

Тогда функция "эффективности" "оптимального" (n, k, 0)-алгоритма имеет следующий вид:

F(n, k) = (k+1)n.(1)

Для случая k = 1 эта формула сводится к выражению для функции "эффективности" "двоичного" алгоритма.

Заметим, что подобно "двоичному" алгоритму, который "порождает" двоичную систему счисления, "оптимальный" (n, k, 0)-алгоритм "порождает" позиционную систему счисления с основанием R = k + 1, то есть

A = an-1 Rn-1 + an-2 Rn-2 + ... + ai Ri + ... + a1 R1 + a0 R0,(2)

где ai Î {0, 1, 2, ..., k} цифра i-го разряда.

В частности, для случая k=9 формула (2) сводится к классической десятичной системе счисления:

A = an-1 10n-1 + an-2 10n-2 + ... + ai 10i + ... + a1 101 + a0 100,

которая изучается в средней школе.

Для случая k = 59 формула (2) сводится к Вавилонской 60-ричной системе счисления. Из этого рассуждения вытекает, что "оптимальные" (n, k, 0)-алгоритмы "порождают" все известные позиционные системы счисления.

Хотя ничего особенно нового мы еще не получили, но нам приятно, что классические позиционные системы счисления порождаются "оптимальными" алгоритмами измерения и это дает нам право применить к ним слово "оптимальный", то есть все известные позиционные системы счисления, в частности, двоичная и десятичная, являются "оптимальными"!