Объяснение рекурсивного решения Ханойской башни - PullRequest
Новая
       29

Объяснение рекурсивного решения Ханойской башни

0 голосов
/ 12 ноября 2018

Я боролся с проблемой Ханойской башни в течение 3 месяцев. Вот самый простой код, который я могу найти: 

void moveDisk(int n, char from, char to, char buffer)
{
    if(n == 1)
    {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    moveDisk(n-1, from, buffer, to);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    moveDisk(n-1, buffer, to, from);
}

int main()
{
    moveDisk(3, 'A', 'C', 'B');
}

И это прекрасно работает: 

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Мой самый большой вопрос: почему это работает?

Я провел некоторое исследование, и все они говорят, что: «Переместите первые n-1 диски в« буфер », затем переместите n-диск в стек« to »и, наконец, переместите первые n-1 диски в «к» стеку. Я понимаю идею этого, но мой вопрос: почему написание кода таким способом работает? Кроме того: зачем нам нужно печатать: 

cout << "Move disk 1 from " << from << " to " << to << endl;

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

Я пытался отследить рекурсию вручную, и переменные «from», «to» и «buffer» постоянно меняются - но как-то это работает!

Пожалуйста, объясните мне, почему?

Спасибо!

...