Напишите функцию Min, возвращающую значение наименьшего элемента вектора.

Настало время обратиться к механизму ускоренного поиска элемента вектора по значению, - ускоренного в сравнении с последовательным просмотром. Он известен под именами метод дихотомии или метод половинного деления. Как обычно, за скорость взимается плата: массив

Рассмотрим упражнения на ускоренный поиск элементов

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

Существует несколько способов выбрать такой элемент и организовать переключение между левым и правым индексами, участвующими в процедуре просмотра подмассива и организации обменов. Вот один из них:

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

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

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

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

Важнейшим моментом при решении задачи является способ сведения задачи к подзадачам. Но не менее важным вопросом является и способ построения решения исходной задачи из решений подзадач. Одним из наиболее эффективных способов построения решения исходной задачи является использование таблиц для запоминания решений подзадач. Такой метод решения задач называется методом динамического программирования.

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

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

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

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

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

Двое играют в следующую игру: начиная с некоторой даты (день, месяц) они по очереди называют следующую, причем можно увеличивать либо номер дня, либо номер месяца (одновременное изменение номеров дня и месяца не разрешается). Проигравшим считается тот, кто называет дату 31.12. Какие даты должен выбирать первый игрок, чтобы выиграть?

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

Между двумя городами расстояние равно 50 километров, причем через каждый километр имеется остановка.

Затем необходимо создать пустую очередь, выполнив операцию init. Параметрами этой процедуры являются имя массива, моделирующего очередь, и связанные с ним указатели очереди.

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

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

Основным свойством структуры данных КУЧА является условие, что элементы в ней организованы таким образом, что приоритет вершины не ниже приоритета каждого из ее "сыновей".

При выполнении операции добавления элемента со значением 17, элемент должен поместиться на свободное место, т.е. позицию с индексом Num+1. Однако эта позиция может не соответствовать правильному положению элемента в куче, так как над ним может находиться элемент, имеющий меньший приоритет.

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

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

Мы стали различать статические и динамические структуры, но основное внимание уделили первым. Сейчас мы переходим к динамическим структурам. Напомним, что основное их отличие от статических в возможности менять в ходе работы количество содержащихся в структуре элементов.