Смешенная система счисления

Смешенная система счисления

Принцип кодового замка

[pic 1]

Для описания состояний кодового замка используется смешенная система счисления. Например, шестое состояние замка можно обозначить как 021

Смешенная система счисления задаётся последовательностью оснований

…, p3,  p2,  p1

которые отвечают за цифры в разрядах (справа налево):

• в 0-ом разряде пишутся цифры 0… (p1 -1)
• в 1-ом разряде пишутся цифры 0… (p2 -1)
• и т.п.

Число abcd, записанное в смешенном виде, находится по формуле

abcd = p1⬩ p2⬩ p3⬩ a + p1⬩ p2 ⬩ b + p1 ⬩ c + d

Чтобы получить запись некоторого числа A в смешенной системе S, надо делить число A по порядку на все основания и выписывать остатки в обратном порядке. Например, если основаниями системы S являются 4, 3, 2, то для A = 21

В итоге получаем A = 311S

Кодировка перестановок

Рассматривается перестановка букв ABCD

[pic 2]

Примеры кодов перестановок из 4-х букв

[pic 3]

Перебор перестановок можно осуществлять и без числовой кодировки вариантов. Рассмотрим следующую простую идею.

Расположим N переставляемых элементов в ряд.

A  B  C

Будем последовательно выдвигать вперёд элементы ряда путём взаимного обмена с первым и всякий раз применять к оставшимся элементам (начиная со второго) любой метод перебора перестановок.

A  ( B  C )                B  ( A  C )                C  ( A  B )

       перебираем                 перебираем                       перебираем

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

Ниже приводится схема организации рекурсивной процедуры Rpl. Массив a наполняется переставляемыми элементами. Переменная c должна иметь тот же тип. Переменная i определяет номер выбираемого элемента. Главная процедура Rpl вызывается при i = 1, затем она сама изменяет значение i.