Изменения

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

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

4 байта убрано, 06:19, 26 ноября 2011
Описанте алгоритма
== Описанте алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов плюс 1(нумерацию ведём с 10).Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса.Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины i совпадает , а i+1 элемент лексикографически меньше i+1-го в данном объекте(i=0..n-1).
Следующий алгоритм вычисляет эту сумму
numOfObject=1 0 ''// numOfObject {{---}} искомый номер комбинаторного объекта
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''
'''for''' j = 1 '''to''' a[i]-1 '''do''' ''// перебираем элементы которые в лексикографическом порядке меньше рассматриваемого''
'''if''' элемент j можно поставить на i-e место
'''then''' numOfObject+=(коллличество комбинаторных объектов с префиксом от 1 до i-1 равным данному и с i-м элементом равным j)
т.е. он правильно находит номер данного объекта.
394
правки

Навигация