9796

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

Реферат

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

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

Русский

2013-03-17

48.5 KB

13 чел.

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

Постановка задачи: Задан массив содержащий 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


 

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

48184. Основы системного использования ЭВМ. Работа с системой MathCAD 581.5 KB
  Работа с системой MthCD Пекунов В. В настоящее время существуют универсальные математические пакеты например MthCD MtLB Mthemtic позволяющие оперативно решать такие задачи. При этом система MthCD выгодно отличается простотой освоения возможностями ввода и редактирования формул в естественной для человека форме имеет достаточную мощность для большинства инженерных расчетов. Курс содержит сведения позволяющие освоить основные возможности системы MthCD: решение систем линейных и нелинейных уравнений; работу с последовательностями;...
48185. ФИНАНСОВЫЙ МЕНЕДЖМЕНТ 187.5 KB
  Итого внеоборотных активов 100 100 Доля в общих активах 007 014 Структура оборотных активов Незавершенное производство 1162 6 авансы поставщикам 48 18 производственные запасы и МБП 208 142 готовая продукция и товары 206 525 дебиторская задолженность счета к получению 108 85 Денежные средства 172 4 прочие текущие активы 14 13 ===Итого оборотных активов 100 100 Доля в общих активах 9993 9986 Структура инвестированного капитала Уставный капитал 043 01 Накопленный капитал 9957 999 Долгосрочные...
48186. Регіональна геологія. Конспект лекцій 4.83 MB
  Використовуючи історико-геологічний принцип в структурі континентальної літосфери виділяються області давніх докембрійських і молодих епігерцинських платформ байкальські каледонські герцинські складчасті споруди мезозойські параплатформи тобто області близькі до платформ кайнозойські складчасті споруди сучасні геосинкліналі області епіплатформового орогенезу тощо. Сюди відносяться Східноєвропейська Сибірська Індостанська Китайська платформи Євроазіатського континенту АфриканоАравійська Австралійська Північноамериканська та...
48187. Регионализация международных отношений 100 KB
  Современный мир не ограничивается реальным географическим пространством он стал многомерным. Политологи делают упор на распространение демократических институтов. Формирование единого мирового пространства на принципах европейского Просвещения оказалось в качестве основной приманки для бездумной советской интеллигенции сыгравшей роль разрушителя отечественного социокультурного пространства. В реальной действительности процесс глобализации идет по пути интернационализации элит формирования мирового клуба избранных преимущественно из...
48190. ІСТОРІЯ СЕРЕДНЬОВІЧНОГО СХОДУ КУРС ЛЕКЦІЙ 2.42 MB
  ІНДІЯ ПІСЛЯ ІСЛАМСЬКОГО ЗАВОЮВАННЯ. Встановивши східну деспотію в СРСР вожді від âдиктатури пролетаріатуâ не бажали залишати в умах підданих зайвих асоціацій і хоча після смерті Й. Інші річки Хуайхе Чжуцзян Хайхе Ляохе теж відігравали певну роль у природногосподарській системі традиційного Китаю а після завершення будівництва Великого каналу VII ст. Для тогочасних китайців було характерним міняти особисте ім'я людини протягом життя: в дитинстві всім давалося âмолочне ім'яâ жумін після повноліття основне мін нарешті...
48191. ПРОБЛЕМЫ ТЕОРИИ ПРАВА. КУРС ЛЕКЦИЙ 2.87 MB
  Кожевников ПРОБЛЕМЫ ТЕОРИИ ПРАВА КУРС ЛЕКЦИЙ Второе издание переработанное и дополненное Нижний Новгород 2008 УДК 340 ББК 67. Проблемы теории права: Курс лекций: Право: понятие сущность система; правотворчество и правовое регулирование. Нормы права правоотношения правосознание и правовая культура действие права. Вопервых на основе обобщения материала последних лет по правоведению и сохранения всего ценного накопленного в прошлые годы доступно изложить достаточно сложные и объемные вопросы относящиеся к природе права его...
48192. Джерела з історії середньовічної Європи (V-XV ст.) 145.5 KB
  На території власне германських областей панували місцеві діалекти зокрема законодавчі документи перекладалися цими діалектами. В Англії латина була мовою церкви документи та історичні твори писалися місцевою мовою. Поодинокі документи збереглися лише через те що знаходилися за межами імперії. Це варварські правди для раннього середньовіччя потім королівське законодавство правові документи феодального звичаєвого права парламентське законодавство.