Башни Ханоя

Question

Я работаю над упражнением в книге, в котором просим нас решить проблему Ханойских башен рекурсивными методами. Я пришел к решению, но из того, что я понял после просмотра Интернета, когда я закончил, можно сказать, что мое решение может быть неправильным. Кто-нибудь знает лучший / другой способ решения проблемы? И есть ли у кого-нибудь предложения по улучшению. (Между прочим, выходной сигнал правильный. Предполагается, что он должен только сказать, от какой башни к другой колышки движутся, а не конкретно какие колышки)

Вот код:

#include <iostream>
#include <cmath>

using namespace std;

static int counter = 0;

void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
if (dskToMv == 0);
else
{
    if (dskToMv%2!=0)
    {
        cout << cLocation << "->" << tmpLocation << endl;
        cout << cLocation << "->" << fLocation << endl;
        cout << tmpLocation << "->" << fLocation << endl;
        ToH(dskToMv-1, cLocation, fLocation, tmpLocation);
    }
    else if (dskToMv%2==0)
    {
        counter++;
        if (counter%2==0)
            cout << fLocation << "->" << cLocation << endl;
        else
            cout << cLocation << "->" << fLocation << endl;
        ToH(dskToMv-1, tmpLocation, cLocation, fLocation);
    }
}
}

int main()
{
int x, j;
cout << "Enter number of disks: ";
cin >> x;
j = pow(2.0, x-1)-1;
if (x%2==0)
    ToH(j, 1, 2, 3);
else
    ToH(j, 1, 3, 2);
return 0;
}

Этот метод квалифицирован как рекурсия?

Answer 1

Чтобы ответить на ваш вопрос: да, это квалифицируется как рекурсия. Каждый раз, когда функция вызывает себя, это рекурсия.

При этом ваш код может быть существенно урезан:

#include <iostream>

using namespace std;

void ToH(int dskToMv, int cLocation, int tmpLocation, int fLocation)
{
    if( dskToMv != 0 ) 
    {
        ToH( dskToMv-1, cLocation, fLocation, tmpLocation );
        cout << cLocation << "->" << fLocation << endl;
        ToH( dskToMv-1, tmpLocation, cLocation, fLocation );
    }
}

int main()
{
    int x;
    cout << "Enter number of disks: ";
    cin >> x;
    ToH(x, 1, 2, 3);
    return 0;
}

Answer 2

Вот рекурсивное решение для Ханойской башни.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

void move(vector<int>& frompeg, vector<int>& topeg) {
    topeg.push_back(frompeg.back());
    frompeg.pop_back();
}

void hanoi(vector<int>& frompeg, vector<int>& topeg, vector<int>& auxpeg, 
int num_disks) {
    if (num_disks == 1) {
        move(frompeg, topeg);
    }
    else {
        hanoi(frompeg, auxpeg, topeg, num_disks - 1);
        move(frompeg, topeg);
        hanoi(auxpeg, topeg, frompeg, num_disks - 1);
    }
}

void printpeg(vector<int> a, vector<int> b, vector<int> c) {
    cout << "a: ";
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    cout << "b: ";
    for (int i = 0; i < b.size(); i++) {
        cout << b[i] << " ";
    }
    cout << "\n";
    cout << "c: ";
    for (int i = 0; i < c.size(); i++) {
        cout << c[i] << " ";
    }

}

int main() {

    int n;
    cin >> n;
    vector<int> a,b,c;
    for (int i = 0; i < n; i++) {
        a.push_back(n - i);
    }
    cout << "befor: " << endl;
    printpeg(a, b, c);
    hanoi(a, b, c, n);
    cout << "after: " << endl;
    printpeg(a, b, c);
    cin.get();
    cin.get();
    return 0;
    }

Answer 3

#include <iostream>

using namespace std;

void towers(int, char, char, char);

void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {

        cout<<"\n Move disk 1 from peg "<<frompeg<<" to peg "<<topeg<<endl;

        return;
    }

    towers(num - 1, frompeg, auxpeg, topeg);

    cout<<"\n Move disk "<<num<<" from peg "<<frompeg<<" to peg "   <<topeg<<endl;

    towers(num - 1, auxpeg, topeg, frompeg);
}

int main()
{
    int num;

    cout<<"Enter the number of disks : ";

    cin>>num;

    cout<<"The sequence of moves involved in the Tower of Hanoi are :\n"<<endl;

    towers(num, 'A', 'C', 'B');

    return 0;
}

Answer 4

Каждый метод рекурсии имеет 3 шага

1) Условие проверки 2) Возвращаемое значение при выполнении условия проверки.3) Идеальный вызов самого метода

@ Решение Stargazer712 идеально.

Answer 5

Проще всего, если вы посмотрите на проблему рекурсивно:

Чтобы переместить N дисков из A в B (используя C):

1. , если (N> 1) переместите N-1 диск от A до C (с использованием B)
2. переместить один диск с A на B
3. , если (N> 1) переместить N-1 дисков с C на B (с использованием A)

Для любого данного звонка, какой бы ни была привязка , а не , источником или адресатом является вспомогательный объект.

Чтобы ответить на ваш фактический вопрос: да, ваше решение выглядит так:рекурсивный, хотя и немного более сложный, чем действительно необходимо.