 |
Алгоритмы поиска в строке
|
|
|
|
Алгоритмы генерации комбинаторных объектов.
1.Размещения с повторениями из n символов по k – это последовательность длины k, в которых n-возможных элементов будут повторяться. A kсверху n снизу =n!/(n-k)! Напечатать все последовательности длины k из чисел 1..n. Решение: Будем печатать их в лексикографическом порядке (последовательность а предшествует последовательности b, если для некоторого i их начальные отрезки длины i равны, а (i+1)-ый член последовательности а меньше). Первой будет последовательность <1,1,...,1>, последней - <n,n,...,n>. Будем хранить последнюю напечатанную последовательность в массиве x[1],..,x[k].
last[1],..,last[k] положим равным n. Для того, чтобы перейти к следующей последовательности надо: двигаясь с конца последовательности, найти самый правый член, меньший n, увеличить его на 1, а идущие за ним члены положить равными 1. Процедура print(x:massiv) - вывод последовательности.
Функция egual(x,last:massiv):boolean - сравнивает элементы массивов,если x<>last, то egual:=false иначе egual:=true.
for i:=1 to k do x[i]:=1;
print(x);
for i:=1 to k do last[i]:=n;
while not(equal(x,last)) do
begin
p:=k;
while not (x[p]<n) do p:=p-1;
x[p]:=x[p]+1;
for i:=p+1 to k do x[i]:=1;
print(x);
end;
Перестановки из n элементов - частный случай размещения элементов из Е по k, при k=n. Иными словами, перестановками называют размещения без повторений из n элементов, в которые входят все элементы. Можно также сказать, что перестановками из n элементов называют всевозможные n-расстановки, каждая из которых содержит все эти элементы по одному разу, и которые отличаются друг от друга лишь порядком элементов. Число перестановок вычисляется по формуле: Pn=n! 1. Просматриваем а1,..., аn с конца до тех пор, пока не попадется ai<ai+1. Если таковых нет, то генерация закончена.
|
|
|
2. Рассматриваем ai+1, ai+2,..., an. Найдем первый с конца am больший ai и поменяем их местами.
3. ai+1, ai+2,..., an переставим в порядке возрастания (для этого достаточно её переписать с конца).
4. Печатаем найденную перестановку.
5. Возвращаемся к пункту 1.
Сочетанием элементов из Е={a1,..., an} по k называется упорядоченное подмножество из k элементов, принадлежащих Е и отличающиеся друг то друга составом, но не порядком элементов. Число сочетаний вычисляется по формуле: Ckn=n!/(n-k)!k! Алгоритм генерации сочетаний Ckn.
1. Для i:=1 до k ci:=i; печатаем ci, для i=1..k.
2. С конца находим такое i, что ci<>n-k+i. Если такого i нет, то генерация сочетаний закончена.
3. ci:=ci+1; для m=i+1, i+2,..., k выполним cm:=cm-1+1; выводим ci для i=1,..., k.
4. Возрващаемся к пункту 2.
3) Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Этапы:
1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.
|
|
|
Ярким примером является вычисление последовательности Фибоначчи,Ф3=Ф2+Ф1
Динамическое программирование обычно придерживается двух подходов к решению задач:
· нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
· восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.
Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
Алгоритмы поиска в строке
Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.) Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.
Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.
Алгоритм прямого поиска Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,
Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм поиска образца (подстроки) в строке. Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году. Поставим следующую задачу: имеется образец S и строка T, и нужно определить индекс, начиная с которого строка S содержится в строке T. Если S не содержится в T — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
|
|
|
ЛИТЕРНЫЙ ТИП У ЛИТЕРЫ
ЛИТЕРЫ
ОТ ы ЛИТЕРЫ И ДО СОВПАДЕНИЯ Литеры
После частичного совпадения начальной части образа W с соответствующими символами строки Т мы фактически знаем пройденную часть строки и может «вычислить» некоторые сведения (на основе самого образа W), с помощью которых потом быстро продвинемся по тексту.
Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.
5) Алгоритмы на графах. Поиск в глубину. Поиск в ширину.
Поиск в глубину (Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройдённой вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Метод систематического прохождения (посещения) вершин графа, когда за счет продвижений от текущей вершины по ребру вперед (к еще непросмотренной вершине) всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины невозможно, осуществляется движение по всем вершинам графа, достижимым из заданной вершины s, с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов в вершине s - начале просмотра; после его завершения все ребра связного графа оказываются разбитыми на два класса: древесные, по которым осуществлялись переходы из посещенных вершин в непосещенные, и ребра касания, замыкающие циклы.
|
|
|
