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

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