递归和汉诺塔问题~!!!!!

fanxiaobao

昨天下午看了甲鱼兄递归解决汉诺塔问题的视频后,至今大脑还在一个死循环跳不出来怎么办?求大神帮忙啊,好痛苦,夜不能寐啊...............

谭斌谭斌

贴出代码，不然谁知道你的问题是什么

仰望天上的光

这个本质上说不是C语言本身的问题，而在于原先你是否能看懂数学定义，很多数学上的定义，如费泼拉契数列都不直接描述如何得到该数列的，而是通过递归的方式定义问题。而C语言的递归仅仅是提供了一种类似的方式而已。

fishc_hz

贴代码           

fanxiaobao

经过这两天的无限循环终于找到出口了,并且做了一个数组版的过程演示和简单的步骤提示,需要的新手可以看一下,老鸟可以飘过.....
网盘:http://pan.baidu.com/s/1sjHE4Cd

andalousie

用堆栈吧

#include <iostream>
#include <cstdlib>
#include <limits>
using namespace std;

#define STYPE int

#define        EMPTY    -2
#define        FULL     -1
#define        PUSH_OK   1
#define        CAPACITY  32767

class Stack {
    int top;
    STYPE element [CAPACITY];
public:
    Stack ();
    ~Stack ();
    int num (void);
    int push (STYPE new_elem);
    STYPE pop (void);
    STYPE snoop (void);
};

Stack::Stack (void)
{
    top = -1;
    for (int i=0; i<CAPACITY; i++)
        element[i] = 0;
}

Stack::~Stack (void)
{
    // nothing
}

int Stack::num (void)
{
    return (top + 1);
}

STYPE Stack::pop (void)
{
    STYPE x;
    if (top >= 0) {
        x = element[top];
        element[top] = 0;
        top--;
        return x;
  } else
      return EMPTY;
}

STYPE Stack::snoop (void)
{
    if (top >= 0)
        return element[top];
    else
        return EMPTY;
}

int Stack::push (STYPE new_elem)
{
    if (top < CAPACITY - 1) {
        top++;
        element[top] = new_elem;
        return PUSH_OK;
    } else
        return FULL;
}

int main (int argc, char **argv)
{
    STYPE N, _N, _P, _T, _F, _R;

    if (argc != 2) {
        cerr << "usage: " << argv[0] << " N\n";
        exit(1);
    }

    N = (STYPE)strtol(argv[1], (char **)NULL, 10);

    /* a bit of error checking, LONG_XXX should be there in limits.h */
    if (N == LONG_MIN || N == LONG_MAX || N <= 0) {
        cerr << "illegal value for number of disks\n";
        exit(2);
    }

    Stack s;
    s.push(N);
    s.push(1);
    s.push(3);
    s.push(0);

    while (s.num() != 0) {
        _P = s.pop();
        _T = s.pop();
        _F = s.pop();
        _N = s.pop();
        _R = 6 - _F - _T;
        if (_P == 0) {
            if (_N == 1)
            cout << "move " << _F << " --> " << _T << "\n";
            else {
                s.push(_N);
                s.push(_F);
                s.push(_T);
                s.push(1);
                s.push(_N-1);
                s.push(_F);
                s.push(_R);
                s.push(0);
            } 
        } else {
            cout << "move " << _F << " --> " << _T << "\n";
            s.push(_N-1);
            s.push(_R);
            s.push(_T);
            s.push(0);
        }
    }
}

fanxiaobao

andalousie 发表于 2014-1-26 10:22

                               
登录/注册后可看大图

用堆栈吧

堆栈虽然我还看不懂,但还是感谢你这么长的代码!!