Смешанные позиционные системы счисления. Факториальная система

Важным обобщением позиционных систем с постоянным основанием являются смешанные системы, где основания меняются от разряда к разряду. Обозначим основания разрядов с номерами 0, 1, ..., k через р₀, р₁, ..., р_k. Тогда запись вида А_p=a_k...a₂a₁a₀означает представление в смешанной системе счисления величины a_k×р_(k-1)× ... ×p₁р₀+ ...+a₂p₁р₀+a₁р₀ + a₀. Каждый коэффициент a_i удовлетворяет неравенcтву: 0£ a_i < p_i . Наиболее известным примером смешанной системы счисления является общепринятая система измерения времени: «секунды – минуты – часы – сутки – недели – годы», основаниями в которой являются числа р₀= 60, р₁= 60, р₂= 24, р₃ = 7, р₄=52.

4.6.1. Перевод целых чисел из десятичной системы в смешанную с основаниями р₀, р₁, ... , р_k

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

Пример 1. Выразим временной период А = 1 526 840 секунд в общепринятой системе измерения времени «сек — мин — ч — сут. — нед. —
— годы», где р₀ = 60, р₁ = 60, р₂ = 24, р₃= 7, р₄=52.

Решение. 1526840 ½60

1526820 ½25447 ½60

20 25440 ½424 ½24

7408 ½17½7

1614½2

3.

Рассматривая в обратном порядке остатки от деления на каждом шаге и самое последнее частное, получим искомую запись числа:

А =a₄a₃a₂a₁a₀=2/3/16/07/20 = 2недели 3 дня 16 часов 7 минут 20 секунд.

Обратный перевод из смешанной системы в десятичную осуществляют посредством умножения каждого символа a_k на сомножитель, представляющий собой произведение р_kр_(k–1)∙∙∙p₁р₀,
с последующим суммированием полученных произведений.

С точки зрения практического применения в комбинаторных задачах из смешанных систем счисления для представления целых чисел наиболее важна факториальная, где стоимость каждого разряда с номером i равна i!. При этом основание разряда равно p_i = i + 1.Запись a_k∙∙∙a₂a₁a₀. в факториальной системе обозначает число А_ф=a_k×k! +...+a₂ 2!+ a₁1!+a₀. Поскольку в математике принято соглашение 0! = 1, то в факториальной системе всегда задается a₀=0. Правила перевода из десятичной системы счисления в факториальную и обратно аналогичны правилам для всех смешанных систем.

Пример 2. Перевести в факториальную систему счисления
число А = 627₁₀.

Решение.

627 ½1

627 ½627½2

0 626½313½3

1312½104½4

1104½26½5

025½5

1

Ответ: Искомое представление числа в факториальной системе имеет вид: А _ф= 510110.

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

А = 5×5! + 1×4! + 0 × 3! + 1×2! + 1× 1! =5×120 + 1×24 + 1×2 + 1×1 = = 600 + 24 + 2 + 1 = 627₁₀.

Факториальная запись чисел удобна для подсчета вариантов множеств, состоящих из взаимно отличных друг от друга объектов.

Задачи

1. Перевести в двоичную систему числа:

а) 1052₁₀, б) 0,965₁₀, в) 31,53₁₀, г) 159,66₁₀.

2. Перевести в десятичную систему числа:

а) 1100110₂, б) 0,0010₂, в) 10101,011₂, г) 110,0101₂.

3. Доказать, что в n – мерном кубе Вⁿ :

а) количество вершин в сфере радиусом 1 равно n, а количество вершин в шаре радиусом 1 равно n +1;

б) количество вершин в сфере радиусом 2 равно n (n – 1)/2,
а количество вершин в шаре радиусом 2 равно n(n+1)/2+1.

4. Доказать (например, с использованием метода математической индукции), что общее количество вершин в бинарном дереве Тⁿ равно 2ⁿ⁺¹–1.

5. Доказать методом математической индукции, что в n-мерном кубе Вⁿ число ребер равно n∙2^n–1.

6. Доказать, что на множестве всех n-мерных булевых векторов расстояние Хэмминга удовлетворяет неравенству треугольника:

r (`a<sup>n</sup>,`b ⁿ) + r (`b <sup>n</sup>,`g ⁿ) ³ r (`a<sup>n</sup>,`g ⁿ),

где`a<sup>n</sup>,`b ⁿ,`g <sup>n</sup> — любые векторы из `bⁿ .

7. Пусть Вⁿ — множество всех n – мерных двоичных векторов
bⁿ, которые появляются случайно c одинаковой вероятностью. Доказать, что средневероятный вес w_св(b ⁿ) булевых векторов`bⁿ равен n/2.

8. Перевести в двоичную систему и систему с основанием 4 числа B23DA₁₆, АD7С₁₆.

9. Перевести в десятичную систему числа F9B83₁₆, CАF5₁₆.

10.Перевести в шестнадцатеричную систему числа 110110₂ , 1101101₂ , 1011011010101₂ .

11.Перевести, используя сокращенные правила перевода, из восьмеричной системы в двоичную числа 5716₈, 173₈ , 265₈ .

12. Перевести следующие дроби в десятичную систему:

а) 0,16₈, б) 0,21₃, в) 0,43₆, г) 0,5₇.

13. Выполнить следующие арифметические действия:

а) 12021101₃ – 210012231₃ , 7435813₉ – 525048₉ ;

б) 10111101₂ ´ 1101₂ , A4D3₁₆ ´ C5A₁₆ ;

в) 5362 ₇ : 65₇ , 67516 ₈ : 47₈ .

14. Перевести в факториальную систему числа:

а) 172₁₀, б) 934₁₀, в) 2157₈, г) 1535₆.

15. Перевести в десятичную систему из факториальной числа:
а) 423010, б) 231200, в) 142110, г) 502110.