Программирование с отходом назад

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

Решение:

Мы промоделируем каждую возможную комбинацию из N ( 0 и 1 на i-м месте)

1, если вкл. и 0, если выкл.

Моделируем с помощью второго дерева.

Рекурсия

В математике и программировании это метод определения или выражения функции или процедуры для решения задачи посредством той же функции или процедуры.

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

Для вычисления нужно произвести рекурсивное обращение и вычислить , сделать N- рекурсивных обращений.

Принято говорить, что глубина рекурсии, требуемая для вычисления , равна N.

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

Глубина рекурсии ряда Фибоначчи равна (N-3)

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

Пример: функция Аккермана.

Массив:

int a [10] char char a [10] [10]

Алгоритмы машины и математики

Не существует алгоритма сортировки, который был бы.

Эффективность зависит от:

1) какое число сортируемых элементов

2) все ли они могут быть помещены доступную оперативную память

3) до какой степени они отсортированы

4) какой диапазон сортируемых элементов

5) какова длина, сложность и требования к памяти алгоритма сортировки

6) предполагается ли добавление или исключение

Сортировка

Сортировка стала важным предметом вычислительной математики в основном потому, что она отнимает значительную часть времени работы ЭВМ. Осознание того, что 25% всего времени вычислений расходуется на сортировку данных , придает особое значение эффективным алгоритмам сортировки.

К сожалению ,нет алгоритма сортировки, который был бы наилучшим в любом случае. Трудно даже решить, какой алгоритм будет лучшим в данной ситуации, так как эффективность алгоритма сортировки может зависеть от множества факторов, например от того ,(1) каково число сортируемых элементов; (2) все ли элементы могут быть помещены в доступную оперативную память;(3) до какой степени элементы уже отсортированы; (4) каковы диапазон и распределение значений сортируемых элементов ; (5) записаны ли элементы на диске, магнитной ленте или перфокартах; (6) каковы длина , сложность и требования к памяти алгоритма сортировки ; (7) предполагается ли , что элементы будут периодически исключаться или добавляться ;(8) можно ли элементы сравнивать параллельно.

Очевидно, что с отсортированными данными работать легче , чем с произвольно расположенными. Когда элементы отсортированы, их проще найти (как в телефонном справочнике), обновить , исключить, включить и слить воедино. На отсортированных данных легче определить, имеются ли пропущенные элементы (как в колоде игральных карт) , и удостовериться , что все элементы были проверены. Легче также найти общие элементы двух множеств , если они оба отсортированы. Сортировка применяется при трансляции программ , когда составляются таблицы символов ; она также является важным средством для ускорения работы практически любого алгоритма , в котором часто нужно обращаться к определенным элементам.

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

В этом разделе мы рассматриваем два из наиболее эффективных алгоритмов сортировки , быстрой сортировки и сортировки пирамидой (QUICKSORT и HEAPSORT) , и устанавливаем теоретически неулучшаемые границы для всех алгоритмов сортировки с помощью сравнений. В других разделах обсуждаются еще два алгоритма сортировки : сортировка простыми включениями (SIS) и параллельная сортировка (PARSORT).