Сортировка методом половинного деления

Сортировка методом пузырька

Упорядоченные структуры данных.

Ассоциативные массивы

Ассоциативный массив (словарь, карта) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу. Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами. В паре (k,v) значение v называется значением, ассоциированным с ключом k.

Реализация ассоциативного массива рассмотрена в параграфе 3.4.

Другие структуры данных рассмотрены в параграфах 3.4 – 3.6.

В обычном векторе для поиска элемента требуется просмотреть в среднем половину списка, т.е. его сложность O(N). Если объем данных большой и запросы к ним выполняются часто, такая сложность алгоритма неприемлема.

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

(Алгоритм половинного деления)

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

Чтобы данные были расположены упорядоченно, их требуется отсортировать.

Это наиболее простой метод сортировки. Его сложность O(N 2 ). Эффективен, если исходные данные в некоторой мере упорядочены, например, если в отсортированный массив добавляется небольшое количество новых данных.

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:

из массива выбирается некоторый опорный элемент a[i],

запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] – вправо,

теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,

для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.

На входе массив a[0]. a[N] и опорный элемент p, по которому будет производиться разделение.

Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.

Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j]

void quickSortR(T* a, long N) <

// На входе – массив a[], a[N] – его последний элемент.

long i = 0, j = N; // поставить указатели на исходные места

p = a[ N/2]; // центральный элемент

if (i 0 ) quickSortR(a, j);

if ( N > i ) quickSortR(a+i, N-i);

Рис 3.3. Пример реализации быстрой сортировки

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

Каждое разделение требует, очевидно, O(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n 2 ) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге. Вообще говоря, малореальная ситуация.

Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части.

Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9136 – | 7298 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Читайте также:  Что писать в start bat

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Пусть уравнение F(x) = 0 имеет один корень на отрезке [a;b]. Функция F(x) непрерывна на отрезке [a; b].

Метод половинного деления заключается в следующем:

Сначала выбираем начальное приближение, деля отрезок пополам, т.е.

Если F(x)=0, то x является корнем уравнения. Если F(x) 0, то выбираем тот из отрезков, на концах которого функция имеет противоположные знаки. Полученный отрезок снова делим пополам и выполняем действия сначала и т.д.

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

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

1. Написать функцию с умалчиваемыми параметрами в соответствии с вариантом, продемонстрировать различные способы вызова функции:

  • с параметрами заданными явно,
  • с опущенными параметрами
  • часть параметров задана явно, а часть опущена.

2. Написать функцию с переменным числом параметров в соответствии с вариантом, продемонстрировать вызов функции с различным числом параметров.

3. Написать перегруженные функции в соответствии с вариантом. Написать демонстрационную программу для вызова этих функций.

4. Написать шаблон функций вместо перегруженных функций из задания 3. Написать демонстрационную программу для вызова этих функций. списка параметров

5. Решить уравнение указанным в варианте методом. Уравнение передать в функцию как параметр с помощью указателя.

Варианты

№ варианта Функция с умалчиваемыми параметрами Функция с переменным числом параметров Перегруженные функции и шаблон функции Передача функции как параметра другой функции с помощью указателя
Печать фамилии, имени и отчества Минимальный элемент в списке параметров Среднее арифметическое массива Метод итераций Отрезок, содержащий корень: [2;3] Точное значение: 2,2985
Печать фамилии, имени и возраста Максимальный элемент в списке параметров Количество отрицательных элементов в массиве Метод Ньютона Отрезок, содержащий корень: [2;3] Точное значение: 2,2985
Печать фамилии, курса и группы Количество четных элементов в списке параметров Максимальный элемент в массиве Метод половинного деления Отрезок, содержащий корень: [2;3] Точное значение: 2,2985
Печать фамилии, имени и рейтинга Среднее арифметическое элементов в списке параметров Минимальный элемент в массиве Метод итераций 0,25x 3 + x – 1,2502 = 0 Отрезок, содержащий корень: [0;2] Точное значение: 1,0001
Печать фамилии, курса и рейтинга Максимальный из элементов в списке параметров, стоящих на четных местах Сортировка массива методом простого обмена Метод Ньютона 0,25x 3 + x – 1,2502 = 0 Отрезок, содержащий корень: [0;2] Точное значение: 1,0001
Печать фамилии, адреса и возраста Максимальный из элементов в списке параметров, стоящих на нечетных местах Сортировка массива методом простого выбора Метод половинного деления 0,25x 3 + x – 1,2502 = 0 Отрезок, содержащий корень: [0;2] Точное значение: 1,0001
Печать названия экзамена, количества сдающих и среднего балла Минимальный из элементов в списке параметров, стоящих на четных местах Сортировка массива методом простого включения Метод итераций Отрезок, содержащий корень: [0;0,85] Точное значение: 0,2624
Печать названия экзамена, даты экзамена и среднего балла Минимальный из элементов в списке параметров, стоящих на нечетных местах Поиск заданного элемента в массиве Метод Ньютона Отрезок, содержащий корень: [0;0,85] Точное значение: 0,2624
Печать координат точки Среднее арифметическое из элементов в списке параметров, стоящих на четных местах Поиск заданного элемента в отсортированном массиве Метод половинного деления Отрезок, содержащий корень: [0;0,85] Точное значение: 0,2624
Вычисление и печать расстояния от точки с координатами x1,y1 до центра координат Среднее арифметическое из элементов в списке параметров, стоящих на нечетных местах Удаление элемента с заданным номером из динамического массива Метод итераций 0,1x 2 – x ln x = 0 Отрезок, содержащий корень: [1;2] Точное значение: 1,1183
Вычисление и печать расстояния от точки с координатами x1,y1 до точки с координатами x2,y2 Минимальный элемент в списке параметров Удаление элемента с заданным ключом из динамического массива Метод Ньютона 0,1x 2 – x ln x = 0 Отрезок, содержащий корень: [1;2] Точное значение: 1,1183
Печать фамилии, имени и отчества Максимальный элемент в списке параметров Добавление элемента с заданным номером в динамический массив Метод половинного деления 0,1x 2 – x ln x = 0 Отрезок, содержащий корень: [1;2] Точное значение: 1,1183
Печать фамилии, имени и возраста Количество четных элементов в списке параметров Добавление элемента после элемента с заданным номером в динамический массив Метод итераций 3x – 4lnx – 5 = 0 Отрезок, содержащий корень: [2;4] Точное значение: 3,2300
Печать фамилии, курса и группы Среднее арифметическое элементов в списке параметров Номер максимального элемента в массиве Метод Ньютона 3x – 4lnx – 5 = 0 Отрезок, содержащий корень: [2;4] Точное значение: 3,2300
Печать фамилии, имени и рейтинга Максимальный из элементов в списке параметров, стоящих на четных местах Среднее арифметическое массива Метод половинного деления 3x – 4lnx – 5 = 0 Отрезок, содержащий корень: [2;4] Точное значение: 3,2300
Печать фамилии, курса и рейтинга Максимальный из элементов в списке параметров, стоящих на нечетных местах Количество отрицательных элементов в массиве Метод итераций Отрезок, содержащий корень: [0;1] Точное значение: 0,5629
Печать фамилии, адреса и возраста Минимальный из элементов в списке параметров, стоящих на четных местах Добавление элемента с заданным номером в динамический массив Метод Ньютона Отрезок, содержащий корень: [0;1] Точное значение: 0,5629
Печать названия экзамена, количества сдающих и среднего балла Минимальный из элементов в списке параметров, стоящих на нечетных местах Сортировка массива методом простого обмена Метод половинного деления Отрезок, содержащий корень: [0;1] Точное значение: 0,5629
Печать названия экзамена, даты экзамена и среднего балла Среднее арифметическое из элементов в списке параметров, стоящих на четных местах Минимальный элемент в массиве Метод итераций Отрезок, содержащий корень: [0;1] Точное значение: 0,7672
Печать координат точки Среднее арифметическое из элементов в списке параметров, стоящих на нечетных местах Сортировка массива методом простого выбора Метод Ньютона Отрезок, содержащий корень: [0;1] Точное значение: 0,7672
Вычисление и печать расстояния от точки с координатами x1,y1 до центра координат Минимальный элемент в списке параметров Сортировка массива методом простого включения Метод половинного деления Отрезок, содержащий корень: [0;1] Точное значение: 0,7672
Вычисление и печать расстояния от точки с координатами x1,y1 до точки с координатами x2,y2 Максимальный элемент в списке параметров Поиск заданного элемента в массиве Метод итераций e x – e -x -2 = 0 Отрезок, содержащий корень: [0;1] Точное значение: 0,8814
Печать фамилии, имени и отчества Количество четных элементов в списке параметров Поиск заданного элемента в отсортированном массиве Метод Ньютона Метод итераций e x – e -x -2 = 0 Отрезок, содержащий корень: [0;1] Точное значение: 0,8814
Печать фамилии, имени и возраста Среднее арифметическое элементов в списке параметров Удаление элемента с заданным номером из динамического массива Метод половинного деления Метод итераций e x – e -x -2 = 0 Отрезок, содержащий корень: [0;1] Точное значение: 0,8814
Печать фамилии, курса и группы Максимальный из элементов в списке параметров, стоящих на четных местах Удаление элемента с заданным ключом из динамического массива Метод итераций Отрезок, содержащий корень: [1;2] Точное значение: 1,3077
Читайте также:  Lg ffh не включается

Методические указания

1. В функции с умалчиваемыми параметрами использовать структурированный тип данных.

2. При демонстрации вызова функции с умалчиваемыми параметрами учесть, что опускать параметры функции можно только с конца.

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

4. Перегрузить функции для массивов типа char, int, и double.

5. Инстанцировать шаблон функции для типов char, int, и double.

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

7. Точность нахождения корня уравнения выбирается не менее 0.001.

8. Полученный результат вычисления корня сравнить с точным значением, заданным в задании.

Содержание отчета

1. Постановка задачи (общая и для конкретного варианта).

2. Определения функций для реализации поставленных задач.

Фактически мы сейчас сформулировали метод приближенного решения уравнения f(x)=0. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.

Далее ученикам предлагается записать алгоритм и блок-схему нахождения корня уравнения с помощью метода половинного деления.

Алгоритм

2) Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)ּf(a);

3) Если d>0, то теперь точкой a станет c: a=c; Если d ε, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;

Блок- схема

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

Читайте также:  Утюг braun texstyle 3 инструкция

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

В применении информатики к преподаванию других предметов используются в основном две формы работы: привлечение программных средств для контроля знаний учащихся и работа учащихся с обучающими программами. В стороне остаются возможности составления программ самими учащимися для решения тех или иных задач, например, из области физики. Среди методистов распространено мнение, что подобная работа в школе возможна лишь на высоком уровне (в специализированных классах) из-за слабой подготовки учащихся в области программирования. Однако при согласованных действиях преподавателей физики, математики и информатики этот недостаток может быть легко выполнен. В частности успешным оказывается проведение уроков по теме "Движение тела под действием силы тяжести при начальной скорости управления горизонтально или под углом к горизонту", изучаемой в курсе физики 9 класса совместно с учителем информатики. В курсе информатики Учащимся предлагается лабораторная работа "Артиллериская задача". При выполнении данной работы учитель отрабатывает навыки программирования, изучает метод дихотомии (половинного деления). При этом приходится решать задачу физически, т.е. возникают трудности по применению формул физики. Таким образом затмевается главная цель урока по информатике: формирование умений и навыков решения задач методом половинного деления с использованием ЭВМ. Поэтому здесь и необходимо проведение интегрированных уроков по физике и информатике при решении задач. Тем более, что в Сборник задач по физике для 9-11 классов (переизданного в 1992 г.), автором которого является А.П. Рымкевич, включены программируемые задачи, которые для решения требуют знаний по физике и информатике.

1. Гейн А.Г., А.И. Сенокосов, Н.А. Юнерман «Информатика: учебное пособие для 10-11 классов». М.: Просвещение, 2001.

2. Гейн А.Г., В.Г. Житомирский, Е.В. Линецкий, М.В. Сапир, В.Ф. Шолохович «Основы информатики и вычислительной техники». М.: Просвещение, 1992.

3. Симонович С., Г. Евсеев. «Практическая информатика: Учебное пособие для средней школы. Универсальный курс». – М.: Аст-пресс: Инфорком-пресс, 2001.

4. Сеть Internet

Тематическое планирование уроков в 11 классе (68 часов).