Рекурсия: различия между версиями

Нет изменений в размере ,  11 лет назад
м (вычитка, много правок)
=== Задача 13 ===
 
Известный алгоритм [[w:Быстрая сортировка|быстрой сортировки Хоара]] также основан на рекурсии. Пусть нам нужно отсортировать кусочек массива <math>A</math> от элемента с индексом <math>b</math> по элемент с индексом <math>e</math> включительно. Перераспределим элементы на этом кусочке так, чтобы вначале стояли элементы меньшие либо равные <math>A_b</math>, а потом элементы большие либо равные <math>A_b</math>. Пусть последний элемент в первом кусочке оказался на месте <mahtmath>c</math>. Вызовем рекурсивно сортировку двух кусочков от <math>b</math> до <math>c</math> и от <math>c + 1</math> до <math>e</math> включительно, (если, конечно, эти кусочки состоят более, чем из одного элемента). Воплотите эту идею в работающую процедуру сортировки массива. Проведите эксперименты по оценке средней глубины дерева рекурсии и времени работы алгоритма в зависимости от размера массива. Рассмотрите случаи а) случайного массива, б) массива, упорядоченого по возрастанию, и в) массива, упорядоченного по убыванию.
 
== Задача коммивояжёра ==
Анонимный участник