写的一个递归程序 出问题了


大致的是 给定 1 2 3 4 到n 的序列
求出所有的合法的出站序列

准备用递归写
a 表示 初始站 b 是中间的那个中转站 c 是终点

foo（m,n） //表示 a 和 b 中元素的个数
有两种转移方式 --》foo(m,n-1)

--> foo(m-1,n+1)

但是我一直不太会控制 这个递归程序，貌似数据会有污染

CSS code

#include <stdio.h>#include <stdlib.h>#include <math.h>#include <stack>#include <iostream>using namespace std;const int N = 1000;int a[N],d[N];stack<int> b,c;int M;//void cp(stack<int> &src ,)void foo(int n,int m){    int tmp = 0;    if(m < 0 || n <0 )        return ;    if(m == 0 && n ==0)    {        int i = 1;        while(!c.empty() )        {            tmp = c.top();            c.pop();            d[i++] = tmp;        }        for(i = M ; i > 0 ; i --)        {            printf("%d%c",d[i],(i==1)?'\n':' ');            c.push(d[i]); //恢复栈C 的内容        }    }    if(n > 0)    {        tmp = a[n];        b.push(tmp);        foo(n-1,m+1);        b.pop();    }    if( m >0 && !b.empty())    {        tmp = b.top();        b.pop();        c.push(tmp);        foo(n,m-1);        c.pop();    }}int main(){    M = 4;    for(int i = 1 ; i <= M ; i ++)        a[i] = i;    foo(M,0);    return 0;}

[解决办法]
你最好不要将C和C++语法混用，下面是我写的，希望对你用帮助。

#include<iostream>
#include<stack>

using namespace std;
int count = 0;

template<class T>
void Create(stack<T> S, T tar[], T str[], int pos, int curp, int n)
{
if(pos < n) //还有元素没进栈则继续进栈
{
S.push(str[pos]); //进栈
Create(S, tar, str, pos+1, curp, n);
S.pop(); //出栈恢复环境
}

if(!S.empty()) //栈不为空则继续出栈
{
tar[curp] = S.top();//将出栈元素记录到目标数组中以待输出
S.pop(); //出栈
Create(S, tar, str, pos, curp+1, n);
S.push(tar[curp]); //进栈恢复环境
}

if(pos == n && S.empty()) //栈空且所有元素都进过栈则输出
{
cout << "[" << ++count << "] ";
for(int i = 0; i < curp; i ++)
{
cout << tar[i];
}
cout << endl;
}
}

void main()
{
stack<char> S;
char str[6] = "12345";
char tar[6];

Create(S, tar, str, 0, 0, 5);
}


[解决办法]
数据出栈以后，记得把数据再送回来，以便下次递归时候使用，在楼主代码中增加了2条语句，我标识在程序中了

C/C++ code

const int N = 1000;int a[N],d[N];stack<int> b,c;int M;void foo(int n,int m){    int tmp = 0;    if(m < 0 || n <0 )        return ;    if(m == 0 && n ==0)    {        int i = 1;        while(!c.empty() )        {            tmp = c.top();            c.pop();            d[i++] = tmp;        }        for(i = M ; i > 0 ; i --)        {            printf("%d%c",d[i],(i==1)?'\n':' ');            c.push(d[i]); //恢复栈C 的内容        }    }    if(n > 0)    {        tmp = a[n];        b.push(tmp);        foo(n-1,m+1);        a[n] = b.top(); //这里增加一句，需要再次把数据复原，以便下次使用        b.pop();    }    if( m >0 && !b.empty())    {        tmp = b.top();        b.pop();        c.push(tmp);        foo(n,m-1);        b.push(c.top());    //相应的，这里添加一句        c.pop();    }}int main(){    M = 4;    for(int i = 1 ; i <= M ; i ++)        a[i] = i;    foo(M,0);    return 0;}