Студопедия

КАТЕГОРИИ:

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


ДВОИЧНЫЙ ПОИСК




Двоичный поиск применяют для нахождения элемента X в отсортированном массиве a[1..N].

Основная идея заключается в следующем.

Пусть массив отсортирован в порядке убывания:

1) определяем средний элемент массива a[m], где m = (n+1)/2 ;

2) сравниваем его с Х, и если Х=a[m], то поиск на этом заканчивается;

3) если a[m] < Х, то все элементы от m до n отбрасывают;

4) если a[m] > Х, то отбрасывают элементы от 1 до m;

5) таким образом, каждый раз необходимо пересчитывать левую (L) или правую (R) границы, т.е. изначально L=1, R=n (первый шаг); на втором шаге или L=m или R=m т.е. на втором шаге либо левая, либо правая граница поменяет свое значение и т.д.;

6) поиск продолжается до тех пор, пока элемент не будет найден: a[m]=X, либо пока левая и права границы поиска не совпадут: (L==R), т.е. объект Х в массиве отсутствует.

количество операций сравнения, которые необходимы для нахождения элемента в упорядоченном массиве при помощи алгоритма бинарного поиска K=[log2 N]+1, где квадратные скобки обозначают целую часть числа находящегося в скобках. Алгоритм имеет следующий вид:

flag = «ложь»;

L=0;

R=N-1;

Начало цикла 1: выполнять пока (L ≤ R) и (flag = =«ложь»);

m=(R+L)/2;

если (a[m] = = X)

Тогда

flag = «истина»;

Иначе

если a[m]> X

Тогда

R=m+1;

Иначе

L=m-1;

Все

Все

Конец цикла 1

Если (flag= = true) то

печать сообщения: «Элемент Х найден, его номер - m»,

иначе печать: «Элемента Х нет!»,


Варианты заданий

1. Программа должна сформировать случайным образом одномерный целочисленный массив из N чисел в диапазоне от 0 о 99 (значение N – с клавиатуры). Для этого:

· в начале функции main() нужно вызвать стандартную функцию srand(time(NULL));котораяпри каждом обращении к ней задает новое стартовое значение для генератора случайных чисел rand() использую для этого текущее системное время компьютера ;

· далее в цикле заполнить массив N – случайными значениями: m[i]=rand()%100; (rand() возвращает очередное псевдослучайное число в диапазоне от 0 до RAND_MAX, обе функции декларированы в заголовочном файле stdlib.h, а time() – в time.h).

Теперь программа должна обратиться к функции сортировки sort() передав ей сформированный массив и его размер (предусмотреть подсчет числа перестановок).

Функция sort() после завершения работы возвратит отсортированный массив чисел (алгоритмы сортировки получить у преподавателя).

Рассчитать время работы каждого варианта сортировки и сравнить.

И в заключение вызывается функция бинарного поиска значения Х, вводимого с клавиатуры.

 

№варианта Алгоритмы сортировки
1. а). Простой линейный выбор б) Метод Хоара
2. а). Простой линейный выбор б)Метод Шелла
3. а)Линейный выбор с обменом (сортировка выбором). б) Метод «гномьей» сортировки
4. а)Линейный выбор с обменом (сортировка выбором). б)Метод Шелла
5. а)Стандартный обмен (сортировка обменом, метод "пузырька") б) Метод Хоара
6. а)Стандартный обмен (сортировка обменом, метод "пузырька") б)Метод «гномьей» сортировки
7. а)Стандартный обмен с контролем б) Метод Хоара
8. а)Стандартный обмен с контролем б)Метод Шелла
9. а). Простой линейный выбор б) Метод «гномьей» сортировки
10. а). Простой линейный выбор б)Метод Шелла
11. а)Линейный выбор с обменом (сортировка выбором). б) Метод Хоара
12. а)Линейный выбор с обменом (сортировка выбором). б)Метод «гномьей» сортировки
13. а)Стандартный обмен (сортировка обменом, метод "пузырька") б) Метод Хоара
14. а)Стандартный обмен (сортировка обменом, метод "пузырька") б)Метод Шелла
а)Стандартный обмен с контролем б) Метод «гномьей» сортировки

Контрольные вопросы

 

1. В чем суть метода сортировки обменом и почему его зовут метод «пузырька»?

2. Какие группы алгоритмов сортировки можно выделить?

3. Как работают методы быстрой сортировки?

4. Как оценить скорость алгоритмов сортировки?

5. Что представляет из себя двоичный поиск.

 

ЗАДАНИЕ 5. «ПОЛИЗ»

Цель работы: познакомиться с алгоритмамиработы снелинейными структурами данных


Поделиться:

Дата добавления: 2015-04-04; просмотров: 70; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты