Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

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



Важным обобщением позиционных систем с постоянным основанием являются смешанные системы, где основания меняются от разряда к разряду. Обозначим основания разрядов с номерами 0, 1, ..., k через р0, р1, ..., рk. Тогда запись вида Аp=ak...a2a1a0означает представление в смешанной системе счисления величины ak×р(k-1)× ... ×p1р0+ ...+a2p1р0+a1р0 + a0. Каждый коэффициент ai удовлетворяет неравенcтву: 0£ ai < pi . Наиболее известным примером смешанной системы счисления является общепринятая система измерения времени: «секунды – минуты – часы – сутки – недели – годы», основаниями в которой являются числа р0= 60, р1= 60, р2= 24, р3 = 7, р4=52.

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

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

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

Решение. 1526840 ½60

1526820 ½25447 ½60

20 25440 ½424 ½24

7408 ½17½7

1614½2

3.

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

А =a4a3a2a1a0=2/3/16/07/20 = 2недели 3 дня 16 часов 7 минут 20 секунд.

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

С точки зрения практического применения в комбинаторных задачах из смешанных систем счисления для представления целых чисел наиболее важна факториальная, где стоимость каждого разряда с номером i равна i!. При этом основание разряда равно pi = i + 1.Запись ak∙∙∙a2a1a0. в факториальной системе обозначает число Аф=ak×k! +...+a2 2!+ a11!+a0. Поскольку в математике принято соглашение 0! = 1, то в факториальной системе всегда задается a0=0. Правила перевода из десятичной системы счисления в факториальную и обратно аналогичны правилам для всех смешанных систем.

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

Решение.

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 = 62710.

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

Задачи

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

а) 105210, б) 0,96510, в) 31,5310, г) 159,6610.

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

а) 11001102, б) 0,00102, в) 10101,0112, г) 110,01012.

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

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

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

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

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

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

r (`an,`b n) + r (`b n,`g n) ³ r (`an,`g n),

где`an,`b n,`g n — любые векторы из `bn .

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

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

9. Перевести в десятичную систему числа F9B8316, CАF516.

10.Перевести в шестнадцатеричную систему числа 1101102 , 11011012 , 10110110101012 .

11.Перевести, используя сокращенные правила перевода, из восьмеричной системы в двоичную числа 57168, 1738 , 2658 .

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

а) 0,168, б) 0,213, в) 0,436, г) 0,57.

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

а) 120211013 – 2100122313 , 74358139 – 5250489 ;

б) 101111012 ´ 11012 , A4D316 ´ C5A16 ;

в) 5362 7 : 657 , 67516 8 : 478 .

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

а) 17210, б) 93410, в) 21578, г) 15356.

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

 

Глава 5. КОМБИНАТОРИКА

Комбинаторикойназывают математическую дисциплину, изучающую свойства множеств, которые можно построить из заданного базового набора дискретных объектов. Отдельные задачи количественного анализа таких множеств известны еще с древности. В современной комбинаторике рассматривается большое число общих и конкретных задач из области как естественных, так и гуманитарных наук. Необходимость в подобного рода подсчетах обычно возникает при определении вероятности, оценках, подсчетах, задачах планирования и т. д.

Основная задача комбинаторики. Характеристики комбинаторных задач

Обозначим через A начальное базовое множество дискретных объектов. В простейшем случае – это обычный набор объектов, заданный перечислением.

Способ порождения из заданного базового набора A новых множеств (комбинаторных множеств) называют комбинаторным правилом. Обозначим его через С. Полную совокупность комбинаторных множеств, которые могут быть образованы из A при помощи правила C, обозначим через C(А), а общее число комбинаторных множеств в ней обозначим через N(C(А)).

Поскольку комбинаторика, в первую очередь, рассматривает количественные свойства совокупностей комбинаторных множеств, то основную задачу комбинаторики (комбинаторного анализа) можно сформулировать следующим образом: по заданному базовому множеству объектов A и комбинаторному правилу C определить общее число элементов N(C(A)) в порождаемом комбинаторном множестве C(А).