Интернет-журнал "Домашняя лаборатория", 2007 №9
Шрифт:
Рекурсивный вариант решения задачи прозрачен, хотя и напоминает некоторый род фокуса, что характерно для рекурсивного стиля мышления. Базис рекурсии прост. Для перекладывания одного кольца задумываться о решении не нужно — оно делается в один ход. Если есть базисное решение, то оставшаяся часть также очевидна. Нужно применить рекурсивно алгоритм, переложив 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. "Ханойские башни"
В рекурсивном варианте исчезли все трудности, связанные с выбором хода и соблюдением правил. Выбор выполняется почти автоматически, поскольку слияние частных решений не нарушает правил. В этом еще одна мощь рекурсии.
Решение исходной задачи свелось к решению двух подзадач и одному ходу. В отличие от задачи сортировки слиянием, обе подзадачи имеют не половинный размер, а размер, лишь на единицу меньший исходного. Это, казалось бы, незначительное изменение приводит к серьезным потерям эффективности вычислений. Если сложность в первом случае имела порядок n*iog(n), то теперь она становится экспоненциальной. Давайте проведем анализ временных затрат для ханойских башен (и всех задач, сводящихся к решению двух подзадач размерности n-1). Подсчитаем требуемое число ходов T(n). с учетом структуры решения:
T(n) = 2Т(n-1) +1
Простое доказательство по индукции дает:
T(n) = 2n-1 + 2n-2 +… + 2 +1 = 2n -1
Можно
показать, что последовательность ходов, реализуемая рекурсивным алгоритмом, является оптимальной, так что никакой другой алгоритм не может решить задачу за меньшее число ходов.Быстрая сортировка Хоара
Продолжая тему рекурсии, познакомимся с реализацией на C# еще одного известного рекурсивного алгоритма, применяемого при сортировке массивов. Описанный ранее рекурсивный алгоритм сортировки слиянием имеет один существенный недостаток — для слияния двух упорядоченных массивов за линейное время необходима дополнительная память. Разработанный Ч. Хоаром метод сортировки, получивший название быстрого метода сортировки — Quicksort, не требует дополнительной памяти.
Хотя этот метод и не является самым быстрым во всех случаях, но на практике он обеспечивает хорошие результаты. Нужно отметить, что именно этот метод сортировки встроен в класс System.Array.
Идея алгоритма быстрой сортировки состоит в том, чтобы выбрать в исходном массиве некоторый элемент M, затем в начальной части массива собрать все элементы, меньшие M. Так появляются две подзадачи размерности — k и n-k, к которым рекурсивно применяется алгоритм. Если в качестве элемента M выбирать медиану сортируемой части массива, то обе подзадачи имели бы одинаковый размер и алгоритм быстрой сортировки был бы оптимальным по времени работы. Но расчет медианы требует своих затрат времени и усложняет алгоритм. Поэтому обычно элемент M выбирается случайным образом. В этом случае быстрая сортировка оптимальна лишь в среднем, а для плохих вариантов (когда в качестве M всякий раз выбирается минимальный элемент) имеет порядок n2.
Несмотря на простоту идеи, алгоритм сложен в своей реализации, поскольку весь построен на циклах и операторах выбора. Я проводил построение алгоритма параллельно с обоснованием его корректности, введя инварианты соответствующих циклов. Текст обоснования встроен в текст метода. Приведу его, а затем дам некоторые объяснения. Вначале, как обычно, приведу нерекурсивную процедуру, вызывающую рекурсивный метод:
/// <summary>
/// Вызывает рекурсивную процедуру QSort,
/// передавая ей границы сортируемого массива.
/// Сортируемый массив tower1 задается
/// соответствующим полем класса, public void Quicksort
{
QSort(0,size-1);
}
Вот чистый текст рекурсивной процедуры быстрой сортировки Хоара:
void QSort(int start, int finish)
{
if (start!= finish)
{
int ind = rnd.Next(start,finish);
int item = tower1[ind];
int ind1 = start, ind2 = finish;
int temp;
while (ind1 <=ind2)
{
while((ind1 <=ind2)&& (tower1[ind1] < item)) ind1++;
while ((ind1 <=ind2)&&(tower1[ind2] >= item)) ind2--;
if (ind1 < ind2)
{
temp = tower1[ind1]; tower1[ind1] = tower1[ind2];
tower1[ind2] = temp; ind1++; ind2--;
}
}
if (ind1 == start)
{
temp = tower1[start]; towerl[start] = item;
tower1[ind] = temp;
QSort(start+1,finish);
}
else
{
QSort(start,ind1-1);
QSort(ind2+1, finish);
}
}
}//QuckSort