Question

出栈入栈问题

有（1，……，n）n个整数，按照入栈出栈规则（先进者先后，随时可进出，互不影响）从1→n依次进出栈，栈的深度不限，共有多少种情况？n=1， 1； 1种n=2，1 2；2 1； 2种 n=3，1 2 3；1 3 2；2 1 3；2 3 1；3 2 1； 5种即n与情况种数的关系。

Answer 1

这是一个火车进站出站的问题，里面既有全排列的问题又有进栈出栈的问题！！！程序如下：#include<stdio.h>
int cont=1; /*全局变量，用于记录所有可能的出栈序列个数*/
void print(int str[],int n);
/*求整数序列 str[]从k到 n 的全排列*/
void perm(int str[],int k,int n)
{int i,temp; <br> if (k==n-1) print(str,n); <br> else <br> { for (i=k;i<n;i++) <br> {temp=str[k]; str[k]=str[i]; str[i]=temp; <br> perm(str,k+1,n); /*递归调用*/ <br> temp=str[i]; str[i]=str[k]; str[k]=temp; <br> }
}
}
/*本函数判断整数序列 str[]是否满足进出栈规则,若满足则输出*/
void print(int str[],int n)
{int i,j,k,l,m,flag=1,b[2]; <br> for(i=0;i<n;i++) /*对每个 str[i]判断其后比它小的数是否为降序序列*/ <br> { m=0; <br> for(j=i+1;j<n&&flag;j++) <br> if (str[i]>str[j]) {if (m==0) b[m++]=str[j]; <br> else {if (str[j]>b[0]) {flag=0;}
else b[0]=str[j];
}
}
}
if(flag) /*满足出栈规则则输出 str[]中的序列*/
{ printf(" %2d:",cont++);
for(i=0;i<n;i++)
printf("%d",str[i]);
printf("\n");
}
}
void main()
{int str[100],n,i; <br> printf("input a int:"); /*输出排列的元素个数*/ <br> scanf("%d",&n); <br> for(i=0;i<n;i++) /*初始化排列集合*/ <br> str[i]=i+1; <br> printf("input the result:\n"); <br> perm(str,0,n); <br> printf("\n"); <br> }

Answer 2

这个问题不是简单的计算方法的，我有个程序可以给你看下。如果想要，和我QQ聊吧。

Answer 3

不是，先进后出，后进先出吗？？？？