- •Поиск и включение для деревьев
- •Исключение из деревьев
- •Сбалансированные деревья
- •Включение элементов в сбалансированное дерева.
- •1 Случай
- •2 Случай
- •Исключение из балансированного дерева (авл)
- •Критерии и оценки алгоритма. Общие методы.
- •Асимптотические характеристики
- •Роль и методы в снижении трудоемкости решения задачи
- •Структура данных для описания решетки.
- •Частные характеристики качества алгоритмов
- •Увеличение быстродействия программ
- •Хеширование
- •Хеш таблицы.
- •Хеш функции
- •Двойное хеширование
- •Идеальное хеширование
- •Алгоритмы для работы с графами
- •Деревья поиска в ширину
- •Поиск в глубину
- •Стягивающие или остовные деревья
- •Минимальное остовное дерево
- •Эйлоровый цикл
- •Гомельтоновый цикл
- •Кротчайшие пути в ориентированных графах.
- •Комбинаторика
Комбинаторика
Перестановки. Генераторы перестановок. Перестановка – вариант расположения n объектов в линейной последовательности при этом состав объектов не меняется. Для 3-х величин a,b,c: abc, bca, cab,bac,acb,cba 3!=12*3=6 комбинаций
Переставлять описание объектов неразумно, теряется их дивергентность и время. Аперировать надо адресами. Адресами могут служить индекс массива записи. В программе ген. перестановки будут перемещаться курсоры (по мере), а предметная сущность остается за рамками схемы операции. Есть простой способ: считаем ? влияние кольцом и n перестановок получаем вращением кольца. Когда кольцо совершит полный оборот на одну позицию, часть оглавнения и снова ? кольцо. Получаем следующие n перестановок и т.д.
Function GenPer(var p;array of integer; n”integer=maxint):Boolean var (j,d):integer; begin if n=maxint then n=length(p); repeat dec(n); d=p[0]; for j:=1 to n do begin if n=1 then p[0]=p[length(p)-1] else p[j-1]=p[j]; p[n]:=d; end; result:=d<n / d<n поле генерации всех перестановок. until not Result or (n=1); end;
Сочетание (Sn)m – подмножество S, базового множества с попарного различными элементами n – мощность множества m – можность подмножества
Таким способом можно посчитать… For i:=1 to n-m+1 do For j:=i+4 to n-m+2 do For k:=j+1 to n-m+3 do For z:=y+1 to n do т.ц. задается сочетания I,j,k и тд
Недостаток: жесткая настройка значений n. Процедуру можно осуществить универсальным генератором со скрытой рекурентностью курср в массив p, подобно ?