Изменения

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

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

238 байт добавлено, 03:45, 29 октября 2011
Нет описания правки
== Общий алгоритм получения комбинаторного объекта по номеру в лексикографическом порядке ==
: Получим элементы объекта по порядку, сначала определим какой элемент будет стоять на 1-м месте, 2-м и т.д.Пусть мы нашли первые i элементов нашего объекта. Для всех вариантов i+1 элемента посчитаем диапазон номеров объектвов объектов с данным префиксом. Если искомый номер входит в один из диапазонов, то очевидно мы нашли элемент, который должени стоять на (i+1)-ом месте.
''//В начале каждого шага numOfObject - номер комбинаторного объекта среди объектов с заданным префиксом. ''
'''for''' i = 1 '''to''' n '''do''' ''//n - количество элементов в комбинаторном объекте''
перейти к выбору следующего элемента
: Несложно понять, что корректность алгоритма следует из его построения.Сложность алгоритма <tex>O(n^(2)f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов сданным префиксом.
Анонимный участник

Навигация