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



             

Целые


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

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

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

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

(d_{0},d_{1},d_{2},d_{3},\ldots,d_{k}),

(2.1)

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

d_{i}
- целое, удовлетворяющее условию
0 \leqslant d_{i} < r
и
d_{k} \ne 0
. Нуль представляется последовательностью
(0)
.
r
называется основанием системы
(r > 1)
. Целое, соответствующее последовательности (2.1), имеет вид

 N = d_{0} + d_{1}r + d_{2} r^2 + d_{3} r^3 + \ldots + d_{k} r^k,

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

 N = (d_{k} d_{k - 1} \ldots d_{1d} d_{0} )_{r}.

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

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

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

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

 N = (d_{k} d_{k - 1} \ldots d_{0})_{r} = (e_{l} e_{l - 1} \ldots e_{0} )_{r}.

Если

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

 \sum\limits_{i = 0}^l {(r - 1)r^i = r^{l + 1} - 1} < r^{l + 1} < r^k

и поскольку

d_{k} \ne 0
, мы заключаем, что

 (d_k d_{k - 1} \ldots d_0 )_r > (e_l e_{l - 1} \ldots e_0 )_r,

(2.2)

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

k = l
. Аналогично, если
d_k > e_k
, мы имели бы снова неравенство (2.2) и отсюда с необходимостью
d_k = e_k
.


Содержание  Назад  Вперед