Интернет-журнал "Домашняя лаборатория", 2007 №9

long time1, time2;

long f=0;

time1 = getTimeInMilliseconds;

for (int i = 1; i <1000000; i + +)f =han.fact(15);

time2 =getTimeInMilliseconds ;

Console.WriteLine(" f= {0}, " + "Время работы циклической процедуры:

{1}",f,time2 — time1);

time1 = getTimeInMilliseconds ;

for(int i = 1; i <1000000; i + +)f =han.factorial (15);

time2 =getTimeInMilliseconds ;

Console.WriteLine(" f= {0}, " + "Время работы рекурсивной процедуры:

1}",f,time2 — time1);

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

Проводить сравнение эффективности работы различных вариантов — это частый прием, используемый при разработке программ. И я им буду пользоваться неоднократно. Встроенный тип DateTime обеспечивает необходимую поддержку для получения текущего времени. Он совершенно необходим, когда приходится работать с датами. Я не буду подробно описывать его многочисленные статические и динамические методы и свойства. Ограничусь лишь приведением функции, которую я написал для получения текущего времени, измеряемого в миллисекундах. Статический метод Now класса DateTime возвращает объект этого класса, соответствующий дате и времени в момент создания объекта. Многочисленные свойства этого объекта позволяют извлечь требуемые характеристики. Приведу текст функции getTimeInMilliseconds:

long getTimeInMilliseconds

{

DateTime time = DateTime.Now;

return(((time.Hour*60 + time.Minute)*60 + time.Second)*1000

+ time.Millisecond);

}

Результаты измерений времени работы рекурсивного и циклического вариантов функций слегка отличаются от запуска к запуску, но порядок остается одним и тем же. Эти результаты показаны на рис. 10.1.

Рис. 10.1. Сравнение времени работы циклической и рекурсивной функций

Вовсе не обязательно, что рекурсивные методы будут работать медленнее нерекурсивных.

Классическим примером являются методы сортировки. Известно, что время работы нерекурсивной пузырьковой сортировки имеет порядок с*n2, где с — некоторая константа. Для рекурсивной процедуры сортировки слиянием время работы — q*n*log(n), где q — константа. Понятно, что для больших n сортировка слиянием работает быстрее, независимо от соотношения значений констант. Сортировка слиянием — хороший пример применения рекурсивных методов. Она демонстрирует известный прием, называемый "разделяй и властвуй". Его суть в том, что исходная задача разбивается на подзадачи меньшей размерности, допускающие решение тем же алгоритмом. Решения отдельных подзадач затем объединяются, давая решение исходной задачи. В задаче сортировки исходный массив размерности n можно разбить на два массива размерности n/2, для каждого из которых рекурсивно вызывается метод сортировки слиянием. Полученные отсортированные массивы сливаются в единый массив с сохранением упорядоченности.

На примере сортировки слиянием покажем, как можно оценить время работы рекурсивной процедуры. Обозначим через T(n) время работы процедуры на массиве размерности n. Учитывая, что слияние можно выполнить за линейное время, справедливо следующее соотношение:

Т(n) = 2Т(n/2) + сn

Предположим для простоты, что п задается степенью числа 2, то есть n = 2к. Тогда наше соотношение имеет вид:

Т(2k) = 2Т(2k—1) + с2k

Полагая, что T(1) =с, путем несложных преобразований, используя индукцию, можно получить окончательный результат:

T(2k) = с*k*2k = c*n*log(n)

Известно, что это — лучшее по порядку время решения задачи сортировки. Когда исходную задачу удается разделить на подзадачи одинаковой размерности, то, при условии существования линейного алгоритма слияния, рекурсивный алгоритм имеет аналогичный порядок сложности. К сожалению, не всегда удается исходную задачу разбить на к подзадач одинаковой размерности n/k. Часто такое разбиение не представляется возможным.

Рекурсивное решение задачи "Ханойские башни"

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

В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Беспокоиться о близком конце света не стоит. Задача эта не под силу и современным компьютерам. Число ходов в ней равно 2⁶⁴, а это, как известно, большое число, и компьютер, работающий в сотню миллионов раз быстрее монахов, не справится с этой задачей в ближайшие тысячелетия.

Рассмотрим эту задачу в компьютерной постановке. Я спроектировал класс Hanoi, в котором роль пирамид играют три массива, а числа играют роль колец. Вот описание данных этого класса и некоторых его методов:

public class Hanoi

{

int size,moves;

int[] tower1, tower2,tower3;

int top1,top2,top3;

Random rnd = new Random;

public Hanoi(int size)

{

this.size = size;

tower1 = new int [size];

tower2 = new int[size];

tower3 = new int[size];

top1 = size; top2=top3=moves =0;

}

public void Fill

{

for (int i =0; i< size; i + +)

tower1[i]= size — i;

}

}//Hanoi

Массивы tower играют роль ханойских башен, связанные с ними переменные top задают вершину — первую свободную ячейку при перекладывании колец (чисел). Переменная size задает размер массивов (число колец), а переменная moves используется для подсчета числа ходов. Для дальнейших экспериментов нам понадобится генерирование случайных чисел, поэтому в классе определен объект уже известного нам класса Random (см. лекцию 7). Конструктор класса инициализирует поля класса, а метод Fill формирует начальное состояние, задавая для первой пирамиды числа, идущие в порядке убывания к ее вершине (top).

Займемся теперь непосредственно методом, реализующим нашу игру и перекладывающим кольца в соответствии с правилами игры. Заметьте, написать нерекурсивный вариант ханойских башен совсем не просто. Можно, конечно, написать цикл, завершающийся по достижению требуемой конфигурации, на каждом шаге которого выполняется очередной ход. Но даже первый ход не тривиален. Поскольку фиксирована пирамида, где должны быть собраны кольца, то неясно, куда нужно переложить первое кольцо — на вторую или третью пирамиду?