Составители:
Рубрика:
15
2. Граф-схема алгоритма микропрограммного автомата содержит
операторные и условные вершины. Операторные вершины “начало” и
“конец” обязательны. Сколько существует разных граф-схем алгорит-
мов, содержащих 6 вершин, если нас интересует только количествен-
ный состав, а не связи между вершинами?
1.9. Свойства чисел сочетаний
Приведем некоторые свойства чисел сочетаний, которые часто ис-
пользуются при преобразованиях формул комбинаторики.
1.
.
knk
nn
C
C
−
=
2.
1
11
.
kk k
nn n
C
CC
−
−−
=+
3.
012
... 2 .
nn
nnn n
C
CC C++−+=
Первое свойство совершенно очевидно. Второе легко доказывается,
если оба члена правой части представить по формуле (7). Третье свой-
ство можно доказать методом математической индукции. Для приме-
ра, при n = 2 имеем:
012 2
222
12142.
C
CC
++=+++=
Для n = 3 получаем:
0123 3
3333
13312.
C
CCC+ + + =+++=
Упражнения
1. Полный дешифратор имеет n входов и 2
n
выходов. Сколько выхо-
дов будет иметь дешифратор на 5 входов, если исключить все выходы,
соответствующие равновесным входным наборам из 2 и 4 единиц?
2. В некотором государстве не было двух жителей с одинаковым
набором зубов. Сколько могло быть жителей в таком государстве, если
во рту человека не может быть больше 32 зубов?
1.10. Комбинаторные задачи с ограничениями
Рассмотрим несколько типов задач, в которых на комбинации накла-
дываются определенные ограничения.
a) Задача о львах и тиграх. Имеется 5 львов и 4 тигра. Необходимо
их расставить в ряд, но при этом известно, что тигр не может идти
спокойно за тигром. Тогда расставляем львов с промежутками ( их бу-
дет 6) и в них вставляем тигров. Таким образом, если тигры и львы
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
