Не могу понять алгоритм Ханойской башни

@Lars · Регистрация: 16.09.2014

Author24 — интернет-сервис помощи студентам

Всем привет, есть у кого время разжевать мне работу кода ?
Битый час сижу с дебагером отлаживаю по шагам ,но после этой строчки

C++

1	hanoi_Turm(scheibe_anzahl - 1, start_basis, mittlere_basis, ziel_basis);

начинается для меня какая-то абракадабра .

C++

#include <iostream>
using namespace std;
 
void hanoi_Turm(int scheibe_anzahl, int start_basis, int ziel_basis, int mittlere_basis) 
//scheibe_anzahl-число колец, start_basis-начальное положение колец(1-3),ziel_basis-конечное положение колец(1-3)
{                               //mittlere_basis - промежуточный колышек(1-3)
    if (scheibe_anzahl != 0)
    {
        hanoi_Turm(scheibe_anzahl - 1, start_basis, mittlere_basis, ziel_basis);
 
        cout << start_basis << " -> " << ziel_basis << endl;
 
        hanoi_Turm(scheibe_anzahl - 1, mittlere_basis, ziel_basis, start_basis);
    }
}
 
int main()
{
    setlocale(LC_ALL, "rus");
    int start_basis, ziel_basis, mittlere_basis, scheibe_anzahl;
    cout << "basis stab:";
    cin >> start_basis;
    cout<<  endl;
    cout << "ziel stab:"; 
    cin >> ziel_basis;
    cout << endl;
    cout << "mittlere stab:"; 
    cin >> mittlere_basis;
    cout << endl;
    cout << "anzahl scheibe:"; 
    cin >> scheibe_anzahl;
    cout << endl;
 
    hanoi_Turm(scheibe_anzahl, start_basis, ziel_basis, mittlere_basis);
    system("pause");
    return 0;
}

@Mr.X · 26.12.2015, 08:27

Недавно уже была такая тема.

@Dimension · 26.12.2015, 11:11

n-1 кольцо кладете на вторую стойку ,затем n-ое на третью стойку ,затем те что на второй перекладываете на третью

@Lars · 26.12.2015, 23:35 **[ТС]**

Я читал коменты в этой теме задолго до того как создать свою тему .Как играть в Ханойскую башню теоретически понятно ,но как это реализовать рекурсией загадка .

@DocC · 27.12.2015, 08:14

Lars,
Итак,

C++

#include <iostream>
#include <locale>
 
using std::cout;
using std::endl;
using std::cin;
 
int count = 0;
 void hanoi_tower(int disk, int start, int final, int help) {   
    if(disk != 0) {
        hanoi_tower(disk-1, start, help, final);
        cout << "Шаг № " << count << " Берём диск №" << disk << ", снимаем его со стержня # " 
                               << start << " после чего надеваем на стержень # "
                               << final << endl;
        hanoi_tower(disk-1,  help, final, start);
 
    }
    else count ++;
}
 
int main() {
    setlocale(LC_ALL,"Russian");
    int diskamount, start_rod, final_rod, help;
    //help - вспомогательный-промежуточный стержень
    cout << "Число дисков = ";
    cin >> diskamount;
    cout << "Номер стержня, на котором находятся кольца = ";
    cin >> start_rod;
    cout << "Номер стержня на которой переносятся кольца = ";
    cin >> final_rod;
    if (start_rod != 1 && final_rod != 1)
          help = 1;
      else if (start_rod != 2 && final_rod != 2)
                 help = 2;
             else if (start_rod != 3 && final_rod != 3)
                        help = 3;
    cout << "Вспомогательный диск = " << help << endl;
    hanoi_tower(diskamount, start_rod, final_rod, help);
    return 0;
}

Вероятнее всего, я где-то сам запутаюсь, поясняя то, как будет выполняться программа. Но всё же попробую. И, надеюсь, что смогу вам помочь понять рекурсивный метод для решения задачи с Ханойской Башней

I. Вносим входные данные.
В моём примере:
Кол-во дисков = 3
Стержень, с которого требуется перенести кольца = 1
Стержень, на который требуется перенести кольца = 3
Соответственно, вспомогательным(свободным) стержнем является стержень под номером 2.
II. Обращаемся в первый раз к функции hanoi_tower, передавая при этом следующие параметры (d, s, f, h) -> (3, 1, 3, 2)
Сокращения (особое внимание обратите на то, как меняется порядок передачи параметров при различных вызовах функции)
d-disk
s-start
f-final
h-help

Пойдём поэтапно:
Проверяем условие, что кол-во дисков не равно 0 (d != 0)
Оно выполняется.
1) Первым делом рекурсивно вызывается функция hanoi_tower с параметрами (d-1, s, h, f) -> (3-1, 1, 2, 3)

1.1) Обращаемся во второй раз к функции hanoi_tower с параметрами (d, s, f, h) -> (2, 1, 2, 3)
Выполняется условие (d != 0)
Вызывается функция hanoi_tower с параметрами (d-1, s, h, f) -> (2-1, 1, 3, 2)

1.1.1) Обращаемся во третий раз к функции hanoi_tower с параметрами (d, s, f, h) -> (1, 1, 3, 2)
Выполняется условие (d != 0)
Вызывается функция hanoi_tower с параметрами (d-1, s, h, f) -> (1-1, 1, 2, 3), которая в виду d = 1-1 = 0 закончит рекурсию.
Переходим к cout << disk(d) << start(s) << final(f). Имеем: Диск(d) 1 переносим со стержня(s) 1 на стержень(f) 3 - Это шаг 1.
После cout снова рекурсивно вызывается функция hanoi_tower уже с параметрами (d-1, h, f, s) -> -> (1-1, 2, 1, 3), которая в виду d = 1-1 = 0 закончит рекурсию.

1.1.2) На этапе 1.1 после обращения к функции hanoi_tower (1.1.1) выполняем cout << disk(d) << start(s) << final(f):
Имеем: Диск(d) 2 переносим со стержня(s) 1 на стержень(f) 2 - Это шаг 2.

1.1.3) После cout (1.1.2), рекурсивно вызывается функция hanoi_tower с параметрами (d-1, s, f, h) -> (1, 3, 2, 1).
Выполняется условие (d != 0)
Вызывается функция hanoi_tower с параметрами (d-1, s, h, f) -> (1-1, 1, 3, 2), которая в виду d = 1-1 = 0 закончит рекурсию.

1.1.3.1) Переходим к cout после 1.1.3.
Имеем: Диск(d) 1 переносим со стержня(s) 3 на стержень(f) 2 - Это шаг 3.
1.1.3.2) После cout (1.1.3.1) вызывается функция hanoi_tower с параметрами (d-1, h, f, s) -> (1-1, 1, 2, 3), которая в виду d = 1-1 = 0 закончит рекурсию.

2) Мы закончили с "первой" строчкой (она же этап "1") в условии if(d != 0). Переходим к строке с cout, вспоминая, что на этапе 1 hanoi_tower имела следующие параметры (d, s, f, h) -> (3, 1, 3, 2).
Имеем: Диск(d) 3 переносим со стержня(s) 1 на стержень(f) 3 - Это шаг 4.

2.1) После строки cout (2) попадем на строку вызова функции hanoi_tower с параметрами (d-1, h, f, s) -> (3-1, 2, 3, 1). hanoi_tower примет за параметры (d, s, f, h) -> (2, 2, 3, 1)
Снова проверка условия if(d != 0) даёт нам true. Идём далее.

2.1.1) Попадаем на строку вызова функции hanoi_tower с параметрами (d-1, s, h, f) -> (2-1, 2, 1, 3). Отправляемся ещё глубже.

2.1.1.1) Уже вызвана функция hanoi_tower с параметрами (d, s, f, h) -> (1, 2, 1, 3). Проверку if(d != 0) проходит.
Вызывается функция hanoi_tower с параметрами (d-1, s, h, f) -> (1-1, 2, 3, 1), которая в виду d = 1-1 = 0 закончит рекурсию.
2.1.1.2) После завершения данной рекурсии попадаем на строку cout.
Имеем: Диск(d) 1 переносим со стержня(s) 2 на стержень(f) 1 - Это шаг 5.
2.1.1.3) После cout (2.1.1.2) попадем на строку вызова функции hanoi_tower с параметрами (d-1, h, f, s) -> (1-1, 3, 1, 2), которая в виду d = 1-1 = 0 закончит рекурсию.

2.1.2) Возвращаемся на уровень повыше, он же этап 2.1. Рекурсия по "первой" строке закончилась. Переходим к cout. При этом помним, какие значения имели параметры имела наша функция на этапе 2.1.
Имеем: Диск(d) 2 переносим со стержня(s) 2 на стержень(f) 3 - Это шаг 6.

2.1.3) Итак, этап 2.1 пройден, cout выведен. Попадаем на следующую строку, в которой в очередной раз вызывается функция hanoi_tower с передаваемыми параметрами (d-1, h, f, s) -> (2-1, 1, 3, 2) (см. этап 2.1, второе предложение).

2.1.3.1) Вызвана функция hanoi_tower с параметрами (d, s, f, h) -> (1, 1, 3, 2). Условие if(d != 0) срабатывает. Вызывается в предпоследний раз функция hanoi_tower с параметрами (d, s, h, f) -> (1-1, 1, 2, 3), которая в виду d = 1-1 = 0 закончит рекурсию.
2.1.3.2) Попадаем в строку с cout.
Имеем: Диск(d) 1 переносим со стержня(s) 1 на стержень(f) 3 - Это шаг 7.
2.1.3.3) Переходим на строку, следующую за строкой с cout. Снова передаем параметры функции hanoi_tower и опять же завершаем рекурсии, так как d-1 = 1-1 = 0 (этап 2.1.3.1)

finita la comedia

@Lars · 27.12.2015, 15:33 **[ТС]**

Супер спасибо вам за объяснение ,я проникся в тему

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	26.12.2015, 08:27	2
	Недавно уже была такая тема. 0

@Dimension Dimension 594 / 462 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	26.12.2015, 11:11	3
	n-1 кольцо кладете на вторую стойку ,затем n-ое на третью стойку ,затем те что на второй перекладываете на третью 0

@Lars 1 / 1 / 0 Регистрация: 16.09.2014 Сообщений: 36
	26.12.2015, 23:35 [ТС]	4
	Я читал коменты в этой теме задолго до того как создать свою тему .Как играть в Ханойскую башню теоретически понятно ,но как это реализовать рекурсией загадка . 0

@Lars 1 / 1 / 0 Регистрация: 16.09.2014 Сообщений: 36
	27.12.2015, 15:33 [ТС]	6
	Супер спасибо вам за объяснение ,я проникся в тему 0

Не могу понять алгоритм Ханойской башни

Решение