fanxiaobao 发表于 2014-1-23 09:43:45

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

本帖最后由 fanxiaobao 于 2014-1-26 09:21 编辑

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


谭斌谭斌 发表于 2014-1-23 11:21:49

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

仰望天上的光 发表于 2014-1-23 11:38:08

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

fishc_hz 发表于 2014-1-23 23:40:14

贴代码         

fanxiaobao 发表于 2014-1-26 09:21:34


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

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

用堆栈吧{:5_91:}#include <iostream>
#include <cstdlib>
#include <limits>
using namespace std;

#define STYPE int

#define        EMPTY    -2
#define        FULL   -1
#define        PUSH_OK   1
#define        CAPACITY32767

class Stack {
    int top;
    STYPE element ;
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 = 0;
}

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

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

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

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

int Stack::push (STYPE new_elem)
{
    if (top < CAPACITY - 1) {
      top++;
      element = 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 << " N\n";
      exit(1);
    }

    N = (STYPE)strtol(argv, (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 发表于 2014-1-26 11:11:22

andalousie 发表于 2014-1-26 10:22 static/image/common/back.gif
用堆栈吧

堆栈虽然我还看不懂,但还是感谢你这么长的代码!!
页: [1]
查看完整版本: 递归和汉诺塔问题~!!!!!