A246. C-соответствие

C-соответствие – взаимно однозначное соответствие между множеством натуральных чисел N и множеством вещественных чисел R, устанавливаемое применением Алгоритма C.

Алгоритм C является усовершенствованием и обобщением Алгоритма B (см. A245). Он описан в МОИ № 29, стр.39–41.

Сейчас мы покажем, как установить взаимно однозначное соответствие между N и R путем линейной генерации множества R , в ходе которой каждому числу из R присваивается однозначный порядковый номер.

Для этого нам потребуется обобщить и потом модифицировать Алгоритм B, который генерировал Промежуток [0, 1] и который мы принимаем здесь хорошо известным и понятным. Сначала представим логическую структуру Алгоритма B в виде, показанном на Рис.1.

Рис. 1. Логическая структура Алгоритма B

Здесь Алгоритм B состоит из двух блоков (TOTUM и FRACTIO) и оперирует структурой данных под названием ACERVUS. Блок TOTUM в Алгоритме B отрабатывает один-единственный раз, поставляя в структуру ACERVUS (в Ацервус) стартовую строку «0,». Блок FRACTIO отрабатывает бесконечное количество раз. Каждый раз он берет всё то, что уже есть в Ацервусе, делает из этого материала копию, прибавляя каждому элементу копии в конце «1», а к исходным строкам присоединяет в конце «0»; новые строки помещает в конце Ацервуса. Таким образом блок FRACTIO обеспечивает присоединение ко всем элементам Ацервуса все возможные комбинации нулей и единиц в дробной части.

Теперь модифицируем Алгоритм B, и этот модифицированный алгоритм назовем Алгоритмом C. Его принципиальная схема показана на Рис.2.

Рис. 2. Принципиальная схема Алгоритма C

В Алгоритме C, в отличие от Алгоритма B, блок TOTUM отрабатывает не один раз, а тоже бесконечное количество раз. В первый раз он «бросает» в Ацервус стартовые строки «+0» и «–0». Второй раз он отрабатывает после первого цикла блока FRACTIO и бросает в Ацервус строки «+1» и «–1»; третий раз он после второго цикла блока FRACTIO помещает в Ацервус «+2» и «–2» и т.д. Таким образом начинается генерация всё новых и новых интервалов множества R алгоритмом C.

Легко видеть, что чем дальше интервал отстоит от 0, тем позднее начинается его генерация. Тем не менее, когда-нибудь она всегда начинается, и продолжается сколь угодно далеко в дробной части. Каждое число из R получает свой фиксированный, раз и навсегда данный номер (который всегда можно вычислить, если не пожалеть усилий). Любой наперед заданный знак любого числа из R , как в его целой, так и в дробной части, будет рано или поздно сгенерирован алгоритмом C, если допустить, что тот может работать бесконечно.

Покажем пошагово начальную часть генерации (и тем самым нумерации) множества R . Продукт перед первым циклом блока FRACTIO:

Номер продукта	Продукт Алгоритма C
0 1	+0, –0,

После первой отработки блока FRACTIO:

Номер продукта	Продукт Алгоритма C
0 1 2 3	+0,0 –0,0 +0,1 –0,1

Перед второй отработкой блока FRACTIO:

Номер продукта	Продукт Алгоритма C
0 1 2 3 4 5	+0,0 –0,0 +0,1 –0,1 +1, –1,

После второй отработки блока FRACTIO:

Номер продукта	Продукт Алгоритма C
0 1 2 3 4 5 6 7 8 9 10 11	+0,00 –0,00 +0,10 –0,10 +1,0 –1,0 +0,01 –0,01 +0,11 –0,11 +1,1 –1,1

Перед третьей отработкой блока FRACTIO:

Номер продукта	Продукт Алгоритма C
0 1 2 3 4 5 6 7 8 9 10 11 12 13	+0,00 –0,00 +0,10 –0,10 +1,0 –1,0 +0,01 –0,01 +0,11 –0,11 +1,1 –1,1 +10, –10,

После третьей отработки блока FRACTIO:

Номер продукта	Продукт Алгоритма C
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27	+0,000 –0,000 +0,100 –0,100 +1,00 –1,00 +0,010 –0,010 +0,110 –0,110 +1,10 –1,10 +10,0 –10,0 +0,001 –0,001 +0,101 –0,101 +1,01 –1,01 +0,011 –0,011 +0,111 –0,111 +1,11 –1,11 +10,1 –10,1

Мы начали нумерацию с 0, чтобы нулевую строку можно было бы отбросить, посчитав +0,0000... и –0,0000... за одно и то же число; тогда нумерация будет начинаться с единицы. В приведенной выше таблице генерация отрезков [0, 1] и [–1, 0] доведена до трех двоичных знаков после запятой; генерация отрезков [1, 2] и [–2, –1] доведена до двух знаков; генерация отрезков [2, 3] и [–3, –2] доведена до одного знака за запятой. На следующем шаге будет включена генерация отрезков [3, 4] и [–4, –3]. С каждым циклом алгоритма будет добавляться один знак за запятой в существующих уже строках, и начинаться генерация нового положительного и нового отрицательного интервала.

Разумеется, алгоритм C может работать не только с двоичной, но и с десятичной или любой другой системой счисления.

Итак, мы установили взаимно однозначное соответствие между множеством натуральных чисел и «полным континуумом»: множеством всех вещественных чисел от –∞ до +∞.