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


 

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

27375. Мораль. Формирование морали 34 KB
  Ценность человеческой жизни меняется в зависимости от ценности вещей и статуса или других признаков человека. Ценность жизни человека определяется чувствами связанных с ним людей. Ценность человеческой жизни определяется вкладом человека в общий прогресс человечества. Главной проблемой является не следование предписаниям а отыскание смысла жизни.
27376. Профессиональные свойства и характеристики личности учителя 40.5 KB
  Как и любой вид деятельности деятельность педагога имеет свою структуру Зимняя И. Предмет педагогической деятельности. Продукт и результат педагогической деятельности. Каждый вид деятельности имеет свой предмет точно также и педагогическая деятельность имеет свой.
27377. Классный руководитель 27.5 KB
  выполняет следующие функции: 1 знакомится с семьями учащихся для того чтобы знать какое влияние оказывается на них дома и для того чтобы своевременно помочь им если это влияние оказывается неблагоприятным; 2 знакомит родителей с требованиями школы к учащимся по режиму дня приготовлению уроков привлечению учащихся к домашнему труду и др.; 3 стремится обеспечить единство требований школы и семьи; 4 для родителей регулярно устраивает лекции по отдельным вопросам где говорится о средствах и методах которыми семья может помочь школе в...
27378. Общеобразовательные цели обучения математике 19.7 KB
  ФГОС здесь все из книги по фгосам на экзамене будут фгосы доступны так что учить здесь всё не нужно наизусть: В результате изучения курса математики обучающиеся на ступени начального общего образования: научатся использовать начальные математические знания для описания окружающих предметов процессов явлений оценки количественных и пространственных отношений; овладеют основами логического и алгоритмического мышления пространственного воображения и математической речи приобретут необходимые вычислительные навыки; научатся применять...
27379. Этапы формирования представлений о числе 18.8 KB
  5 этап: изучение отрезка ряда натуральных чисел. Так же необходимо в процессе изучения отрезка натуральных чисел отрабатывать прием присчитывания и отсчитывания по одному. Моро А последовательно один за другим рассматриваются отрезки ряда натуральных чисел 12 123 123. Основные приемы: прочтение чисел счет предметов выделение нового для изучаемого числа.
27380. Изучение смысла сложения и вычетания 18.9 KB
  Этот подход легко интерпретируется на уровне предметных действий позволяя тем самым учитывать психологические особенности младших школьников. Например в учебнике М1М в качестве основного средства формирования у детей представлений о смысле действий сложения и вычитания выступают простые текстовые задачи. В основе другого подхода лежит выполнение учащимися предметных действий и их интерпретация в виде графических и символических моделей. Деятельность учащихся сначала сводится к переводу предметных действий на язык математики а затем к...
27381. Действия с величинами 23.83 KB
  Формирование у учащихся представлений о числе и о десятичной системе счисления тесно связано с изучением величин. В начальных классах у учащихся имеются некоторые интуитивные представления о величинах и об их измерении. Измерение заключается в сравнении данной величины с некоторой величиной того же рода принятой за единицу.
27382. ЗУНы для вычисления в пределах 100 (сложение и вычитание) 22.28 KB
  Остальные случаи вычислений над числами большими 100 относятся к письменным вычислениям. Рассмотрим методические особенности формирования умений складывать и вычитать числа в пределах 100 которые нашли отражение в учебниках М1М и М2М Моро. Овладение вычислительными приемами предполагает усвоение: нумерации чисел в пределах 100 разрядного состава двузначного числа табличных случаев сложения вычитания и свойств сложения и вычитания; прибавления числа к сумме вычитания числа из суммы прибавления суммы к числу вычитания...
27383. Алгоритмы: 1. Письменного сложения и вычитания 2. Письменного умножения 3. Письменного деления 20.18 KB
  Письменного деления ЗУНы для сложения и вычитания: Нумерация многозначных чисел Разрядный состав многозначных чисел Десятичный состав числа Навык сложения и вычитания чисел в пределах 20 Знание переместительного и сочетательного закона сложения Как и другие алгоритмы письменного вычисления в и – рассматриваются поэтапно: Актуализация ЗУН подготовка к изучению алгоритма подготовка и изучение алгоритма Введение самого алгоритма Усвоение алгоритма Продуктивное повторение новой темы включать новые знания в систему имеющихся Основная...