Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Высокоуровневые методы информатики и программирования (ВМИП) - файл 1.doc


Лекции - Высокоуровневые методы информатики и программирования (ВМИП)
скачать (2205.5 kb.)

Доступные файлы (1):

1.doc2206kb.04.12.2011 09:12скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10   11
Реклама MarketGid:
Загрузка...
^

Поиск подстроки в строке

Прямой поиск



Постановка задачи. Заданы две строки - s и x. Длина первой строки - n, длина второй - m, причем 0 ≤ m ≤ n. Требуется определить, является ли строка x подстройкой строки s, при этом требуется обнаружить первое вхождение x в s.

Самым простым методом поиска является метод прямого поиска. Рассмотрим его на примере. Пусть s = ‘воротник’, а x = ‘рот’. Длина первой строки n = 8, длина второй - m = 3. В данном случае строка x короче s, следовательно, нужно найти такое решение индекса i, что для любого значения индекса к - 1 ≤ k ≤ 3 будет выполняться равенство s [ i + k ] = x [ k ].

Начальное значение i равно 0.
1 - й шаг

i = 0, k = 1 - сравниваем s [ 1 ] и x [ 1 ]: ‘в’ ≠ ‘p’, значит, с первой позиции вхождения нет, нужно увеличить на 1 значение i.
2-й шаг

i = 1, k = 1 - сравниваем s [ 2 ] и x [ 1 ]: ‘o’ ≠ ‘p’, снова надо перейти к следующему i.
3 -й шаг

i = 2, k = 1 - сравниваем s [ 3 ] и x [ 1 ]: ‘p’ = ‘p’, следовательно, возможно совпадение, нужно увеличить k.
4-й шаг

i = 2, k = 2 - s [ 4 ] = x [ 2 ]: ‘o’ = ‘o’ - снова надо увеличить k.
5-й шаг

i = 2, k = 3 - s [ 5 ] = x [ 3 ]: ‘т’ = ‘т’ - полное совпадение! Далее поиск можно не продолжать, так как требовалось обнаружить лишь первое вхождение x в s.

Таким образом, прямой поиск подстроки в строке сводится к последовательным сравнениям отдельных символов. Поиск продолжается до тех пор, пока не обнаружится вхождение или пока не будет пройдена вся строка s. При этом можно закончить просмотр, когда i будет равно n-m, так как при следующих значениях i длина любого фрагмента строки s с позиции i меньше m.

Ниже приведена программа, реализующая метод прямого поиска подстроки.
Program n10;var s,x: string;

i,j,n,m: integer;

f: boolean;

begin

writeln('Введите строку s: ');

readln(s);

writeln('Введите строку x: ');

readln(x);

n:=length(s); m:=length(x);{ Определение длин строк }

i:=0;

f:=False; { Признак того, что подстрока найдена}

repeat

j:=1;

while (j<=m) and (s[i+j] =x[j]) do inc(j);

if j=m+1 then f:=true else inc(i);

until f or (i>n-m);

if f then writeln(x,' является подстрокой ',s,' с позиции - ',i+1)

Else writeln(x, ' не является подстрокой ',s);

readln;

end.
Этот алгоритм требует достаточно больших временных затрат, поскольку, когда n значительно больше m, количество выполняемых сравнений –

( n-m )*m ≈ n*m.
^

Алгоритм Р. Бойера и Дж. Мура



Алгоритм Р. Бойера и Дж. Мура по сравнению с линейным поиском требует значительно меньших временных затрат.

^ Основная идея
Поиск ведется от начала строки s, но с конца искомой подстроки x, для которой формируется таблица, размерность которой равна 256 - количеству всех символов в машинном алфавите. В таблице записываются расстояния от последнего символа искомой подстроки x до каждого ее символа. ( Если в x встречаются одинаковые символы, то в таблицу заносится расстояние до ближайшего из них. ) Если символ не входит в x, то в соответствующую ячейку таблицы заносится m - длина подстроки x. Когда очередной символ подстроки не совпадает с очередным символом строки s, для последнего из таблицы определяется расстояние, после чего x

сдвигается вправо на соответствующее число позиций. Тем самым ряд позиций пропускается, время поиска сокращается.



Пример
Пусть s =’Мила мало мылась мылом’, x =’ мыло’.

Длина x равна 4. Составим таблицу расстояний.
М Ы Л О

1

2

3
Расстояние до символа равно m-j, где j - индекс этого символа, а m - длина строки x.

Таблица расстояний ( sd ) выглядит так:


Символ

Расстояние

...

А

...

К
Л

М

Н
О

П

...

Ъ

Ы

Ь

...

...

4

...

4

1

3

4

4

4

...

4

2

4

...



Для всех символов, кроме выделенных, расстояние равно 4.

Будем выделять из строки s фрагменты длиной m и сравнивать их последовательно, начиная с конца, с соответствующими символами строки x. Пусть j - номер обрабатываемого символа строки x. Чтобы определить номер соответствующего символа s, нужно знать, с какой позиции начинается рассматриваемый фрагмент строки s. Обозначим через i номер символа, предшествующего первому символу обрабатываемого фрагмента. Тогда номер символа во фрагменте строки s, соответствующего j-му символу x, определяется как i+j.
1-й шаг

i = 0, m = 4. Рассмотрим первые 4 символа s и строку x. Начнем сравнивать их с конца. Для j = 4 s [ i+j ] x [ j ] ( s[4] x[4] ). Следовательно, далее можно не сравнивать, поскольку можно уже сказать, что этот фрагмент строки s не может являться искомой подстрокой ( имеется по крайней мере одно несовпадение ). Поэтому перейдем к следующему фрагменту.
2-й шаг

Теперь надо определить номер первого символа нового фрагмента. Для этого заметим, что так как последнего символа фрагмента s ( ‘A’ ) в x нет, то фрагменты со 2-го, 3-го, 4-го символов s можно не рассматривать, а нужно сразу перейти к фрагменту с позиции 5. В этом случае новое значение i получится прибавлением к старому значению sd [ ‘A’ ].

Таким образом, новый фрагмент строки s - ‘ мал’. Начинаем новые сравнения с конца. Так как ‘Л’  ‘О’, этот фрагмент снова можно далее не рассматривать.
3-й шаг

Поскольку символ ‘Л’ в искомой строке есть, то он может являться предпоследним. Следовательно, новое значение i = 5 ( определяется как 4+sd [‘Л’] = 4+1 ). Рассматриваем ‘МАЛО’ и ‘МЫЛО’: s [ 9 ] = x [ 4 ], s [ 8 ] = x [ 3 ], s [ 7 ]  x [ 2 ] ( ‘А’’Ы’ ), значит, и этот фрагмент строки s не является искомым.
^ 4-й шаг

Четвертый фрагмент ( i = 9 ) ‘МЫЛ’ ( см. 2-й шаг ) снова не совпадает с x.
5-й шаг

Для следующего фрагмента значение i = 9+sd [‘Л’] =10. После первого сравнения можно сказать, что этот фрагмент тоже не подходит.
6-й шаг

i =14. Фрагмент ‘СЬ М’ пропускаем после первого сравнения.
7-й шаг

i =17 ( 14+sd [‘М’] =14+3 ). Сравниваем ‘МЫЛО’ и ‘МЫЛО’:

Искомая подстрока найдена с позиции 18.

Задача решена.
Программа, реализующая этот алгоритм, выглядит так:
Program n11;var s,x: string; sd: array[0..255] of integer;Procedure search(s,x: string);var i,j,n,m: integer; f: boolean; h: char;begin n:=length(s); { Определение длин строки и подстроки } m:=length(x); { Начальное заполнение массива расстояний }

for i:=0 to 255 do sd[i]:=m;

for i:=1 To m-1 do { Заполнение массива расстояний }

begin

h:=x[i];

sd[ord(h)]:=m-i;

end;

i:=1; f:=False; { Признак того, что подстрока найдена}

while (i<n-m+1) and (not f) do

begin

j:=m;

while (j>0) and (s[i+j]=x[j]) do j:=j-1;

if j=0 then f:=true { Полное совпадение! }

else i:=i+sd[ord(s[i+j])];

end;

if f then writeln(x,' - является подстрокой ',s,' с позиции ',i+1)

else writeln('нет вхождения');

end;

begin { Основная программа }

writeln('Введите строку s:');

readln(s);

writeln('Введите подстроку x:');

readln(x);

search(s,x);

readln

end.

Примеры




В приведенном ниже примере берется массив случайных чисел; массив сортируется, после чего с применением 2-х методов поиска ( метод половинного деления и метод простого перебора ) осуществляется поиск элемента x.
program pr1;{ программа поиска }

uses crt;

const max=100;

type feld=array[1..max] of integer;

var f:feld;

x:integer;
procedure binaersuchen(x:integer;f:feld);

(* Поиск методом половинного деления.

Массив должен быть отсортирован. *)

var i,rechts,links,mitte:integer;

found:boolean;

begin

links:=1; rechts:=max;

repeat mitte:=(links+rechts) div 2;

if x<f[mitte] then rechts:=mitte-1

else links:=mitte+1;

found:=x=f[mitte];

until found or (links>rechts);

if found

then

begin

write(x:3,'при i=',mitte:3);

writeln(' успешный поиск');

end

else writeln(x:3,' безрезультатный поиск');

end; (* по методу половинного деления *)
procedure feld_anlegen(var f:feld);

var i:integer;

begin

for i:=1 to max do f[i]:=random(99)+1;

end; { заполнение массива }
procedure druckfeld(f:feld);

var i:integer;

begin

for i:=1 to max do write(f[i]:4);

writeln;

end; { поле печати }
procedure ksuchen(x:integer; f:feld);

(* Простой перебор сверху вниз *)

var i:integer;

found:boolean;

begin

i:=1; found:=false;

while (i<=max) and not found do

begin

found:=x=f[i];

inc(i);

end;

if found

then writeln(x:3,'при i=',i-1:3,'элемент найден')

else writeln(x:3,'элемент не найден');

end; (* поиск *)
procedure sortiere(var f:feld);

var i,j,hilf:integer;

begin

(* Здесь просто сравниваются два соседних элемента

и соответствующим образом меняются местами (см.

следующий пример); это простейший, но к сожале-

нию, малоэффективный метод сортировки *)

for i:=1 to max-1 do

for j:=i+1 to max do

if f[j]<f[i] then {f[i] и f[j] меняются местами}

begin

hilf:=f[i];

f[i]:=f[j];

f[j]:=hilf;

end;

end; { сортировка }
begin (********** Исполняемая часть **********)

feld_anlegen(f);

druckfeld(f);

sortiere(f);

druckfeld(f);

writeln('Какое число искать? (Конец=0)');

readln(x);

while x<>0 do begin

ksuchen(x,f);

binaersuchen(x,f);

write('Какое число');

writeln(' искать?');

readln(x);

end;

end.


Центральной проблемой обработки данных является сортировка множества данных. Существует большое число методов сортировки. Следующий пример демонстрирует три элементарных способа поиска, добавления и замены элементов массива с некоторыми их модификациями ( heapsort, shellsort, quicksort ).


(* Здесь приведено три наиболее распространенных алгоритма,

применяемых при сортировке массива: перебор, добавление,

замена. Реализуется основной принцип сортировки. Каждый

способ допускает модификацию. Они известны

для: перебора как heapsort

добавления shellsort

замены quicksort

Частично отсортированный массив состоит из:

выходной последовательности =

уже отсортированный кусок в начале массива;

исходной последовательности =

не отсортированный кусок в конце массива. *)


program pr2;

{программа сортировки}

uses crt;

const n=1000;

type feld=array[-9..n] of integer;

(* -9 по методу shellsort *)

var a:feld;

anz,nr:integer;
procedure eingabe(var f:feld);

var i:integer;

begin

for i:=1 to anz do f[i]:=random(99)+1;

end; (* Ввод *)
procedure druckfeld(f:feld);

(* Выдаются первые 20 элементов *)

var i:integer;

begin

for i:=1 to 20 do write(f[i]:4); writeln;

end; (* Поле печати *)
procedure austausch(var a:feld);

(* Последовательно сравниваются между собой два соседних

элемента и соответствующим образом меняются местами.

Это самый примитивный способ сортировки ( называемый

также пузырьковым методом или методом британского музея).*)
var i,j,x:integer;

begin (*Прямая замена*)

for i:=2 to anz do

for j:=anz downto i do

if a[j-1]>a[j] then (* поменять местами *)

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x;

end;

end; (* Замена *)
procedure quicksort(var a:feld);

(* Число операций перемены местоположения элементов внутри

массива значительно сократится, если менять местами да-

леко отстоящие друг от друга элементы. Для этого выбира-

ется для сравнения один элемент x ( наиболее целесообразно

выбрать элемент из середины массива), отыскивается слева

первый элемент, который не меньше x, а справа первый эле-

мент, который не больше x. Найденные элементы меняются

местами. После первого же прохода все элементы, которые

меньше x, будут стоять слева от x, а все элементы, кото-

рые больше x,- справа от x. С двумя половинами массива

поступают точно так же. Из-за такой рекурсии метод оформ-

ляется как процедура. *)
procedure quicks(links,rechts:integer);

var i,j,x,w:integer;

begin

i:=links; j:=rechts;

x:=a[(links+rechts) div 2];

repeat

while a[i]<x do i:=i+1;

while x<a[j] do j:=j-1;

if i<=j then

begin

w:=a[i]; a[i]:=a[j]; a[j]:=w;

i:=i+1; j:=j-1;

end;

until i>j;

if links<j then quicks(links,j);

if i<rechts then quicks(i,rechts);

end; (* quicks *)
(* Работа с алгоритмом заключается тогда в серии

отдельных обращений *)

begin

quicks(1,anz);

end; (* quicksort *)
procedure einfuegen(var a:feld);

(* Из исходной последовательности берется следующий элемент

и добавляется в выходной массив, причем для него с шагом

1 ищется соответствующее место, начиная с конца массива. *)

var i,j,x:integer;

begin (* Непосредственное добавление *)

for i:=2 to anz do

begin

x:=a[i]; a[0]:=x; j:=i-1;

while x<a[j] do

begin

a[j+1]:=a[j];

j:=j-1;

end;

a[j+1]:=x;

end;

end; (* Добавление *)
procedure shellsort(var a:feld);

(* Алгоритм добавления выполняется t раз с уменьшающимся

каждый раз шагом s[1], s[2], ..., s[t] для "следующего

x". Пусть s[1]=anf, а s[t]=1. Для того, чтобы установить

конечную метку для добавления, нужно массив a сначала

продлить на начальную длину шага anf. Итак, нужно задать

type feld = array[-anf..n] of integer;

Для выбора шага рекомендуется, например, 40, 13, 4, 1

или 31, 15, 7, 3, 1 или 9, 5, 4, 1 *)

var s:array[1..4] of integer;

marke,m,t,i,j,k,x:integer;

begin (* shellsort *)

t:=4; s[4]:=1; s[3]:=3; s[2]:=5; s[1]:=9;

for m:=1 to t do

begin

k:=s[m]; marke:=-k;

for i:=k+1 to anz do

begin

x:=a[i];

j:=i-k;

if marke=0 then marke:=-k;

marke:=marke+1;

a[marke]:=x;

while x<a[j] do

begin

a[j+k]:=a[j]; j:=j-k;

end;

a[j+k]:=x;

end;

end;

end; (* shellsort *)
procedure auswahl(var a:feld);

(* Из исходной последовательности выбираются те элементы,

которые следует добавить в конец выходной последователь-

ности *)

var i,j,k,x:integer;

begin (* Прямой выбор *)

for i:=1 to anz-1 do

begin

k:=i; x:=a[i];

for j:=i+1 to anz do

{ В оставшейся части ищется наименьший элемент }

if a[j]<x then

begin

k:=j;

x:=a[j];

end;

a[k]:=a[i]; a[i]:=x;

end;

end; (* Перебор *)
procedure heapsort(var a:feld);

(* При выборе сохраняется появляющаяся по пути информация

о соотношениях между элементами ( теряющаяся при прямом

переборе), так что следующий шаг выбора значительно сок-

ращается. Согласно предварительному условию о том, что

место в памяти должно использоваться лишь для хранения

a, весь массив a предварительно упорядочивается таким

образом, чтобы всеми элементами выполнялись следующие

соотношения:

a[i]>=a[2i] для всех i=1, ..., n/2

a[i]>=a[2i+1]

Упорядоченный таким образом массив называется "кучей"

(heap - динамическая область). Вначале в состояние "ку-

чи" приводится левая половина массива a. Затем берется

первый элемент справа ( поскольку он имеет наибольшее

значение ), правая граница сдвигается влево на единицу

и остальной массив вновь отфильтровывается, чтобы опять

получить "кучу". Затем повторяется тот же процесс. Итак,

в отличие простого перебора выходная последовательность

формируется справа. *)
var rechts,links,x:integer;

procedure sieb;

(* Массив a, как и переменные links,rechts

является глобальным *)

var i,j:integer;

begin

i:=links; j:=2*i; x:=a[i];

while j<=rechts do

begin

if j<rechts then

if a[j]<a[j+1] then j:=j+1;

if x<a[j] then

begin

a[i]:=a[j]; i:=j;

j:=2*i;

end

else j:=rechts+1;

end;

a[i]:=x;

end; (* Фильтрация *)
begin (* heapsort *)

rechts:=anz;

for links:=(anz div 2) downto 1 do sieb;

(* В результате получим массив в форме "кучи" *)

(* Теперь начнем сортировать *)

while rechts>1 do

begin

links:=1;

x:=a[links];

a[links]:=a[rechts];

a[rechts]:=x;

rechts:=rechts-1;

sieb;

end;

end; (* heapsort *)
begin (********** Исполняемая часть **********)

write('Сколько элементов (<=1000):');

readln(anz);

eingabe(a);

clrscr;

druckfeld(a);

writeln(anz:50);

writeln ('Какой метод?');

writeln ('1=einfuegen');

writeln ('2=shellsort');

writeln ('3=auswaehlen');

writeln ('4=heapsort');

writeln ('5=austauschen');

writeln ('6=quicksort');

readln(nr);

writeln('Внимание:'); delay(500); write(^g);
case nr of

1: einfuegen(a);

2: shellsort(a);

3: auswahl(a);

4: heapsort(a);

5: austausch(a);

6: quicksort(a);

else writeln('Ничего не нужно'); end;

write(^g);

writeln('Выполнить с сортировкой:');

druckfeld(a);

end.
Здесь будут считаны n чисел и отсортированы в соответствии с таблицей ASCII ( таблица кодов ).


program pr3;

{ Программа сортировки строк }

uses crt;

const n=10;

type feld=array[1..n] of string[10];

var z:feld;
procedure lies(var a:feld);

var i:integer;

begin

clrscr;

for i:=1 to n do

begin

write('слово: ',i:2,' '); readln(a[i]);

end;

end; (* Считывание *)
procedure drucklinks(f:feld);

(* Выдается массив слов, выравненных по левому краю *)

var i:integer;

begin

for i:=1 to n do writeln(f[i]);

end; (* Печать *)
procedure druckrechts(f:feld);

(* Выдается массив слов, выравненных по правому краю *)

var i:integer;

begin

for i:=1 to n do writeln(f[i]:10);

end; (* Печать *)
procedure sortieren(var a:feld);

var i,j:integer;

x:string[10];

begin (* Прямой перебор *)

for i:=2 to n do

for j:=n downto i do

if a[j-1]>a[j] then (* Перемена местами *)

begin

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x;

end;

end; (* Сортировка *)
begin (********** Исполняемая часть **********)

lies(z);

writeln('до сортировки:');

drucklinks(z);

sortieren(z);

writeln(^j'после сортировки:');

druckrechts(z);

end.


В завершении нашего обзора сравним эффективность описанных методов сортировки.

В качестве показателей для оценки того или иного метода в них используются количество сравнений и количество перемещений элементов в ходе сортировки. Однако эти характеристики не учитывают затрат времени на другие операции, такие, как управление циклами и др. Очевидно, что критерием для сравнения различных методов является время, затрачиваемое на сортировку. Данные о времени выполнения процедур сортировки получены Н.Виртом. Конечно, современные компьютеры работают значительно быстрее чем тогда, когда были проведены расчеты. В тоже время относительные показатели различных методов в целом не изменились. В табл.1 представлены относительные характеристики 9 вариантов методов сортировки, полученные на основе результатов, приведенных Н.Виртом.


Метод сортировки

Упорядоченный массив

Случайный массив

Упорядоченный в обратном порядке массив

Сортировка простыми вставками

2.4

4.6

6.1

24.1

19.0

76.6

Сортировка выбором

97.8

338.4

8.5

32.6

18.8

72.3

“Пузырьковая” сортировка

108.0

433.0

17.1

67.6

40.3

160.3

Усовершенствованная “пузырьковая” сортировка

1.0

1.6

18.4

71.1

44.5

176.8

“Шейкер” – сортировка

1.0

1.8

16.0

60.7

43.8

176.2

Сортировка методом Шелла

11.6

23.2

2.1

5.8

4.2

13.3

Пирамидальная сортировка

23.2

50.1

1.8

4.0

2.8

6.1

Сортировка слиянием

19.8

46.8

1.7

4.0

2.7

6.3

Быстрая сортировка

6.2

18.6

1.0

2.4

1.0

2.1

Табл.1 Сравнительные характеристики методов сортировки
Значение, равное 1, в каждой колонке соответствует наименьшему времени, затрачиваемому на сортировку массива указанным методом. Все остальные значения в столбце рассчитаны относительно минимальному времени.

Верхнее число в каждой колонке дано для массива из 256, а нижнее - для 512 элементов. Еще раз заметим, что современные компьютеры такие массивы отсортируют очень быстро, но в данном случае нас интересуют относительные показатели различных методов.

Приведенные данные демонстрируют явное различие методов n2 и log2n.

Из табл.1 видно, что наилучшим среди простых методов является сортировка вставками, среди усовершенствованных - быстрая сортировка. Н.Вирт отмечает также следующее:

  • “пузырьковая” сортировка является наихудшим среди всех сравниваемых методов. Ее Улучшенный вариант – “шейкер” - сортировка - все-таки хуже, чем сортировка простыми вставками и сортировка выбором.

  • особенностью быстрой сортировки является то, что она сортирует массив с элементами, расположенными в обратном порядке практически так же, как и отсортированный в прямом порядке. Следует добавить, что приведенные результаты были получены при сортировке числовых массивов. Если же значением элементов массива являются данные типа “запись”, в которых сопутствующие поля (компоненты ) занимают в семь раз больше памяти, чем числовое поле, по которому проводится сортировка, то картина изменится на следующую.




Метод сортировки

Упорядоченный массив

Случайный массив

Упорядоченный в обратном порядке массив

Сортировка простыми вставками

2.4

9.2

6.1

18.8

19.0

58.1

Сортировка выбором

97.8

109.4

8.5

10.1

18.8

38.6

“Пузырьковая” сортировка

108.0

122.0

17.1

53.5

40.3

151.3

Усовершенствованная “пузырьковая” сортировка

1.0

1.0

18.4

54.0

44.5

155.7

“Шейкер” – сортировка

1.0

1.0

16.0

51.2

43.8

155.6

Сортировка методом Шелла

11.6

37.2

2.1

6.2

4.2

11.8

Пирамидальная сортировка

23.2

52.8

1.8

4.1

2.8

6.1

Сортировка слиянием

19.8

39.2

1.7

3.2

2.7

5.0

Быстрая сортировка

6.2

11.0

1.0

2.3

1.0

2.0

Табл.2 Сравнительные характеристики методов сортировки массивов данных типа “запись”
Верхнее число в каждой колонке относится к сортировке числового массива, а нижнее - массива данных типа “запись” ( число элементов в обоих случаях 256 ).

Видно, что

1.Сортировка выбором дает существенный выигрыш и оказывается лучшим из простых методов.

  1. “Пузырьковая” сортировка по-прежнему является наихудшим методом.

Быстрая сортировка даже укрепила свою позицию в качестве самого быстрого метода и оказалась действительно лучшим алгоритмом сортировки
1   2   3   4   5   6   7   8   9   10   11



Скачать файл (2205.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru