汉诺塔问题的堆栈解法

关于汉诺塔问题，虽然是一个经典的递归示例，但是也可以用堆栈的方法来解（其实递归本质上是一种堆栈，函数帧的堆栈）。下面是分别用堆栈和递归的解法。

堆栈解法：

//hnt.cpp, the solution for hnt question using stacks

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <stack>
#include <ctime>

class Cplat
{
    public:
        Cplat(short ibottom=0, short itop=0):bottom(ibottom), top(itop)
        {
        }
        short bottom;
        short top;
};

class Caction
{
    public:
        Caction(short ibottom=0, short itop =0, short isrc=0, short ides=0):
            plat(ibottom, itop), src(isrc), des(ides)
        {
        }
        short src: 2;
        short des: 2;
        Cplat plat;
};

void display(short plat, short src, short des);

typedef std::stack < Caction > psT;//std::, remember


int main()
{
    clock_t start=clock();
    short number;
    Caction action;
    psT ps;
    //cout<<"the src is A, the min is B, the des is C"<
    //cout<<"consider you want to move plats from A to C"<
    //cout<<"how much plats you want to move?"<
    cin>>number;
    ps.push(Caction(1, number, 0, 2));

    while(!ps.empty())
    {
        action=ps.top();
        ps.pop();//reduce the top action

        if(action.plat.bottom==action.plat.top)//a action only moves one plat, it can be simly finished

        {
            display(action.plat.bottom, action.src, action.des);
        }
        else//a action moves more than one plat

        {
            ps.push( Caction(action.plat.bottom+1, action.plat.top, ~(action.src ^ action.des), action.des));
            ps.push( Caction(action.plat.bottom, action.plat.bottom, action.src, action.des));
            ps.push( Caction(action.plat.bottom+1, action.plat.top, action.src, ~(action.src ^ action.des)));
        }
    }
    clock_t finish=clock();
    cout<<"the eclapsed time is "<<static_cast<double>(finish-start)/CLOCKS_PER_SEC;
}

void display(short plat, short src, short des)
{
    char c_src=src==0?'A':src==1?'B':'C';
    char c_des=des==0?'A':des==1?'B':'C';
    //cout<<"move plat "<
}


递归解法：

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <ctime>

void solve(short bottom, short top, short src, short des);

int main()
{
    clock_t start=clock();
    short number;
    //cout<<"the src is A, the min is B, the des is C"<
    //cout<<"consider you want to move plats from A to C"<
    //cout<<"how much plats you want to move?"<
    cin>>number;
    solve(1, number, 0, 2);
    clock_t finish=clock();
    cout<<"the eclapsed time is "<<static_cast<double>(finish-start)/CLOCKS_PER_SEC;
}

void solve(short bottom, short top, short src, short des)
{
    src=src & 003;
    des=des & 003;
    if(bottom==top)//move only one plat

    {
        char c_src=src==0?'A':src==1?'B':'C';
        char c_des=des==0?'A':des==1?'B':'C';
        //cout<<"move plat "<
        return;
    }
    else
    {
        solve(bottom+1, top, src, ~(src ^ des));
        solve(bottom, bottom, src, des);
        solve(bottom+1, top, ~(src ^ des), des);
    }
}


虽然用堆栈解法似乎是不走寻常路，但是不见得就高校。从空间角度而言，虽然没有显性的调用函数帧（但是像构造函数等还是调用了），而且由于要向下传递一个子问题的对象，这个开销事实上比函数帧的开销要大。

而从时间角度上来讲，事实上堆栈的解法要耗时——很多。经过gcc的证明（VC运行的话会慢）。结果是当盘子的数目是22的时候，

堆栈解法: 1.15s左右

递归解法: 0.13s左右

当然这个也有可能是STL造成的多余耗时。但是无论怎么样，为了构建出一个堆栈的ADT，必然涉及像pop和push的操作，这也事实上叠加了函数帧。无论如何，抽象需要代价。在时间严格的时候，C的确比对象代码要快的多。

注意到为了减少内存分配的耗时，堆栈解法中不是用指针作为元素，而是一个对象的句柄。这样的话，当前的帧就会膨胀。但是如果是用指针的话，堆栈解法将耗时1.99s，差不多是多了一倍。

所以对于时间严格的应用来说，避免频繁的内存操作是一个有利的方面。