Изменения

Перейти к: навигация, поиск

Получение номера по объекту

195 байт добавлено, 01:59, 6 декабря 2014
Нет описания правки
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font>
'''for''' j = <tex>A_{min}</tex> '''to''' предшествующий a[i] элемент '''do''' <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font>
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
numOfObject += d[i][j]
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условияпроверки элемента на равенство <tex>1</tex>:
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
*[[Получение следующего объекта|Получение следующего объекта]]
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]
== Литература Источники информации ==
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
29
правок

Навигация