1,2,3,4依次进栈,出栈随时,写一算法求出所有可能出栈序列要求带注释,最好使用C或C++感谢一楼

1,2,3,4依次进栈,出栈随时,写一算法求出所有可能出栈序列要求带注释,最好使用C或C++感谢一楼

你要算法,从程序中归纳就行了我想到一种方法,可是有点复杂,要用到树的结构,先给你看个程序,是计算n个元素进栈,可能的出栈系列种数#define N 4int m=0,a=0,b=N;main(){inS(a,b);printf(%d,m);getch();}int inS(int a,int b){a++;b--;if(b>0) inS(a,b);if(a>0) outS(a,b);}int outS(int a,int b){a--;if(a==0&&b==0) { m++; return; }if(b>0) inS(a,b);if(a>0) outS(a,b);}若想输出这些序列,可以建立一个二叉树,二叉树的节点为操作（进栈或出栈）,从根节点（第一个入栈）到叶子节点（最后一个出栈）的路径就是每个序列的操作序列,每条路径共有2N个节点,分别为每个元素的入栈和出栈操作,然后通过遍历,将这些节点输出即可建立这棵树可以用上面的递归建立,也可以用下面的方法建立①建立一颗深度为2N的满二叉树(根节点深度为1),其中根节点为IN（入栈）,其他左子树为IN,右子树为OUT（出栈）,这棵树共有2^(2N-1)个叶子节点,用根节点到叶子节点共有2^(2N-1)条路径②保留满足下面条件的路径,其他的剔除1)路径从根到叶出现IN和OUT总次数均为N个2)路径从根到叶出现 IN次数≥OUT次数(即出栈次数不可能多余入栈次数)然后输出保留的每条路径上节点类型为OUT的数据,即是出栈序列剔除方法可由下面方法实现1根节点赋值为1,2节点为IN,则此节点赋值为父节点的值+1,节点为OUT,则此节点赋值为父节点的值-1,3剔除节点的值为负数,或值>N的节点,或叶子节点上的值不=0的路径,剩下的就是满足条件的路径 -------------------------------------------------我想到一种方法,可以不用树的结构,只是模拟树,先贴程序#include math.h#define N 4main(){void init(int h[][],int a,int b,int k);int i,j,sum,logo,h[1000][2*N+1],s[N],a,b,n;int M=pow(2,2*N-1);n=M;for(i=0;i

我学会了

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息