Целые являются основными объектами в вычислительной комбинаторике. В различных вычислительных теоретико-числовых исследованиях изучаются сами целые числа, но мы будем использовать их главным образом при подсчете и индексировании. В последнее время установлено, что полезны различные представления. В этой лекции обсудим общий класс позиционных представлений.
Мы будем рассматривать только неотрицательные целые. Кроме того, к любому представлению неотрицательных целых легко присоединить одиночный знаковый двоичный разряд.
Позиционные системы для представления целых чисел очень широко известны, поскольку они встречаются во многих разделах математики, начиная с "новой математики" и кончая углубленным курсом теории чисел. В системе счисления с основанием
каждое положительное целое число имеет единственное представление в виде конечной последовательности
(2.1)
в которой каждое
- целое, удовлетворяющее условию
и
. Нуль представляется последовательностью
.
называется основанием системы
. Целое, соответствующее последовательности (2.1), имеет вид
что принято выражать следующим образом:
На протяжении истории использовались различные значения
. Например, древние вавилоняне использовали
, а индейцы племени Майя —
. Сегодня наиболее широко используется
- десятичная система, которую мы унаследовали от арабов, и
- двоичная система, которая лежит в основе современных вычислительных устройств. В действительности она применяется лишь на самом низком уровне аппаратного оборудования; в сложных вычислительных устройствах и базисных языках удобнее использовать
или
.
Единственность этого представления можно доказать методом от противного. Числа
и
, очевидно, имеют единственное представление. Предположим, что представление не единственно, и пусть
будет наименьшим целым числом, имеющим два различных представления:
Если
, то без потери общности предположим, что
. Тогда, поскольку
и поскольку
, мы заключаем, что
(2.2)
что невозможно. Таким образом, мы должны иметь
. Аналогично, если
, мы имели бы снова неравенство (2.2) и отсюда с необходимостью
.
Следовательно, число
имеет два различных представления, что противоречит предположению, что
- наименьшее из таких чисел.
Для доказательства того, что каждое положительное целое имеет представление по основанию
, достаточно задать алгоритм, конструирующий (с необходимостью единственное) представление данного числа
.
Алгоритм 1. Преобразование числа
в его представление
в системе счисления с основанием
.
Он строит последовательность
путем повторения деления на
и записи остатков. Пусть на первом шаге при делении
на
остаток будет
. Частное, полученное в результате первого шага, делим на
, вновь полученное частное делим на
и так далее. Полученная в результате такого процесса последовательность остатков и будет требуемым представлением
по основанию
.
Важным обобщением систем счисления с основанием
являются смешанные системы счисления, в которых задается не единственное основание
, а последовательность оснований
и последовательность (2.2) соответствует целому
где теперь каждое
удовлетворяет неравенству
и
, если
- тот факт, что каждая такая последовательность соответствует единственному числу и каждое положительное целое число имеет единственное представление, следует из простого обобщения результатов для обычных систем счисления, которые являются частным случаем смешанных систем при
.
Смешанные системы счисления могут вначале показаться странными, но в действительности в повседневной жизни они встречаются почти так же часто, как и десятичные.
Пример. Рассмотрим нашу систему измерения времени: секунды, минуты, часы, дни недели и годы. Это - в точности смешанная система с
.
Представление целого
в смешанной системе счисления
осуществляется с помощью алгоритма 2, который является простым обобщением алгоритма 1. Вместо того, чтобы для получения
