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

вызывается метод сортировки слиянием. Полученные отсортированные массивы сливаются в единый массив с сохранением упорядоченности.

На примере сортировки слиянием покажем, как можно оценить время работы рекурсивной процедуры. Обозначим через 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 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

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

Рассмотрим эту задачу в компьютерной постановке. Я спроектировал класс 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).

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

Рекурсивный вариант решения задачи прозрачен, хотя и напоминает некоторый род фокуса, что характерно для рекурсивного стиля мышления. Базис рекурсии прост. Для перекладывания одного кольца задумываться о решении не нужно — оно делается в один ход. Если есть базисное решение, то оставшаяся часть также очевидна. Нужно применить рекурсивно алгоритм, переложив n-1 кольцо с первой пирамиды на третью пирамиду. Затем сделать очевидный ход, переложив последнее самое большое кольцо с первой пирамиды на вторую. Затем снова применить рекурсию, переложив n-1 кольцо с третьей пирамиды на вторую пирамиду. Задача решена. Столь же проста ее запись на языке программирования:

public void HanoiTowers()

{

    НТ(ref tower1,ref tower2, ref tower3,

         ref top1, ref top2, ref top3,size);

    Console.WriteLine("nBcero ходов 2^n -1 = {0}",moves);

}

Как обычно в таких случаях, вначале пишется нерекурсивная процедура, вызывающая рекурсивный вариант с аргументами. В качестве фактических аргументов процедуре HT передаются поля класса, обновляемые в процессе многочисленных рекурсивных вызовов и потому снабженные ключевым словом ref. Рекурсивный вариант реализует описанную выше идею алгоритма:

/// <summary>

/// Перенос count колец с tower1 на tower2, соблюдая

/// правила и используя tower3. Свободные вершины

/// башен — top1, top2, top3

/// </summary>

void HT (ref int[] t1, ref int[] t2,ref int [] t3,

     ref int top1,ref int top2, ref int top3, int count)

{

    if (count == 1)Move(ref t1,ref t2,ref top1,ref top2);

    else

    {

        HT(ref t1,ref t3,ref t2,ref top1, ref top3, ref top2,count-1);

        Move(ref t1,ref t2,ref top1, ref top2);

        HT (ref t3,ref t2,ref t1,ref top3,ref top2, ref top1,count-1);

    }

}//HT

Процедура Move описывает очередной ход. Ее аргументы однозначно задают, с какой и на какую пирамиду нужно перенести кольцо. Никаких сложностей в ее реализации нет:

void Move(ref int[]t1, ref int [] t2, ref int top1, ref int top2)

{

    t2[top2] = t1[top1-1];

    top1--; top2++; moves++;

    //PrintTowers();

}//Move

Метод PrintTowers позволяет проследить за ходом переноса. Приведу еще метод класса Testing, тестирующий работу по переносу колец:

public void TestHanoiTowers ()

{

    Hanoi han = new Hanoi (10);

    Console.WriteLine("Ханойские башни");

    han.Fill();

    han.PrintTowers ();

    han.HanoiTowers();

    han.PrintTowers();

}

На рис. 10.2 показаны результаты работы с включенной печатью каждого хода для случая переноса трех колец.

Рис. 10.2. "Ханойские башни"

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