Question

:)高分悬赏问题!!!!

怎样用C++语言实现汉诺塔?(即Hannoi问题)
(请提供原代码!)
要求:A:只要能实现3个盘子从3个柱子中的一个到另一个即可!
B:不能用递归函数去编写,只能用"栈"去编写!
C:必须严格用C++语言编写!即只能用类去实 现栈,而不能用C语言中结构体等去构造栈!

Answer 1

运行示例：
./hanoi 3

运行结果：
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

源码如下：

#include <iostream>
#include <stdlib.h>

class TStatus
{
public:
char a, b, c;
int n, step;
void assign(char a = 0, char b = 0, char c = 0, int n = 0, int step = 0)
{
this->a = a;
this->b = b;
this->c = c;
this->n = n;
this->step = step;
}
TStatus(char a = 0, char b = 0, char c = 0, int n = 0, int step = 0)
{
assign(a, b, c, n, step);
}
};

class TStack
{
private:
TStatus *s;
int max_size;
int top;
public:
TStack(int max_size)
{
if (max_size < 0)
max_size = 0;
this->max_size = max_size;
top = 0;
s = new TStatus[max_size];
if (!s)
this->max_size = 0;
}
~TStack()
{
if (s)
delete[] s;
}
bool empty() const
{
return top == 0;
}
bool push(const TStatus &x)
{
if (top >= max_size)
return false;
s[top++] = x;
return true;
}
bool pop(TStatus &x)
{
if (empty())
return false;
x = s[--top];
return true;
}
};

class THanoi
{
private:
TStack stack;
int n;
public:
THanoi(int disk_num): n(disk_num), stack(disk_num)
{
}
void process()
{
if (n <= 0)
return;
TStatus start('A', 'B', 'C', n, 0);
stack.push(start);
while (!stack.empty())
{
TStatus cur;
stack.pop(cur);
if (cur.n == 1)
cout << cur.a << " -> " << cur.c << endl;
else
{
switch (cur.step)
{
case 0:
cur.step++;
stack.push(cur);
cur.assign(cur.a, cur.c, cur.b, cur.n-1, 0);
stack.push(cur);
break;
case 1:
cout << cur.a << " -> " << cur.c << endl;
cur.assign(cur.b, cur.a, cur.c, cur.n-1, 0);
stack.push(cur);
break;
}
}
}
}
};

int main(int argc, char **argv)
{
if (argc < 2)
{
cerr << "Usage: " << argv[0] << " <disk_num>" << endl;
return 1;
}
int disk_num = atoi(argv[1]);
THanoi hanoi(disk_num);
hanoi.process();
return 0;
}

Answer 2

才5分……

Answer 3

呵呵

Answer 4

楼上是正解啦