9796

Задача поиска. Линейный поиск (последовательный поиск)

Реферат

Информатика, кибернетика и программирование

Задача поиска Постановка задачи: Задан массив содержащий n фамилий. Необходимо определить существует ли в этом массиве заданная фамилия. Если существует, необходимо вывести её номер, иначе сообщить об её отсутствии. Линейный поиск (последовательный ...

Русский

2013-03-17

48.5 KB

12 чел.

Задача поиска

Постановка задачи: Задан массив содержащий n фамилий. Необходимо определить существует ли в этом массиве заданная фамилия. Если существует, необходимо вывести её номер, иначе сообщить об её отсутствии.

Линейный поиск (последовательный поиск)

Будем предполагать, что каждый элемент массива уникален. Хотя, если это не так, то будем фиксировать только первое появление заданной строки в массиве.

Суть линейного поиска состоит в последовательной сравнении всех элементов массива с искомым элементом.

Алгоритм

Const n=100; 

Type  strtype=string[20];

Var  m=array[1..n] of strtype;

  found:boolean; (* элемент найден *)

  i:integer; (* номер элемента *)

  str:string; (* искомая строка *)

== == == == == == == ==

i:=0;

repeat

inc(i);

found := m[i]=str;

until found or (i=n);

if found

then writeln(‘Номер искомой строки=’,i)

else writeln(‘В массиве нет заданной строки.');

== == == == == == == ==

Анализ алгоритма линейного поиска

В общем случае при поиске линейным методом среди n элементов требуется в среднем n/2 сравнений в случае успешного поиска и n сравнений в наихудшем случае (если в массиве нет искомого элемента).

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

Постановка задачи

Задан массив m состоящий из n элементов типа string. Необходимо найти номер элемента содержащего строку str.

Алгоритм бинарного поиска

В самом начале процесса поиска обозначим в переменной low=1 номер первого элемента массива, в переменной high=n номер последнего элемента массива.

Сравнить значение str с элементом ряда в позиции, лежащей посередине между low и high. Если этот элемент равен str, то поиск успешно завершается. Если он больше, чем str, значением границы high должен стать номер проверявшейся позиции, уменьшенный на единицу. Если элемент в проверяемой позиции меньше str, то значением границы low должен стать номер проверявшейся позиции, увеличенный на единицу. Продолжать описанный процесс, пока значение str не найдено и при этом low меньше или равно high.

Пример поиска 1

Поиск строки Chester.

Элемент Chesterнайден!

Пример поиска 2. Поиск строки Baker.

Элемент Baker НЕ найден!

Своим названием метод бинарного поиска обязан заложенной в него идеи «отсечения половины». Процесс последовательного деления пополам называется дихотомией, вследствие чего описанный метод поиска часто называют дихотомическим.

Текст программы

Program LEC3_5_4; {бинарный поиск}

const n=7;

Type

   diapason=1..n;

   MyArray=array[diapason] of string[20];

const

   m:MyArray=('Abel','Barnes','Bishop','Charles',

              'Chester','Davis','Fisher');

var

   str:string[20];

   low,high,test:diapason;

   found:boolean;

begin

 str:='Chester';

 {инициализация переменных}

 low:=1; high:=n; found:=false;

 {цикл поиска}

 while (not found) and (low <= high) do

 begin

   test:=(low + high) div 2;

   found:= m[test]=str;

   if m[test]>str

   then high:=test-1

   else low:=test+1;

 end; {while}

 if found

 then writeln('Строка '+str+' найдена. №=',test)

 else writeln('Строка '+str+' НЕ найдена!');

 writeln('Нажмите Enter...');   readln;

end.

Анализ алгоритма бинарного поиска

  1.  Для алгоритма бинарного поиска заданный массив должен быть предварительно упорядочен по возрастанию.
  2.  Число проверок для  массива из n элементов равно k=log2(n+1), где   – округление до ближайшего целого.

Число проверок при поиске

n

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

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

элемент
присутствует

элемент
отсутствует

элемент
присутствует

элемент
отсутствует

7

4

7

3

3

100

50

100

7

7

1 000

500

1 000

10

10

1 000 000

500 000

1 000 000

20

20


 

А также другие работы, которые могут Вас заинтересовать

33591. Законы организации 39.5 KB
  Законы организации. Закон внутренняя существенная устойчивая связь явлений обусловливающая их необходимое развитие. Законы носят объективный характер и не зависят от сознания людей. Закон синергии.
33592. Социально-экономические и политические процессы: сущность, классификация, особенности исследования 37 KB
  Социальноэкономические и политические процессы: сущность классификация особенности исследования Социально экономические и политические процессы. Управляемые социальноэкономические процессы. Социальноэкономические и политические процессы это изменения в обществе отображающиеся на его благосостоянии политической и экономической стабильности условиях безопасности и пр. Классификация социальных процессов Процессы функционирования обеспечивает воспроизводство качественного состояния объекта и процессы развития обуславливает...
33593. Методы исследования социально-экономических и политических процессов 52 KB
  Мыслительнологические методы исследования: дедукции индукции анализ методы классификации доказательства полемики и др. Специфические методы исследования. Методы экспертных оценок тестирования.
33594. Социологические исследования социально-экономических и политических процессов 42 KB
  Программа исследования: методологический и процедурный разделы. Социологические исследования обеспечивают сбор информации об изучаемом объекте раскрывают его характерные черты и тенденции развития формулируются выводы и рекомендации которые помогают руководителю в его должности. Теоретикоприкладные исследования цель которых содействие решению социальных проблем путем разработки новых подходов к их изучению интерпретации и объяснению более глубокому и всестороннему чем ранее.
33595. Методы прогнозирования и их роль в социальном управлении 69.5 KB
  Сущность этого метода состоит в актуализации творческого потенциала специалистов при мозговой атаке проблемной ситуации реализующей вначале генерацию идей и последующее деструирование разрушение критику этих идей с формулированием контридей. Третий этап генерация идей. Предсказывая описание метода ведущий концентрирует внимание участников на правилах проведения мозговой атаки: 1 высказывания участников должны быть четкими и сжатыми; 2 скептические замечания и критика предыдущих выступлений не допускаются; 3 каждый из участников...
33596. Социальное проектирование и его роль в управленческой деятельности 70.5 KB
  Социальное проектирование и его роль в управленческой деятельности Сущность социального проектирования. Цели и задачи социального проектирования. Объект субъект и предмет социального проектирования. Принципы социального проектирования.
33597. Инновационные и инвестиционные проекты как основные виды проектной деятельности 92 KB
  Успех инновационного проекта в значительной степени зависит от того насколько удачно формулируется обосновывается и рекламируется в обществе его главная инновационная идея доходчиво объясняющая качество достижения поставленных целей и результатов в количественном и качественном измерении. При разработке непосредственно инвестиционного проекта который опирается на решение задач по обеспечению установленных инвестором конечных целей необходимо согласование в виде бизнесплана по ресурсам времени и исполнителем. В этом случае в роли...
33598. Сущность управленческого консультирования 41 KB
  Управленческое консультирование вид интеллектуальной профессиональной деятельности в процессе которой квалифицированный консультант предоставляет объективные и независимые советы рекомендации консультации в решении экономических и управленческих задач которые способствуют успешному управлению организацией. Консультант выступает в роли эксперта советника разработчика и передает клиенту рекомендации по конкретным изменениям. консультант выступает в роли идеолога тренера инноватора. Проблемноориентированное: стремится ответить на...
33599. Процесс консультирования 73.5 KB
  Диагностика организации. Услугами консультантов пользуются органы государственной власти и местного самоуправления коммерческие и некоммерческие организации. Зарождение управленческого консультирования было вызвано двумя основными причинами: постоянным поиском предпринимателями и руководителями новых средств повышения эффективности и результативности организации; желанием специалистовуправленцев найти коммерческое приложение своим способностям. Консультирование заключается в приспособлении разработанной консультантами эффективной...