в таких случаях, вначале пишется
Как обычно в таких случаях, вначале пишется нерекурсивная процедура, вызывающая рекурсивный вариант с аргументами. В качестве фактических аргументов процедуре 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*log(n), то теперь она становится экспоненциальной. Давайте проведем анализ временных затрат для ханойских башен (и всех задач, сводящихся к решению двух подзадач размерности n-1). Подсчитаем требуемое число ходов T(n). С учетом структуры решения:
T(n) = 2T(n-1) +1
Простое доказательство по индукции дает:
T(n) = 2n-1 + 2n-2 + ... + 2 +1 = 2n -1
Можно показать, что последовательность ходов, реализуемая рекурсивным алгоритмом, является оптимальной, так что никакой другой алгоритм не может решить задачу за меньшее число ходов.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий