Ханойская башня C ++ (с использованием рекурсии)

Question

Ханойская башня C ++ (с использованием рекурсии)

Я написал следующий код в качестве практического упражнения.
Я получаю неправильный вывод при печати целевого стека.
Может кто-нибудь указать, где я иду не так?

//Tower of Hanoi using Stacks!
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

class Stack
{
private:
int *t;
int length, top;

public:
Stack(int len)
{
length=len;
t= new int[len];
top=-1;
}

~Stack()
{
delete []t;
}

void push(int d)
{
top++;
t[top]=d;
}

int pop()
{
top--;
return t[top+1];
}

void printstack()
{
int cur=top;
while(cur>-1)
{
cout<<t[cur]<<endl;
cur--;
}
}
};

void MoveTowerofHanoi(int disk, Stack *source, Stack *temp, Stack *destination)
{
if (disk==0)
{
destination->push(source->pop());
}
else
{
MoveTowerofHanoi(disk-1,source,temp,destination);
destination->push(source->pop());
MoveTowerofHanoi(disk-1,temp,destination,source);
}
}

void main()
{
clrscr();
int disks;
cout<<"Enter the number of disks!"<<endl;
cin>>disks;
Stack* source=new Stack(disks);
for(int i=0; i<disks; i++) {
source->push(disks-i);
}
cout<<"Printing Source!"<<endl;
source->printstack();
Stack* temp=new Stack(disks);
Stack* destination=new Stack(disks);
MoveTowerofHanoi(disks,source,temp,destination);
cout<<"Printing Destination!"<<endl;
destination->printstack();
getch();
}

Вот результат, который я получаю:

Enter the no. of disks!
3
Printing Source!
1
2
3
Printing Destination!
-4

После редактирования код выглядит так:

    void MoveTowerofHanoi(int disk, Stack *source, Stack *destination, Stack *temp)
{
if (disk==1)
{
destination->push(source->pop());
}
else
{
MoveTowerofHanoi(disk-1,source,temp,destination);
destination->push(source->pop());
MoveTowerofHanoi(disk-1,temp,destination,source);
}
}

первая ошибка была:

void MoveTowerofHanoi(int disk, Stack *source, Stack *temp, Stack *destination)

второй был:

if (disk==0)

Большое спасибо всем за помощь!

Изменения, внесенные в класс стека:

void push(int d)
{
if(top<length-1)
{
top++;
t[top]=d;
}

}

int pop()
{
if(top>-1)
{
top--;
return t[top+1];
}
}

4

c++recursion stack towers-of-hanoi

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это работает:

//Tower of Hanoi using Stacks!
#include<iostream>
//#include<conio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;

void print_elem(int elem)
{
cout << elem << endl;
}

class Stack{
public:
void push(int d){t.push_back(d);}
int pop()
{
int d=t.back();
t.pop_back();
return d;
}
void printstack()
{
for_each(t.rbegin(),t.rend(),print_elem);
}
private:
vector<int> t;

};

void MoveTowerofHanoi(int disk, Stack *source, Stack *temp, Stack *destination)
{
if (disk==1)
{
destination->push(source->pop());
}
else
{
MoveTowerofHanoi(disk-1,source,destination,temp);
destination->push(source->pop());
MoveTowerofHanoi(disk-1,temp,source,destination);
}
}

int main()
{
int disks;
cout<<"Enter the number of disks!"<<endl;
cin>>disks;
Stack* source = new Stack();
for(int i=disks; i>0; --i) {
source->push(i);
}

cout<<"Printing Source!"<<endl;
source->printstack();
Stack* temp = new Stack();
Stack* destination = new Stack();
MoveTowerofHanoi(disks,source,temp,destination);
cout<<"Printing Destination!"<<endl;
destination->printstack();
delete source;
delete temp;
delete destination;
}

2