Рекурсия. Ханойские башни.

[Dragon]

Рекурсию явно придумал не человек, но от этого явления никуда не уйти.

Не могу понять как сделать рекурсивное решение Ханойских Башен. Решения, что есть в интернете не подходят (хочется самому дойти до понимания вопроса, да и не до конца понятны существующие примеры).

С какой стороны подступиться?

Рассмотрим несколько примеров чтобы попытаться прийти к решению "с конца" (это то, что я расчертил себе на листике дабы попытаться увидеть общие черты, чтобы понять алгоритм):

1 кольцо (n == 1)
| | |
| | |
1 | |
A B C
A -> C

2 кольца (n == 2)
| | |
1 | |
2 | |
A B C

A -> B
A -> C
B -> C

3 кольца (n == 3)
1 | |
2 | |
3 | |
A B C

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

=======

Я пока точно могу сказать, что условием останова рекурсии будет (n == 1). Но только какое действие должно происходить?! При 1 и 3 кольцах последнее кольцо (первое, если решать "с конца") перемещается сразу на третий столбец (A -> C), при 2 кольцах картина как видно другая. Т.е. алгоритм я пока понять не могу.

Объявление функции я вижу следующим:
void hanoi(int n, int first, int mid, int last);
//n - кол-во колец
//first, mid, last - с какого переносим (A), буферный (B) и на какой переносим (C).

Это все наброски, которые я имею, но они не позволяют мне прийти к решению и пониманию как должна здесь работать рекурсия.
Буду признателен за любые наставления, разъяснения.

updated
Небольшое озарение. Делим задачу на более мелкие.
1). Чтобы перенести диск 3 на колышек C, надо перед этим перенести диски 1,2 на колышек B.
2). Чтобы перенести диск 2 на колышек B, надо перенести диск 1 на колышек C
3). Перенос диска 1 на колышек С - это условие останова (n==1).

Следовательно 1) и 2) - это рекурсивные вызовы функции... так-с, в которых окончательно осталось решить что куда и зачем.... пошел рисовать колышки, диски и стрелочки....

[Dragon]

Вобщем написал, после первого запуска подправил 2 параметра и в итоге все работает.

Код: Выделить всё

void hanoi(int n, int f, int l, int m)
{
    if(n == 1)
    {
        cout << f << " -> " << l << endl;
    }
    else if(n > 1)
    {
        hanoi(n-1, f, m, l);
        cout << f << " -> " << l << endl;
        hanoi(n-1, m, l, f);
    }
}

n - кол-во дисков;
f - с какого колышка перемещать
l - на какой перемещать
m - буферный колышек

Все-равно не понимал как ЭТО работает, пока не расписал что делают 3 строки (может кому пригодится):

Код: Выделить всё

  hanoi(n-1, f, m, l);
  cout << f << " -> " << l << endl;
  hanoi(n-1, m, l, f);

- для того, чтобы перенести n-й диск, надо n-1 дисков перенести на средний колышек, используя в качестве буфера последний.
- фиксируем перенос n-го диска на последний колышек
- переносим n-1 дисков со среднего (см. первый пункт) на последний, используя первый колышек, как буфер.

Если бы я не увидел примеры решения данной задачки, то не думаю, что дошел бы до решения. Но даже решив, боюсь что подобную задачу штурмом взять не получится. Отсюда вопрос, как часто используется рекурсия в реальных проектах? Возможно нужно больше практики, больше опыта решения хитроумных задач, чтобы мозг по-другому начал мыслить (хотя читал пару статей, что рекурсивное мышление не совсем хорошее т.к. потом нормально писать код будет сложно, везде захочется всунуть рекурсию, забывая, что это все память, и что пока работает функция, стек забивается и рано или поздно можно не заметить его переполнения ,а это в свою очередь скажется на производительности). И конечно же хотелось бы услышать пару примеров, где стоит рассматривать вариант решения чреез рекурсию (например, тот же сабж, двоичный поиск, небольшую формулу (вычисление небольшого числа Фибоначчи, факториал)).

[Romeo]

Хитроумные задачи в реальных прикладных программах встречаются достаточно редко. Рекурсия используется, но без всяких хитростей. Боюсь, что 95% задач, в которых используется рекурсия - это обход деревьев

[WinMain]

Более правильно (в Visual C++) этот алгоритм реализуется так :

Код: Выделить всё

#include "stdafx.h"
 
void HanoyTown(int nLevel, char from, char to, char mid)
{
 if (nLevel > 0)
 {
  HanoyTown(nLevel-1, from, mid, to);
  _tprintf(_T("%c ==> %c\n"), from, to);
  HanoyTown(nLevel-1, mid, to, from);
 }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
 HanoyTown(3, 'A', 'C', 'B');
 return 0;
}

Алгоритм довольно простой, единственная сложность для начинающих программистов состоит в том, что здесь функция дважды вызывыает сама себя, т.е. как бы двойная рекурсия. А суть в том, что для перестановки самого нижнего кольца с одного стержня на другой, нужно сначала перенести все вышестоящие кольца на промежуточный стержень, а после переноса самого нижнего кольца, расположить поверх него все остальные кольца с промежуточного стержня.
Наиболее часто рекурсия применяется для решения математических задач. Задача про Ханойскую башню - это ещё относительно простой пример.
Если хочешь более подробно узнать про рекурсию, могу порекомендовать книгу "Теория рекурсии для программистов".
Вот как она выглядит...
http://www.bolero.ru/books/9785922107211.html

[Dragon]

Я int'овые типы взял для восприятия столбиков, как 1, 2, 3.

Хм, за книгу спасибо, поищу, почитаю

[ujif]

скачал книгу по ссылке начал с самого начала
и знаете что хочется сказать -вашу же бабушку....умеют же у нас так заплести
что и академику не расплести ...обозначаем это потом переобозначаем то ...