Вопрос о Ханойских башнях - PullRequest
Новая
       26

Вопрос о Ханойских башнях

1 голос
/ 19 декабря 2010

Я прочитал несколько дискуссий о проблеме Ханойских Башен. Я понимаю рекурсивное решение, используя следующий код: 

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if(nDisks == 1){
        cout << "Move the plate from " << source << " to " << dest << endl; 
    }
    else{
        Hanoi3(nDisks - 1, source, dest, intermed); 
        cout << "Move the plate from " << source << " to " << dest << endl; 
        Hanoi3(nDisks - 1, dest, intermed, source); 
    }
}

Что мне действительно нужно, так это выводить некий тип «иллюстраций» башен на каждом шаге. У меня много проблем с выполнением этого. Наш инструктор предложил использовать стеки для отслеживания того, какой диск находится в какой-либо башне, но у меня возникают проблемы с выводом этого, поскольку для поиска и вывода значений в стеках необходимо вытолкнуть верхние записи и удалить их. Они теряются, если я правильно понимаю.

В любом случае, это привело меня к какому-то решению, начинающемуся так: 

void Hanoi(int nDisks, stack<int> source, stack<int> intermed, stack<int> dest){
    if(nDisks == 1){
        dest.push(source.top()); 
        source.pop(); 
    }
    else{
        Hanoi(nDisks - 1, source, dest, intermed); 
        dest.push(source.top()); 
        source.pop(); 
        Hanoi(nDisks - 1, dest, intermed, source); 
    }
}

int main()
{

    int nDisks; 
    cout << "Enter the number of disks:    "; 
    cin >> nDisks; 

    stack<int> source, intermed, dest; 

    for(int i = nDisks; i >= 1; i--){
        source.push(i); 
    }

    Hanoi(nDisks, source, intermed, dest); 

    return 0;
}

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

Ответы [ 3 ]

3 голосов
/ 19 декабря 2010

Передайте ссылку на стеки: 

stack<int>&

Также рассмотрите возможность использования вектора, а не стека, чтобы вы могли повторить его, чтобы увидеть текущее содержимое башен.

Ответ PigBen также правильно определяет ошибку в вашем коде, когда вы не перемещаете диски из промежуточной башни в башню назначения.

1 голос
/ 19 декабря 2010

Рассмотрим ваш оригинальный код: 

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if(nDisks == 1){
        cout << "Move the plate from " << source << " to " << dest << endl; 
    }
    else{
        Hanoi3(nDisks - 1, source, dest, intermed); 
        cout << "Move the plate from " << source << " to " << dest << endl; 
        Hanoi3(nDisks - 1, dest, intermed, source); 
    }
}

Это не правильно, поэтому, возможно, поэтому ваш учитель предлагает представить башни.

Как вы заметили, std::stack является хорошим контейнером, который используется для представления текущих дисков башни, но, как вы также заметили, не совсем просто получить элементы std::stack, не щелкая их. Вы можете вытолкнуть их и поместить их в другой стек и переместить обратно, но это сложно и глупо, не говоря уже о неэффективности в общем случае. Вот почему std::stack имеет protected член c, лежащий в основе контейнер, к которому вы можете получить доступ, наследуя от класса.

В std::stack нет виртуальных членов, поэтому единственная цель иметь члена protected - сделать его немного сложным. Я думаю, что это плохое дизайнерское решение. Но это то, что у вас есть, так что 

#include <iostream>
#include <string>
#include <stack>
#include <stddef.h>
using namespace std;

typedef ptrdiff_t   Size;
typedef Size        Index;

class IntStack
    : public stack<int>
{
public:
    Size count() const { return size(); }
    int at( Index i ) const { return c[i]; }
};

class Hanoi
{
private:
    IntStack    towers_[3];
    int         nDisks_;

public:
    Hanoi( int nDisks )
        : nDisks_( nDisks )
    {
        for( int disk = nDisks;  disk >= 1;  --disk )
        {
            towers_[0].push( disk );
        }
    }

    IntStack const& towers( Index i ) const { return towers_[i]; }
};

int main()
{
    int const   nDisksTotal = 2;

    Hanoi   puzzle( nDisksTotal );

    for( Index i = 0;  i < 3;  ++i )
    {
        IntStack const& tower   = puzzle.towers( i );
        Size const      nDisks  = tower.count();

        cout << "Tower " << i << ": ";        
        for( Index diskPos = 0;  diskPos < nDisks;  ++diskPos )
        {
            if( diskPos > 0 ) { cout << ", "; }
            cout << tower.at( diskPos );
        }
        cout << endl;
    }
}

Обратите внимание, что этот код только иллюстрирует, как вы можете получить доступ к элементам этих стеков.

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

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

РЕДАКТИРОВАТЬ : хм, я вижу, другой ответ показал "решение" для ошибки. Это устраняет опыт обучения ОП и всю причину отображения башен. Этот ответ намеренно только подтвердил, что ошибка реальная, и показал вместо этого то, что запросил ОП, а именно, как эффективно отображать стеки.

Приветствия и hth.,

1 голос
/ 19 декабря 2010

Передайте стеки по ссылке и измените порядок их передачи на последнем шаге, чтобы переходить от intermed к dest, используя источник в качестве промежуточного. 

void Hanoi(int nDisks, stack<int> &source, stack<int> &intermed, stack<int> &dest){
    if(nDisks == 1){
        dest.push(source.top()); 
        source.pop(); 
    }
    else{
        Hanoi(nDisks - 1, source, dest, intermed); 
        dest.push(source.top()); 
        source.pop(); 
        Hanoi(nDisks - 1, intermed, source, dest); 
    }
}

Чтобы отобразить стопку, просто скопируйте ее и извлеките из копии.

...