Целые

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

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

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

$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$