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) |