|
|
|
|
|
| Сборник задач по программированию. Старая версия
|
| xsl, сервер, клиент, обзоры, xslt, xslt, сервлет, pascal, интерфейс, язык программирования |
Паскаль. P.48. Алгоритмы. Нумерации
Одной из важнейших задач в программировании является поиск взаимно-однозначных всюду-определенных нумераций для последовательностей различных объектов. Такие нумерации называются геделевыми. Простейшим случаем такой нумерации является задача нумерации последовательностей чисел (смотри пункт.1.1.). В качестве последовательностей нумеруемых объектов также могут выступать не просто числа, а различные множества, такие как последовательности пар чисел, последовательности последовательностей чисел (слова в некотором алфавите) и так далее. Приведем некоторые алгоритмы нумерации пар чисел и последовательностей чисел. Канторовская нумерация пар чисел. Такая нумерация визуально представляется в виде матрицы. По вертикали и горизонтали откладываются числа из пар чисел, а содержимое матрицы заполняют номера пар чисел, на пересечении которых находится номер.
00 01 02 03 04 05 ...
00! 00 01 03 06 10 15
01! 02 04 07 11 16
02! 05 08 12 17
03! 09 13 18
04! 14 19
05! 20
. !
. !
Нумерация последовательностей чисел. Основывается на канторовской нумерации пар чисел. Номер последовательности чисел строится следующим образом. Берется последовательность чисел. Слева к ней приписывается число, равное числу элементов в этой последовательности. Затем два последние числа последовательности заменяются на канторовский номер этой пары чисел. Процесс замены последней пары чисел на их канторовский номер продолжается до тех пор, пока не останется одно число. Это и есть геделев номер последовательности. Алгоритм построения последовательности по его номеру является полностью обратным вышеописанному алгоритму. Берется номер последовательности. Для этого номера находится канторовская пара чисел. Первое число показывает число элементов в результирующей последовательности чисел. По второму числу снова строится пара чисел. Первое число из пары чисел является очередным элементом последовательности, а из второго числа снова строится канторовская пара чисел. И так далее, пока не будет достигнуто требуемое число элементов в последовательности.
Заметим, чтобы описанная здесь нумераций последовательностей чисел была всюду-определенной для всех номеров, то есть, чтобы для любого номера существовала последовательность чисел, нужно в приведенном алгоритме использовать две разновидности канторовской нумерации пар чисел. Первая разновидность приведена выше. Вторая разновидность используется в прямом алгоритме (построение номера для последовательности) на самом последнем этапе, когда остаются 2 числа (первое из них исходная длина последовательности) и для этих двух чисел строится номер. В обратном алгоритме эта разновидность канторовской нумерации используется на самом первом шаге, когда определяется длина результирующей последовательности чисел.
Вторая разновидность канторовской нумерации пар чисел
....00 01 02 03 04 05 ...
01! 00 01 03 06 10
02! 02 04 07 11
03! 05 08 12
04! 09 13
05! 14
. !
. !
Делается это для того, что исключить последовательности с нулевой длины, которых было бы бесконечное число (которые были бы пустыми и одинаковые для бесконечного числа номеров, а это недопустимо).
Примеры номеров последовательностей чисел
Номер Последовательности чисел
0 0
1 1
2 0, 0
3 2
4 0, 1
5 0, 0, 0
6 3
7 1, 0
8 0, 0, 1
9 0, 0, 0, 0
10 4
|
