Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Как взобраться на Ханойскую башню???

Автор: Politexnik 13.5.2008, 16:22

Здравствуйте!!!
Встретилась мне в учебнике Дейтелов задача о Ханойских башнях.
Вероятно вы ее знаете.

Задача такая:
Даны три стержня, на один из которых нанизаны четыре кольца, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из четырех колец на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Бился неделю.

Безрезультатно.

И вот решил покопатся в интернете, где и нашел решение с рекурсией.
Оно работает и выглядит так

Код


   void Step(int n, char a, char b, char c)
    // n - количество колец;
    // a, b, c - башни;
    {
         // т. к. на каждом шаге количество колец будет уменьшаться на один,
         // это условие будет условием выхода из рекурсии
         if (n <= 0) return;
         Step(n-1, a, c, b);
         printf("диск %d с %c на %c \n", n, a, b);
         Step(n-1, c, b, a);
    }

Только вот в чем беда. Не могу представить КАК это работает.
ЧТО после чего вызывается.

До этого я сталкивался с рекурсиех только в функциях возвращающох значения, а не в void.

Помогите пожалуйста разобраться.

Заранее благодарен.

Автор: IKM2007 13.5.2008, 19:23

Politexnik,
Здесь в

Код


char a, char b, char c

предрозумевается
a->Старт
b->Финиш
c->Резерв(где на время можно хранить диски)

когда n<=0, выполняется выход из функции(конец рекурсии).

Код


Step(n-1, a, c, b);// верхние n-1 диски перемещает на башню 'c' (Финиш=c).

Код


printf("диск %d с %c на %c \n", n, a, b);// n-ий диск перемещает на Финиш.

Код


Step(n-1, c, b, a);//верхние n-1 диски  перемещает на башню b(Финиш), где уже находится n-ий диск.

Автор: MAKCim 13.5.2008, 19:30

Цитата(Politexnik @ 13.5.2008, 16:22

)

Только вот в чем беда. Не могу представить КАК это работает.
ЧТО после чего вызывается.

возьмите конкретные a, b, c и пошагово пройдитесь по каждой строчке кода
если будет непонятно, задавайте конкретные вопросы

Цитата(Politexnik @ 13.5.2008, 16:22

)

До этого я сталкивался с рекурсиех только в функциях возвращающох значения, а не в void.

нет никакой разницы