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

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

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

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

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

Решение. 1526840 60

1526820 25447 60

20 25440 424 24

7 408 177

16 142

3.

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

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

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

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

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

Решение. 

627 1

627 6272

0 6263133

1 3121044

1 104265

0 25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-мерных булевых векторов расстояние Хэмминга удовлетворяет неравенству треугольника:

 (ⁿ, ⁿ) +  ( ⁿ, ⁿ)   (ⁿ, ⁿ),

гдеⁿ, ⁿ, ⁿ — любые векторы из bⁿ .

7. Пусть Вⁿ — множество всех n – мерных двоичных векторов bⁿ, которые появляются случайно c одинаковой вероятностью. Доказать, что средневероятный вес _св(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.