Комбинаторные алгоритмы для программистов

         

Целые


Целые являются основными объектами в вычислительной комбинаторике. В различных вычислительных теоретико-числовых исследованиях изучаются сами целые числа, но мы будем использовать их главным образом при подсчете и индексировании. В последнее время установлено, что полезны различные представления. В этой лекции обсудим общий класс позиционных представлений.

Мы будем рассматривать только неотрицательные целые. Кроме того, к любому представлению неотрицательных целых легко присоединить одиночный знаковый двоичный разряд.

Позиционные системы для представления целых чисел очень широко известны, поскольку они встречаются во многих разделах математики, начиная с "новой математики" и кончая углубленным курсом теории чисел. В системе счисления с основанием

каждое положительное целое число имеет единственное представление в виде конечной последовательности

(2.1)

в которой каждое

- целое, удовлетворяющее условию
и
. Нуль представляется последовательностью
.
называется основанием системы
. Целое, соответствующее последовательности (2.1), имеет вид

что принято выражать следующим образом:

На протяжении истории использовались различные значения

. Например, древние вавилоняне использовали
, а индейцы племени Майя —
. Сегодня наиболее широко используется
- десятичная система, которую мы унаследовали от арабов, и
- двоичная система, которая лежит в основе современных вычислительных устройств. В действительности она применяется лишь на самом низком уровне аппаратного оборудования; в сложных вычислительных устройствах и базисных языках удобнее использовать
или
.

Единственность этого представления можно доказать методом от противного. Числа

и
, очевидно, имеют единственное представление. Предположим, что представление не единственно, и пусть
будет наименьшим целым числом, имеющим два различных представления:

Если

, то без потери общности предположим, что
. Тогда, поскольку

и поскольку

, мы заключаем, что

(2.2)

что невозможно. Таким образом, мы должны иметь

. Аналогично, если
, мы имели бы снова неравенство (2.2) и отсюда с необходимостью
.
Следовательно, число



имеет два различных представления, что противоречит предположению, что
- наименьшее из таких чисел.

Для доказательства того, что каждое положительное целое имеет представление по основанию
, достаточно задать алгоритм, конструирующий (с необходимостью единственное) представление данного числа
.

Алгоритм 1. Преобразование числа
в его представление
в системе счисления с основанием
.


Он строит последовательность
путем повторения деления на
и записи остатков. Пусть на первом шаге при делении
на
остаток будет
. Частное, полученное в результате первого шага, делим на
, вновь полученное частное делим на
и так далее. Полученная в результате такого процесса последовательность остатков и будет требуемым представлением
по основанию
.

Важным обобщением систем счисления с основанием
являются смешанные системы счисления, в которых задается не единственное основание
, а последовательность оснований
и последовательность (2.2) соответствует целому


где теперь каждое
удовлетворяет неравенству
и
, если
- тот факт, что каждая такая последовательность соответствует единственному числу и каждое положительное целое число имеет единственное представление, следует из простого обобщения результатов для обычных систем счисления, которые являются частным случаем смешанных систем при
.

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

Пример. Рассмотрим нашу систему измерения времени: секунды, минуты, часы, дни недели и годы. Это - в точности смешанная система с
.

Представление целого
в смешанной системе счисления
осуществляется с помощью алгоритма 2, который является простым обобщением алгоритма 1. Вместо того, чтобы для получения
в качестве делителя всегда использовалась
, в алгоритме 2 используется
.

Алгоритм 2. Преобразование числа
в его представление
в смешанной системе счисления



Содержание раздела