Контрольные вопросы
Дайте геометрическую интерпретацию методов прямоугольников: средних, трапеций, Симпсона.
Дайте геометрическую интерпретацию метода трапеций.
Дайте геометрическую интерпретацию метода Симпсона.
Какой порядок погрешности имеют эти методы?
Суть алгоритма вычисления интеграла с автоматическим выбором шага интегрирования.
Индивидуальные задания
ЗАДАНИЕ 4. Сортировка данных и поиск
Цель работы: познакомиться с алгоритмами сортировки данных на примере одномерных целочисленных массивов а также с организацией быстрого поиска заданных элементов в отсортированных данных .
Краткие теоретические сведения
Сортировка (упорядочение) - это процесс перегруппировки (перераспределения) заданного множества объектов в некотором определенном порядке. Основная цель сортировки - облегчить поиск заданных элементов в таком упорядоченном множестве.
Если каждый следующий элемент упорядоченного множества данных меньше предыдущего, и последнее значение – наименьшее из чисел массива, то такой порядок расположения чисел называют убывающим.
Если же каждый следующий элемент больше предыдущего, и последнее значение – наибольшее из чисел массива, то такой порядок расположения чисел называют возрастающим.
Обычно сортировку подразделяют на два класса: внутреннюю, когда все объекты хранятся в оперативной памяти, и внешнюю, когда они там все не помещаются. Мы рассмотрим только внутреннюю сортировку.
Существующие методы сортировки обычно разбивают на три класса, в зависимости от лежащего в их основе алгоритма:
а) сортировка выбором;
б) сортировка обменами;
в) сортировка включениями (вставками).
Рассмотрим основные алгоритмы сортировки на примере целочисленного массива.
Алгоритмы сортировки выбором Простой линейный выбор
Метод предполагает использование рабочего (дополнительного) массива, в который в конечном итоге помещается отсортированный массив. Количество просмотров определяется количеством элементов массива. Сортировка посредством простого линейного выбора сводится к следующему:
1. Найти наименьший (наибольший) элемент, переслать его в рабочий массив и заменить его в исходном массиве величиной, которая больше (меньше) любого реального элемента.
2. Повторить шаг 1. На этот раз будет выбран наименьший (наибольший) из оставшихся элементов.
3. Повторять шаг 1 до тех пор, пока не будут выбраны все N элементов.
Линейный выбор с обменом (сортировка выбором).
Рабочий массив здесь не используется.
Этот метод сортировки основан на следующих принципах:
Например, нужно отсортировать массив по убыванию
Выбирается максимальный элемент.
Он меняется местами с первым элементом a[1]. На первом месте оказывается максимальный элемент.
Дальше рассматривается только не отсортированная часть массива, и этот процесс повторяется с оставшимися N-1, N-2 элементами и т. д. до тех пор, пока не останется один, наименьший элемент.
Алгоритм метода будет следующим:
Начало
цикла 1 (выполнять для i
от 0 до N-1)
k=i;
max=a[i];
Начало цикла 2 (выполнять для j от i+1 до N-1)
если a[j] >max
тогда
max=a[j];
k=j;
все
конец цикла 2
a[k]=a[i];
a[i]=max;
конец цикла 1