VPF::Как взобраться на Ханойскую башню???

Politexnik

Дата 13.5.2008, 16:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 14
Регистрация: 1.3.2008
Где: Ереван, Армения

Репутация: нет
Всего: нет

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

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

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

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

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

Код


   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 (ссылка)

(нет голосов)

Загрузка ...

Зима близко

Профиль
Группа: Участник
Сообщений: 702
Регистрация: 26.4.2008
Где: olmedreca

Репутация: 3
Всего: 40

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 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 2
Всего: 207

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

)

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

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

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

)

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

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

--------------------

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »