Решение прикладных задач в среде Паскаль.
методическая разработка по информатике и икт (11 класс) на тему

Решение прикладных задач в среде Паскаль.

Нахождение необходимых данных из большого количества информации — это одна из фундаментальных операций, называемая поиском. Поиск используется буквально всюду: в базах данных, текстах, файлах, сайтах, электронных таблицах и т.д., и т.п. Это одна из самых распространённых операций. Насколько разнообразны формы поиска, настолько разнообразны и алгоритмы, которые используются для этого. Однако задача не сводится просто к созданию алгоритма для того или иного поиска. Объёмы информации, используемые в современной информационной отрасли таковы, что востребованными сегодня окажутся только быстрые, а значит — эффективные алгоритмы. Об этом и пойдёт речь. Иными словами, вопрос стоит так: как повысить эффективность в общем-то понятных алгоритмов поиска. Для рассмотрения используем следующие алгоритмы:

1. «барьерный»;
2. дихотомический;

«Барьерный» алгоритм

Поиск производится в неупорядоченном массиве. Заметим, что алгоритм не привязан именно к массиву, т.е. носит достаточно универсальный характер.

Для начала рассмотрим простой линейный поиск. Считаем, что у нас есть массив а[1..n] из n элементов и  шаблон b для поиска.

Алгоритм таков:

i:=1;

while (i<=n) or (a[i]<>b) do i:=i+1;

if i>n then writeln(‘no’)

else writeln(i);

Проанализируем алгоритм. От условия a[i]<>b  избавится невозможно, всё-таки массив неупорядоченный и избавиться от поэлементного сравнивания с шаблоном невозможно. А вот от первого условия избавиться можно. Делается это с помощью так называемого «барьера»: просто в конце массива ставится шаблон b. Изящный приём, который упрощает и без того простой алгоритм. Итак, массив а[1..n+1] и шаблон b.

a[n+1]:=b;

i:=1;

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

if i:=n+1  then writeln(‘no’)

else writeln(i);

Попутные вопросы:

1. если шаблонное значение присутствует в массиве несколько раз, какое вхождение будет найдено?
2. можно ли найти сразу последнее вхождение?

Дихотомический поиск.

Существует большое количество задач, в которых осуществляется поиск информации в некотором списке. Ранее нами использовался метод линейного поиска суть которого заключается в последовательном про смотре всего списка элементов массива и сравнении значения очередного элемента с за данным для поиска. Этот метод поиска эффективен на неупорядоченных массивах дан ных, а на предварительно отсортированных массивах значительно эффектив нее выполнять поиск другими методами. Например, метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, т.к. занимает много времени.

Одним из эффективных методов поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. Поиск производим в упорядоченном (обязательно!) массиве. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении ис комого элемента. Вместо просмотра подряд всех элементов упорядоченного массива его делят пополам (на две части). Т. к. массив отсортирован, то, сравнивая искомый элемент со значением среднего элемента массива, можно сделать вывод о том, может ли быть элемент с искомым значением в массиве и в какой половине он находится, т. е. определить область дальнейшего поиска.

Суть в следующем. Выбираем средний элемент массива. Если шаблон для поиска больше этого элемента, то поиск продолжаем только в правой части массива (считаем, что массив упорядочен по неубыванию), иначе — в левой части. Затем повторяем всё это для одной из этих частей массива. Закончим, когда наткнёмся на искомый элемент (случай успеха), либо когда границы рассматриваемой части массива схлопнутся (случай неуспеха).

Итак, имеем упорядоченный по неубыванию массив а[1..n] из n элементов и шаблон для поиска b.

l:=1; r:=n;        {границы поиска}

while l<=r do

begin        {бинарный поиск}

s:=(l+r) div 2;        {середина области поиска}

if a[s]=b then break;        {если элемент найден, выход}

if a[s]

end;

if a[s]=b then write(s);        {вывод результата}

else write(‘no’) ;