Поиск информации в массивах данных

Поиск информации в массивах данных         Занятие 13 1. Урок 1.  Поиск информации в одномерных массивах данных. 2. Урок 2.  Алгоритм   поиска    информации   в   отсортированном массиве данных ­ бинарный поиск 3. Урок 3.  Исследование алгоритма бинарного поиска. 4. Контрольные вопросы и упражнения.   Информацией люди оперируют с древних времен. В те времена, вероятнее всего, это была информация о физическом количестве чего­либо, например, дичи на месте охоты, количестве людей в племени, количестве напавших на племя   врагов и т.д. В дальнейшем, с появлением письменности, развитием искусств и техники, к информации о физическом   количестве   добавляется   информация   в  виде   произведений   литературы,   музыки,   живописи,     описания природных явлений, закономерностях в измерениях и счете физических величин, работы механизмов, машин и т.д. Это огромное   количество   информации   в   конечном   итоге   систематизировалось   и   превратилось   в   отдельные   области искусств, отдельные науки, библиотеки и патентные бюро. При этом возникла проблема систематизации, хранения, передачи   и   использования   информации.   Для   хранения   и   переработки   такой   информации   люди   придумывали   и создавали   различные   приспособления   и   устройства.   Простейшим   примером   может   служить   стойка   с   ящиками,   в которых хранятся карточки, несущие информацию. Такие каталоги непременный атрибут библиотек, которые в наше время заменяются компьютерными базами данных. Таким   образом,   возникла   наука  информатика,   которая   изучает   вопросы   получения,   хранения, преобразования передачи и использования информации.   Стремление  механизировать  и автоматизировать  процедуры  поиска  информации  в различных  документах привело   к   созданию   специальной   науки   ­  документалистики,  которая   является   частью   информатики.   Детищем документалистики стали ручные и автоматизированные информационно ­ поисковые системы, одним из основных показателей которых является время получения необходимой информации. Урок 1. Поиск информации в одномерных массивах данных В практических задачах имеют место списки, каких либо физических величин, например, продукции, которая изготовляется   отдельным  предприятием  или  хранится  на  складах   торгующей  организации,   списки  учета  владения недвижимостью или транспортными средствами и т.д.  Как правило,   физическая    величина   кодируется    цифровым или     символьно­цифровым   кодом   для   его   присваивания   физическим   величинам   и   занесения   в   списки   и   поиска информации   в     них.   В   настоящее   время   такая   работа   осуществляется   на   компьютерах.   Трудоемкой   и неавтоматизированной частью таких работ является формирование списков или  баз данных. Списки   можно   представить   как   одномерные   массивы   данных   разного   типа,   в   которых   отдельная   запись начинается   с   кода, по которому и осуществляется поиск. Когда списки измеряются десятками и сотнями тысяч записей, возникают проблемы поиска информации в них. Хорошей работой автоматизированной на базе компьютера (компьютеров) информационно­поисковой системы является та, когда человек не замечает время ответа системы на запрос или это время его не раздражает. Все это привело к необходимости преобразования списков таким образом, чтобы поиск информации в них был минимальным и изобретать алгоритмы, которые обеспечивали бы такой поиск. Еще раз пройдем этот мучительный путь человечества, задаваясь целью поиска некоторого значения элемента одномерного массива данных.  Задача.  Дан одномерный массив случайных целых положительных чисел. Провести исследование по оценке времени поиска значений отдельных элементов массива. Сделать выводы о зависимости времени поиска от размера массива. Постановка задачи. 1. Количество элементов массива вводить с клавиатуры, отвечая на сообщение "Введи количество элементов массива". Значение элементов массива получить генератором случайных чисел в диапазоне (0 ­:­ 1000). 2. 3. Искомое значение элемента массива вводить с клавиатуры, отвечая на сообщение "Введи искомое значение элемента массива" 4. Вывести   на   экран   дисплея   позицию   найденного   значения   с   сообщением   "Номер   позиции   найденного значения". Если элемент не найден вывести на экран дисплея сообщение "Элемент не найден". 5. Вывести на экран дисплея количество итераций (циклических операций), которые были проделаны для необходимого поиска с сообщением: "Количество итераций поиска" (количество итераций сопоставляется со временем поиска). Program V1L14P1; {Поиск некоторого значения элемента в одномерном массиве данных} Uses Crt; Var   a :array [1..30000] of integer; i,j,b,n :integer; k :boolean; {} 77 Поиск информации в одномерных массивах данных.  Бинарный поиск.  Исследование алгоритма бинарного поиска   begin ClrScr; {Randomize} Write('Введи количество элементов '); ReadLn(n); {Формирование одномерного массива случайных чисел  в диапазоне (0, 1000)}   for i:=1 to n do begin a[i]:=Random(1000); Write(a[i]:5); end; {} WriteLn; k:=True; Write('Введи значение искомого элемента '); ReadLn(b); Write(' Результат'); {Цикл поиска элемента массива} for i:=1 to n do if a[i]=b then begin {Печать значений элементов массива} {Конец цикла формирования массива} {Присвоение переменной булевского значения} WriteLn('Номер позиции искомого элемента ',i:4); k:=False; {Break} {k изменится на false} end; if k then WriteLn('Элемент не найден'); WriteLn('Количество итераций ',i:4); ReadKey  end. {Конец цикла поиска} {Если k не изменится} {Задержка работы программы до нажатия любой клавиши} Возможный результат работы программы Введи количество элементов  10    0  31 861 202 272 671 318 161 372 425 Введи значение искомого элемента  161 Результат Номер позиции искомого элемента    8 Количество итераций  10 В программе   процедура настройки (инициализации) генератора случайных чисел     Randomize  заключена в фигурные скобки и является комментарием, поэтому с каждым новым запуском программы на исполнение будем получать туже комбинацию случайных чисел, что и в предыдущий запуск,  если количество элементов будет тем же.  Попробуйте изменить количество элементов и получите другую комбинацию случайных чисел. Сравните эти комбинации и сделайте выводы. Уберите фигурные скобки в строке с Randomize и запустите программу на исполнение несколько раз.  Сделайте выводы по результатам работы программы. Данная задача поиска информации решалась в "лоб" т.е. простым перебором массива для сравнения его с искомыми данными и в каждый поиск нового заказанного значения происходил просмотр всех  элементов массива. Возможно, ли усовершенствование программы для сокращения времени поиска искомого значения элемента массива?  Да, если выходить из цикла просмотра сразу после нахождения поискового элемента. Для этого необходимо скорректировать программу  V1L14P1  и использовать процедуру   Break   для немедленного выхода из циклической операции по условию нахождения необходимого значения элемента массива. Удалите фигурные скобки, в которые заключена процедура Break и продолжите эксперимент с программой. Заметьте разницу в получаемых результатах и сделайте выводы. Возможный результат работы программы  после коррекции Введи количество элементов  10 202 272 Введи значение искомого элемента  161 0 31 861 671 318 161 372 425 Результат Номер позиции искомого элемента Количество итераций   8     8 Заметьте, что номер позиции искомого элемента равен количеству итераций, т.е. осуществляется выход из циклической операции поиска сразу же после нахождения необходимого значения поискового элемента. 78 В практических задачах имеет место корректировка списков для дополнения или удаления записей в них. В случае дополнения записей в списки, может увеличиться время поиска информации в них, если списки организованы по правилу   очереди   и  не   преобразованы  для   быстрого   поиска.   Такое   преобразование   массивов   данных   называется сортировкой, т.е.  упорядочиванием по возрастанию или убыванию  некоторого элемента записи, например, кода (см. занятия 9, 10). Поэкспериментируем с поиском информации в отсортированном массиве данных. Program V1L14P2; {Поиск информации в отсортированном массиве данных} Uses Crt; Var a :array [1..10000] of integer; b,i,j,p,n :integer; {} begin ClrScr; {Randomize;} Write('Введи количество элементов '); ReadLn(n); {} for i:=1 to n do     begin          a[i]:=Random(1000);          Write(a[i]:4)     end; WriteLn; {} WriteLn('Сортировка методом "пузырька"'); {Сортировка} for i:=1 to n do begin for j:=i+1 to n do begin if a[i]>a[j] then begin k:=a[i]; a[i]:=a[j]; a[j]:=k                                                            end; Write(a[i]:4) {Конец сортировки} end {Печать элементов сортированного массива} end; WriteLn; {} Write('Введите значение искомого элемента '); ReadLn(b);    {Перевод строки} {Поиск элемента в массиве данных} for i:=1 to n do if a[i]=b then begin WriteLn('Номер позиции искомого элемента ',i:4); Break {Альтернативный выход из циклической операции} end; if a[i]<>b then WriteLn('Элемент не найден'); {Конец поиска} WriteLn('Количество итераций ',i:4); ReadKey end. Возможный результат работы программы Введи количество элементов  10    0  31 861 202 272 671 318 161 372 425 Сортировка методом "пузырька"    0  31 161 202 272 318 372 425 671 861 Введи значение искомого элемента  161 79 Поиск информации в одномерных массивах данных.  Бинарный поиск.  Исследование алгоритма бинарного поиска   Результат Номер позиции искомого элемента    3 Количество итераций    3 Какие выводы можно сделать о результатах экспериментов? 1. Время  поиска  заданного  элемента  (или  записи  в случае списка)   в несортированном  массиве  является случайной величиной. 2. Время поиска зависит от размера массива. 3. В  случае  добавления   новых  данных  в  конец  списка,  время  поиска  их  будет увеличиваться. 4. В отсортированном массиве время поиска заданного элемента массива будет зависеть от размера массива и порядкового номера искомого элемента в массиве. Урок 2. Алгоритм поиска информации в сортированном массиве данных ­ бинарный поиск При внимательном изучении поиска информации в отсортированном массиве данных можно заметить, что искомый элемент может находиться только в одном месте (в случае, если в массиве он один) и делит весь массив на две половины. Следовательно, если, не приступая к поиску, сразу разделить массив на две половины и определить в какой из них он находится, то можно сократить время поиска, по крайней мере, в два раза. Далее разделяя на две половины ту половину исходного массива, где может находиться искомый элемент, возможно, сократить время поиска еще в два раза и т.д., пока искомый элемент не будет найден, или не  будет  выдано   сообщение  об   его   отсутствии.    Такой алгоритм    поиска информации получил название  бинарного  (от английского слова  binary ­двоичный).  Рассмотрим этот прием на примере задачи предыдущего урока. Program V1L14P3; {Бинарный поиск информации в одномерном массиве данных} Uses Crt; Var a :array [1..30000] of integer; i,j,k,n,b,bg,eg,m :integer; {} begin ClrScr; {Randomize;} Write('Введи количество элементов  '); ReadLn(n); {} for i:=1 to n do begin {Открыть скобки в желании получить новый массив случайных чисел} a[i]:=Random(1000); Write(a[i]:4) end; WriteLn; {} WriteLn('Сортировка методом "пузырька"'); for i:=1 to n do begin for j:=i+1 to n do begin if a[i]>a[j] then begin k:=a[i]; a[i]:=a[j]; a[j]:=k end end; Write(a[i]:4) end; WriteLn; {} Write('Введите значение искомого элемента '); ReadLn(b); {} WriteLn('       Результат'); bg:=1; eg:=n; WriteLn('Индекс среднего элемента границ поиска');       {Цикл бинарного поиска} m:=1; while bg<=eg do begin {Начало границы зоны поиска} {Конец границы зоны  поиска} 80 i:=(bg+eg) div 2;  WriteLn(i:4); if {Индекс среднего элемента} a[i]=b then Break {Альтернативный выход из цикла по логическому условию} else if a[i]20 then WriteLn('При n>20 массив не печатается'); for i:=1 to n do begin a[i]:=i; if n<=20 then Write(a[i]:4); {Значение элемента массива} {Логическое условие печати значений элементов массива} {Начальное значение количества делений зон поиска} {Перевод двух строк} {Начало границы зоны поиска} {Конец границы зоны  поиска} end; WriteLn;WriteLn; WriteLn ('Номера позиций элементов массива при последовательном его делении пополам'); bg:=1; eg:=n;         {Цикл бинарного поиска, ищется позиция элемента массива} m:=0; while bg<=eg do begin      i:=(bg+eg) div 2;      if          a[i]=a[n] then Break      else          if a[i]