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

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

 

 

Решение:

Мы промоделируем каждую возможную комбинацию из 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).