Структуры данных и модели вычислений

         

Избыточное представление чисел


Рассматриваемое в этой лекции представление приоритетной очереди основано на использовании так называемых избыточных счетчиков, позволяющих за время O(1) инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь один из способов реализации толстых куч. На самом деле, для их реализации подойдет произвольный d-арный счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.

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

где , . Будем называть цифрой, стоящей в -м разряде. В примерах запятые между цифрами опускаем.

Заметим, что избыточное представление отличается от обычного -арного представления использованием "лишней" цифры , что приводит к неоднозначности представления чисел. Например, при число может быть представлено как и как .

В примерах, в которых , "цифру" 10 будем обозначать символом .

Назовем -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными , найдется цифра, отличная от .

Пример.

Пусть , а число представляется в обычной десятичной системе последовательностью , тогда представления и не являются регулярными -арными избыточными представлениями числа , а представления и регулярны.

Пусть — номер разряда, отличного от и ближайшего слева от -го разряда в регулярном -арном избыточном представлении .

Определим следующим образом: , если ,

и ; — произвольное число , если

и ; — не определено, если .

Величину будем называть прямым указателем. Пусть — -арное регулярное представление некоторого числа.

Фиксацией цифры b, стоящей в i-м разряде представления d,

назовем операцию, заключающуюся в обнулении цифры

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

Инкрементирование i-й цифры избыточного представления d можно выполнить с помощью операторов

Очевидно, что инкрементирование -го разряда регулярного -арного избыточного представления числа

производит представление числа .

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

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



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