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