26 Билет

Пирамидальная сортировка Идея бинарного выбора может быть эффективно применена, если организовать входные данные в виде так называемой пирамиды (или сбалансированного бинарного дерева поиска) и поддерживать их в этом виде в процессе сортировки. Метод сортировки с использованием такой пирамиды был предложен Р. У. Флойдом в 1964 г. под названием «Heap sort» — пирамидальной сортировки или сортировки кучей.

Свойство пирамиды: Пусть дана последовательность h₁, ..., h_n. Элемент h_i образует пирамиду в этой последовательности, если выполнены следующие условия:1.если 2 × i ≤ n, то h_i ≥ h_2i и h_2i образует пирамиду; 2.если 2 × i + 1 ≤ n, то h_i ≥ h_2i+1 и h_2i+1 образует пирамиду. Элементы h_n/2+1, ..., h_n всегда образуют тривиальные пирамиды, поскольку для них приведенные условия имеют ложные посылки. Если элемент h₁ образует пирамиду, то и каждый элемент последовательности образует пирамиду. В этом случае будем говорить, что вся последовательность является полной пирамидой.

Идея метода пирамидальной сортировки: 1.Подготовка к сортировке: входная неупорядоченная последовательность перестраивается в пирамиду. 2.Сортировка: входная и готовая последовательности хранятся в одном массиве, причем готовая последовательность формируется в хвосте массива, а входная остается в начале массива.

Основой реализации метода является следующая процедура просеивания. Пусть в последовательности h₁, ..., h_n элементы h_i+1, ..., h_n уже образуют пирамиды. Требуется перестроить последовательность так, чтобы пирамиду образовывал элемент h_i. На каждой итерации цикла наибольший из трех элементов h_i, h_2×i и h_2×i+1 путем обмена оказывается в корне текущего поддерева, что обеспечивает истинность условий пирамиды в этом корне. Если при этом изменяется корень левого или правого поддерева, то просеивание продолжается для него.

Сортировка включением:

Разделим условно все элементы массива на две последовательности: входную a_i, ... , а_N и готовую последовательность a₁, ... , а_i-1 элементы которой уже отсортированы.

В алгоритмах, основанных на методе включения, на каждом i-м шаге i-й элемент входной последовательности вставляется в подходящее место готовой последовательности .Сортировка простыми включениями наиболее очевидна. Пусть 2 < i < N, a₁, ... , а_i-1 уже отсортированы: a₁ £ а₂ £ ... £ a_i-1. Будем сравнивать по очереди а_i с a_i-1, а_i-2, ... до тех пор, пока не обнаружим, что элемент а_i следует вставить между a_j и a_j+1 (0 £ j £ i - 1) элементами. После этого или в процессе поиска подвинем записи a_j+1, ..., a_i-1 на одно место вправо и переместим запись а_i в позицию j + 1.

28 Билет

Если некоторая процедура P содержит явную ссылку на саму себя, то ее называют прямо рекурсивной. Если же P ссылается на другую процедуру Q, содержащую (прямую или косвенную )ссылку на P, то P называют косвенно рекурсивной. Задача особенно удобна для рекурсивного анализа, если она может быть разложена на совокупность подзадач меньшей размерности.

С использованием рекурсивной функции вычисления факториала. Биномиальные коэффициенты также можно вычислить по следующей формуле (число сочетаний из n по k):

г де выражение n! (n-факториал) обозначает произведение всех натуральных чисел от 1 до n. Исходя из соотношений: 0! = 1, n!= n*(n − 1)! (n > 0) можно написать рекурсивную функцию вычисления факториала, а затем использовать ее для вычисления биномиальных коэффициентов по приведенной выше формуле.