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:
Загрузка...
^

1.1. Сортировка методом простого выбора

1.2. Сортировка методом простого обмена

1.3. Сортировка методом прямого включения

1.4. Сортировка методом слияний

1.5. Обменная сортировака с разделением (сортировка Хоара)


2. Алгоритмы поиска информации

2.1. Линейный поиск

2.2. Линейный поиск с использованием барьера

2.3. Бинарный поиск

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

3.1. Прямой поиск

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

4. Пример
Для решения многих задач удобно сначала упорядочить данные по определенному признаку. Процесс упорядочивания заданного множества объектов по заданному признаку называется сортировкой.

Данные, например, элементы массива, можно отсортировать:

  • по возрастанию – каждый следующий элемент больше предыдущего:

a[1] < a[2] < ... < a[n];

  • по неубыванию – каждый следующий элемент не меньше предыдущего:

a[1] ≤ a[2] ≤ ... ≤ a[n];

  • по убыванию – каждый следующий элемент меньше предыдущего:

a[1] > a[2] > ... >a[n];

  • по невозрастанию – каждый следующий элемент не больше предыдущего: a[1] ≥ a[2] ≥ ... ≥ a[n].

Простейшими примерами могут служить следующие задачи.

^

Сортировка

Сортировка методом простого выбора



Этот метод сортировки обычно применяется для массивов, не содержащих повторяющихся элементов. Для достижения поставленной цели можно действовать следующим образом:

  1. выбрать максимальный элемент массива;

  2. поменять его местами с последним элементом ( после этого наибольший элемент будет стоять на своем месте );

  3. повторить пп.1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним (n-1) - м элементом массива и так далее, пока не останется один элемент, уже стоящий на своем месте.

Всего потребуется n-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться.

Рассмотрим этот процесс на примере. Пусть исходный массив а состоит из 10 элементов и имеет вид:
5 13 7 9 1 8 16 4 10 2
После сортировки массив должен выглядеть так:
1 2 4 5 7 8 9 10 13 16
Процесс сортировки представлен ниже. Максимальный элемент текущей части массива заключен в кружок, а элемент, с которым происходит обмен, - в квадратик. Скобкой помечена рассматриваемая часть массива.

1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент -16 ( он стоит на седьмом месте ); поменяем его местами с последним элементом.




5 13 7 9 1 8 16 4 10 2
Максимальный элемент помещен на свое место.
2-й шаг: рассмотрим часть массива с первого до девятого элемента. Максимальный элемент этой части стоит на втором месте и имеет значение 13. Поменяем его местами с последним элементом этой части.




5 13 7 9 1 8 2 4 10 16
Отсортированная часть массива состоит теперь уже из двух элементов.
3-й шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент ( его значение 10 ) и последний элемент этой части ( его значение 4 ).
5 10 7 9 1 8 2 4 13 16
В отсортированной части массива теперь стало 3 элемента.
4-й шаг: аналогично.
5 4 7 9 1 8 2 10 13 16
5-й шаг: максимальный элемент этой части массива является последним в ней, поэтому его нужно оставить на своем месте.




5 4 7 2 1 8 9 10 13 16
Далее действуем аналогично.
6-й шаг:

5 4 7 2 1 8 9 10 13 16


7-й шаг:

5 4 1 2 7 8 9 10 13 16


8-й шаг:

2 4 1 5 7 8 9 10 13 16



9-й шаг:

2 1 4 5 7 8 9 10 13 16



Итог: 1 2 4 5 7 8 9 10 13 16


Для программной реализации этого процесса необходимо организовать цикл по длине рассматриваемой части массива, которая изменяется от n до 2. В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части.

Теперь можем записать алгоритм сортировки:

For i: = n Downto 2 Do

Begin

найти максимальный элемент из a[1], ..., a[i]; запомнить его индекс в переменной

k; если i<>k поменять местами a[i] и a[k]

End;
Опишем этот алгоритм подробно:
program n1;

type ar=array [1..10] of integer;

var i:integer;

a:ar;
Procedure sorting1(var a:ar);

{поскольку в процессе работы процедуры массив изменится, формальный

параметр а описывается как параметр-переменная}

var i,j,k:integer;

m:integer;

{значение максимального элемента рассматриваемой части массива}

begin

for i:=10 downto 2 do

{цикл по длине рассматриваемой части массива}

begin

{поиск максимального элемента и его номера в текущей части массива}

k:=i;

m:=a[i];

{начальные значения максимального элемента и

его индекса в рассматриваемой части массива}

for j:=2 to i-1 do

if a[j]>m then begin k:=j; m:=a[k] end;

if k<>i then

begin {перестановка элементов}

a[k]:=a[i];

a[i]:=m;

end;

end;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to 10 do read(a[i]);

sorting1(a);

writeln('Отсортированный массив:');

for i:=1 to 10 do write(a[i],' ');

writeln;

end.


При решении практических задач упорядочивание x1,...xn как правило сопровождается некоторыми дополнительными действиями. Например, если x1, y1, x2, y2, ..., xn, yn - это значения аргумента x и некоторой функций y=f(x), то перестановка x1, ..., xn должна сопровождаться перестановкой y1, ..., yn. Элементы y1, ..., yn переставляются так же, как x1, ..., xn вне зависимости от значений самих

y1, ..., yn. Рассмотрим эту задачу; переставленные значения x1, y1, x2, y2, ..., xn будут выведены в два столбца:

x1 y1

x2 y2

.....

xn yn

program tab;

const n=5;

type u=array[1..n] of real;

var x,y:u;

v:real;

i,j,k:integer;

begin

for i:=1 to n do read(x[i],y[i]);

for i:=1 to n do begin

k:=i;

for j:=i+1 to n do

if x[j]<x[k] then k:=j;

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

v:=y[i]; y[i]:=y[k]; y[k]:=v;

writeln(x[i],y[i]);

end;

end.

^

Сортировка методом простого обмена



Сортировка методом простого обмена может быть применена для любого массива. Этот метод заключается в последовательных просмотрах массива слева направо ( от начала к концу ) и обмене местами соседних элементов, расположенных “неправильно”, то есть таких, что i < j, а a[i] > a[j]. Опишем этот метод подробнее.

Начнем просмотр с первой пары элементов ( a[1] и a[2] ), если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем без изменения. Затем берем вторую пару элементов ( a[2] и a[3] ), если a[2] > a[3], то меняем их местами и так далее. На первом шаге будут просмотрены все пары элементов массива a[i] и a[i+1] для i от 1 до n-1. В результате максимальный элемент массива переместится в конец массива.

Поскольку самый большой элемент находится на своем месте, рассмотрим часть массива без него, то есть с первого до (n-1) - го элемента. Повторим

предыдущие действия для этой части массива, в результате чего второй по величине элемент массива переместится на последнее место рассматриваемой части массива, то есть на ( n-1 ) - е место во всем массиве. Эти действия продолжают до тех пор, пока количество элементов в текущей части массива не уменьшится до двух. В этом случае необходимо выполнить последнее сравнение и упорядочить последние два элемента. При сортировке выполняется n-1 просмотр массива.
Пример

Отсортируем по возрастанию методом простого обмена массив из 5 элементов: 5 4 8 2 9

Длина текущей части массива - n-k+1, где k - номер просмотра, i - номер проверяемой пары; номер последней пары - n-k. За вертикальной чертой располагаются отсортированные элементы.
^ Первый просмотр: рассматривается весь массив.
i = 1 5 > 4 8 2 9




обмен
i = 2 4 5 < 8 2 9

нет обмена
i = 3 4 5 8 > 2 9




обмен

i = 4 4 5 2 8 < 9

нет обмена
9 стоит на своем месте.
^ Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.
i = 1 4 < 5 2 8  9

нет обмена
i = 2 4 5 > 2 8  9




обмен
i = 3 4 2 5 < 8  9

нет обмена
8 стоит на своем месте.
Третий просмотр: рассматриваемая часть массива содержит три первых элемента.


i = 1 4 > 2 5  8 9




обмен


i = 2 2 4 < 5  8 9

нет обмена
5 стоит на своем месте.
Четвертый просмотр: рассматриваем последнюю пару.


i = 1 2 4 < 5  8 9

нет обмена
4 стоит на своем месте.
Для самого маленького элемента ( 2 ) остается только одно место - первое.

Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод называют также методом “пузырька”. Название это происходит от обратной интерпретации, при которой в процессе выполнения сортировки более “ легкие ” элементы ( элементы с заданным свойством ) мало - помалу всплывают на “поверхность”.
Программа “пузырьковой” сортировки.
program n2;const n=5;type ar=array [1..n] of integer;

var i:integer;

a:ar;
procedure sorting2(var a:ar);

var k,i,t:integer;

{k - номер просмотра (изменяется от 1 до n-1)

i - номер рассматриваемой пары

t - промежуточная переменная для перестановки местами элементов}

begin

for k:=1 to n-1 do

{цикл по номеру просмотра}

for i:=1 to n-k do

if a[i]>a[i+1] then

{перестановка элементов}

begin

t:=a[i];

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

a[i+1]:=t;

end;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

sorting2(a);

writeln('Отсортированный массив:');

for i:=1 to n do write(a[i],' ');

writeln;

end.

^

Сортировка методом прямого включения



Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.

Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть

а [1] ≤ а [2] ≤ ... ≤ a [k-1].

Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j ( 1 ≤ j ≤ k -1 ), что а [j] ≤ a[k] < a[j+1]. Затем вставить элемент а [k] на найденное место.

С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.

Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения
1 - й шаг

13 6 8 11 3 1 5 9 15 7 Рассматриваем часть массива из одного эле-

мента ( 13 ). Нужно вставить в нее второй

элемент массива ( 6 ) так, чтобы упорядочен-

ность сохранилась. Так как 6 < 13, вставляем

6 на первое место. Отсортированная часть

массива содержит два элемента ( 6 13 ).







2 - й шаг

6 13 8 11 3 1 5 9 15 7 Возьмем третий элемент массива ( 8 ) и под-

берем для него место в упорядоченной части

массива. 8 > 6 и 8 < 13 , следовательно, его

нужно вставить на второе место.




3 - й шаг

6 8 13 11 3 1 5 9 15 7 Следующий элемент - 11. Он записывается в упорядоченную часть массива на третье место, так как 11 > 8 , но 11 < 13.




4 - й шаг

6 8 11 13 3 1 5 9 15 7 Далее, действуя аналогичным образом,

определяем, что 3 необходимо записать на

первое место.




5 - шаг

3 6 8 11 13 1 5 9 15 7 По той же причине 1 записываем на первое

место.




6 - шаг

1 3 6 8 11 13 5 9 15 7 Так как 5 > 3, но 5 < 6 то место 5 в упоря-

доченной части - третье.







7 - шаг

1 3 5 6 8 11 13 9 15 7 Место числа 9 - шестое.




8 - шаг

1 3 5 6 8 9 11 13 15 7 Определяем место для предпоследнего

элемента 15. Оказывается, что этот эле-

мент массива уже находится на своем месте.
9 - шаг

1 3 5 6 8 9 11 13 15 7 Осталось подобрать подходящее место для

последнего элемента ( 7 ).



1 3 5 6 7 8 9 11 13 15 Массив отсортирован полностью.
Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения:

For k: = 2 To n Do

{ так как начинам сортировку с поиска подходящего места для a[2], i изменяется от 2 до n }

Begin

x: = a[k];

‘вставить x на подходящее место в a[1] , ..., a[k] ‘

End;

Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее x ( то есть те, которые уже упорядочены ), двигаясь к началу массива. Нужно просматривать элементы a[ j ] , j изменяется от k-1 до 1. Такой просмотр должен закончиться при выполнении одного из следующих условий:

  • найден элемент a[j] < x, что говорит о необходимости вставки x между a[j-1] и a[j].

  • достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место.

До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на первую позицию вправо, в результате чего в отсортированной части будет освобождено место под x.
Программа сортировки методом прямого включения:
program n3; { Сортировка по убыванию }

const n=5;

type ar=array [1..n] of integer;

var i:integer;

a:ar;
procedure sorting3(var a:ar);

var i,j,x,k:integer;

begin

for k:=2 to n do

begin

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

while (j>0)and(x>=a[j]) do

begin

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

dec(j);

end;

a[j+1]:=x;

end;

end;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

sorting3(a);

writeln('Отсортированный массив:');

for i:=1 to n do write(a[i],' ');

writeln;

end.

^

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



Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.

Этот метод состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности и впоследствии “сливаются” в одну.

Пусть массив а [1...n ] разбивается на части длиной k, тогда первая часть - а [ 1 ], а [ 2 ], ...., а [ k ], вторая - а [ k +1 ], а [ k + 2 ], ...., а [ 2k ] и так далее. Если n не делится на k, то в последней части будет менее k элементов.

После того как массивы - части упорядочены, можно объединить их в упорядоченные массивы - части, состоящие не более чем из 2 k элементов, которые далее объединить в упорядоченные массивы длиной не более 4 k, и так далее, пока не получится один упорядоченный массив.

Таким образом, чтобы получить отсортированный массив этим методом, нужно многократно “сливать” два упорядоченных отрезка массива в один упорядоченный отрезок. При этом другие части массива не затрагиваются.
Задача
Дан массив а [ 1...k ] целых чисел и числа k, m, n, такие, что k ≤ m ≤ n. Описать процедуру, которая сливает отрезки массива а [ k + 1 ], ..., а [ m ] и а [ m + 1 ], ,...., а [ n ] в упорядоченный отрезок а [ k + 1 ], ..., а [ n ].

Основная идея решения состоит в сравнении очередных элементов каждой части, выяснении, какой из них меньше, переносе его в массив с, который является вспомогательным, и продвижении по тому массиву - части, из которого взят элемент. Когда одна из частей будет пройдена до конца, остается только перенести в с оставшиеся элементы второй части, сохраняя их порядок.
Рассмотрим пример.
Пусть первая часть ( часть а ) состоит из 5 элементов:

... 3 5 8 11 16 ...,

а вторая часть ( часть b ) - из 8 элементов:

... 1 5 7 9 12 13 18 20 ...

По условию оба массива - части упорядочены. Нужно сформировать массив с, который будет содержать 13 элементов.

Введем обозначения:

i - номер обрабатываемого элемента части а;

j - номер обрабатываемого элемента части b;

g - номер заполняемого массива части с.

Поскольку заполнение массива с ведется с его начала, на первом шаге значение g =1.
1 -й шаг: на первое место в массиве с претендуют а [k + 1] = 3 и

b [ m + 1 ] = 1 ( i = k + 1, j = m + 1 ). Так как 1 < 3, в массив с нужно занести 1 и перейти к следующему элементу части b, то есть увеличить j на 1 (значение j станет равно m + 2 ), а также увеличить на 1 значение g ( значение g будет равно 2 ).
2 -й шаг: теперь нужно сравнить а [ k + 1 ] = 3 и b [ m + 2 ] = 5 . 3 < 5, следовательно, на второе место в с надо занести а [ k + 1 ] = 3. Затем нужно увеличить на одно значение i и g.
3 -й шаг: на третье место массива с претендуют два одинаковых элемента - а [ k + 2 ] = 5 и b [ m + 2 ] = 5. В этом и подобных случаях договоримся заносить в с первым элемент из части а. Таким образом, с [ 3 ] = а [ k + 2 ], а значение

g = 4, i = k + 3, j остается равным m + 2.

4-11 - й шаги: рассуждая аналогичным образом, нужно занести в с элементы 5, 7, 8, 9, 11, 12, 13, 16.

После выполнения 11 - го шага первая часть будет занесена в с полностью, значение g равно m + 7, значение g = 12.
12 - й шаг: так как часть а закончилась, а “хвост” части b упорядочен по условию, то двенадцатым элементом массива с будет первый элемент “хвоста” b, то есть b [ m + 7 ] = 18.
13 -й шаг: последним элементом массива с будет последний элемент b – 20.

На рисунке схематично изображен процесс заполнения массива c.

часть a

... 3 5 8 11 16 ...






шаг 2 шаг 3 шаг 6 шаг 8 шаг 11

3>6 5=5 8<9 11<12 16<19










C

1

3

5

5

7

8

9

11

12

13

16

18

20
1   2   3   4   5   6   7   8   9   10   11



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

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

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