Студопедия — Алгоритмы поиска
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






6.1. Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=< К1, К2, К3,..., Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация, когда V содержит один элемент, а в В имеется не более одного такого элемента.

Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi – относительная частота использования элемента Кi в В, а Si – количество сравнений, необходимое для его поиска, то

n Max{А} = max{ Si, i=1, n }; Avg{А} = Pi Si. i=1

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

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, поместив часто встречаемые элементы в начало списка.

 

Пример 15.7

Пусть во входном потоке задано 5 целых чисел К1, К2,... К5 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:

#include < stdio.h>

void main(void)

{

int k[5], v, i, count=0;

puts(“Vvedite elementi: ”);

for (i=0; i< 5; i++)

scanf(“%d”, & k[i]);

puts(“vvedite element dlja poiska”);

scanf(“%d”, & v);

i=0;

while(i< 5)

{ if (k[i]==v)

{

printf(“element-%d position-%d\n”, v, (i+1));

count++;

}

i++;

}

if(count==0) printf(“element-%d ne naiden “, v);

}

6.2. Поиск элемента по индексу

Пример 15.8

#include < stdio.h>

void main(void)

{ int k[5], v, i, count=0;

puts(" Vvedite elementi: ");

for (i=0; i< 5; i++)

scanf(" %d", & k[i]);

puts(" vvedite element dlja poiska");

scanf(" %d", & v);

i=0;

while(i< 5)

{

if (k[i]==v)

{

printf(" element-%d position-%d\n", v, (i+1));

count++;

}

i++;

}

if(count==0) printf(" element-%d ne naiden ", v);

puts(" Vvedite index elementa");

scanf(" %d", & v);

if(v> =0& & v< 5)

printf(" element s indexom %d raven = %d\n", v, k[v]);

else printf(" Elementa s takim indexom net\n");

}

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

Линейный поиск - это самый простой тип поиска, потому что при его выполнении просто просматривается множество элементов данных и эти элементы сравниваются с искомыми данными, пока не обнаружится совпадение. Линейный поиск прост в реализации, но не всегда эффективен.

 

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

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

Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

 

Пример 15.9

#include < stdio.h>

void main()

{

int k[6];

int v, i, j, m;

for (i=0; i< 6; i++)

scanf(" %d", & k[i]);

scanf(" %d", & v);

i=0;

j=6;

m=3;

while (k[m]! =v)

{

if (k[m] < v)

i+=m;

else j=m-i;

m=(i+j)/2;

}

printf(" %d %d", v, m);

}

 

Варианты индивидуальных заданий

Разработать программу для создания пяти динамических массивов: a[ ], b[ ], c[ ], d[ ] и e[ ]. Эти массивы необходимо отсортировать соответственно методом обмена, методом выбора, методом вставки, методом Шелла и методом Хоора. Организовать последовательный поиск определенного элемента в каждом исходном массиве и подсчитать количество совпадений этого элемента в каждом массиве. Организовать бинарный поиск определенного элемента в каждом отсортированном массиве. Разработать в программе меню, структура которого следующая:

Menu:

1. Initilization arrays (инициализация массивов)

2. Result of bubble sort

3. Result of min sort

4. Result of insert sort

5. Result of Shell sort

6. Result of Hoor sort

7. Poisk

7.1. Posledovatel’nyi poisk

7.2. Binarnyi poik

Результаты всех сортировок и поиска записать в файл.







Дата добавления: 2014-11-10; просмотров: 766. Нарушение авторских прав; Мы поможем в написании вашей работы!



Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Дренирование желчных протоков Показаниями к дренированию желчных протоков являются декомпрессия на фоне внутрипротоковой гипертензии, интраоперационная холангиография, контроль за динамикой восстановления пассажа желчи в 12-перстную кишку...

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Понятие о синдроме нарушения бронхиальной проходимости и его клинические проявления Синдром нарушения бронхиальной проходимости (бронхообструктивный синдром) – это патологическое состояние...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Постинъекционные осложнения, оказать необходимую помощь пациенту I.ОСЛОЖНЕНИЕ: Инфильтрат (уплотнение). II.ПРИЗНАКИ ОСЛОЖНЕНИЯ: Уплотнение...

Приготовление дезинфицирующего рабочего раствора хлорамина Задача: рассчитать необходимое количество порошка хлорамина для приготовления 5-ти литров 3% раствора...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия