Форум программистов, компьютерный форум CyberForum.ru

Пояснение рекурсии в Ханойских башнях - C++

Восстановить пароль Регистрация
 
renu
0 / 0 / 0
Регистрация: 24.12.2013
Сообщений: 2
26.12.2013, 08:20     Пояснение рекурсии в Ханойских башнях #1
Ребята, нашел рекурсивное решение про задачу с Ханойскими башнями, но хоть убейте не могу понять (найти):
Почему получаются такие значения.
Если про первые четыре более-менее понятно, то как получились обратные 2 --> 1 2 --> 3 не понимаю
Не судите строго, поясните пож-та.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream.h>
#include <iomanip.h>
 
void Towers (int, int, int, int);
 
int main(){
 
int quality = 3, one = 1, two = 2, three = 3;
 
Towers (quality, one, three, two);
 
return 0;
}
 
void Towers (int number, int fst, int thr, int snd)
{
      if (number != 0)
      {
        Towers (number-1, fst, snd, thr); 
        cout << fst << " --> " << thr << endl;
        Towers (number-1, snd, thr, fst);
      }
}
Результат:
1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2013, 08:20     Пояснение рекурсии в Ханойских башнях
Посмотрите здесь:

C++ Что делает функция length?
Граммотное пояснение. C++
Пояснение к коду C++
C++ Пояснение функции
C++ Пояснение к функциям
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Людвиг Бодмер
 Аватар для Людвиг Бодмер
212 / 209 / 70
Регистрация: 29.03.2013
Сообщений: 555
Завершенные тесты: 2
26.12.2013, 10:46     Пояснение рекурсии в Ханойских башнях #2
renu, а вы с какой средой разработки работаете? В Visual Studio под отладчиком пошагово можно пройти и посмотреть как меняются переменные. Вот например, если про первые 4 результата понятно то вот в картинках момент между выводом четвертого и пятого результатов(внизу окно "Локальные переменные"):
Миниатюры
Пояснение рекурсии в Ханойских башнях   Пояснение рекурсии в Ханойских башнях   Пояснение рекурсии в Ханойских башнях  

Пояснение рекурсии в Ханойских башнях   Пояснение рекурсии в Ханойских башнях   Пояснение рекурсии в Ханойских башнях  

Пояснение рекурсии в Ханойских башнях   Пояснение рекурсии в Ханойских башнях  
renu
0 / 0 / 0
Регистрация: 24.12.2013
Сообщений: 2
26.12.2013, 19:03  [ТС]     Пояснение рекурсии в Ханойских башнях #3
Спасибо!
Но меня картинки еще больше запутали, если честно.

Как я вижу, что

Первоначально задаются числа 1-3-2 и потом они присваиваются переменным fst, snd, thr в заданной последовательности и выводится результат fst --> thr

при n = 3
Towers (int number, int fst, int thr, int snd) fst = 1, thr = 3,
при n = 2
Towers (number-1, fst, snd, thr) fst = 1, thr = 2 (такой картинки у Вас нет)
Towers (number-1, snd, thr, fst) fst = 2, thr = 3
при n = 1
Towers (int number, int fst, int thr, int snd) fst = 1, thr = 3,

А как получились в обратную сторону?
fst = 2 --> thr = 1
fst = 3 --> thr = 2
Людвиг Бодмер
 Аватар для Людвиг Бодмер
212 / 209 / 70
Регистрация: 29.03.2013
Сообщений: 555
Завершенные тесты: 2
27.12.2013, 10:36     Пояснение рекурсии в Ханойских башнях #4
renu, у вас напутано даже про первые четыре действия. У меня на картинках показан не весь процесс, а только один этап между выводом 1-->3 и 2-->1. Возможно лучше будет объяснить по-другому, представьте эти башни со снимающимися кольцами, вот так будет это выглядеть:
Миниатюры
Пояснение рекурсии в Ханойских башнях  
Yandex
Объявления
27.12.2013, 10:36     Пояснение рекурсии в Ханойских башнях
Ответ Создать тему
Опции темы

Текущее время: 00:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru