返回信息流将整数1，2，3，4，5依次入栈，同时也允许出栈操作，试问通过入栈出栈会有多少种序列情况，怎么得到？
想了一会没想明白，怎么用C实现，请大牛讲讲吧。谢谢！
这是一条镜像帖。来源：北邮人论坛 / cpp / #31489同步于 2009/11/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
求教一个栈的问题
jrwfreedom
2009/11/17镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
使用递归，2个参数，一个参数是剩余元素的个数，初始值为5，另外一个参数是堆栈里的元素数，初始值为0. 整个递归的过程就是由（5，0）-》。。。-》（0，X），因为一旦5个元素都使用了以后，出堆栈的顺序就固定了，当然递归的过程中一定要保证x不能小于0.计数使用一个全局变量，每调用到最后就加1（即出现（0，X））。具体怎么实现，自己画个图可能比较清楚一点，仅供参考，可能有不妥之处。。。
#include<stdio.h>
int count=0;
int fun(int m,int n)
{
if(m==0)
count++;
else if(n==0)
fun(m-1,n+1);
else
{
fun(m-1,n);
fun(m,n-1);
}
return 0;
}
int main()
{
fun(5,0);
printf("the result is :%d",count);
return 0;
}
-----------------
这个是之前写的，有点问题，已经改正了，见楼下
算法版有这个题的讨论，你可以参考一下
http://forum.byr.edu.cn/wForum/disparticle.php?boardName=ACM_ICPC&ID=35607&pos=7
【 在 lyp275 的大作中提到: 】
: #include<stdio.h>
: int count=0;
: int fun(int m,int n)
: ...................
结果好像是 (2n n)/n+1;
写了代码~~看起来不是很好，但是结果还不错
#include <iostream>
#include <queue>
typedef std::queue<char*> RESULT_SET;
void insert_str(char* str1, const char* str2, int pos) {
int i;
char* buf = new char[strlen(str1)];
strcpy(buf, str1);
for (i = 0; *buf != '\0' || *str2 != '\0'; i++) {
if (i < pos || *str2 == '\0') {
*str1++ = *buf++;
} else {
*str1++ = *str2++;
}
}
*str1 = '\0';
}
int get_pos(const char* str) {
int len = strlen(str);
const char* p = str + len - 1;
while (*p == 'p') {
p--;
len--;
}
return len;
}
void PrintStack(int n, RESULT_SET& ret) {
int i, j, l;
while (!ret.empty())
{
ret.pop();
}
char* str1 = "";
char buf1[255], numbuf[31];
ret.push(str1);
for (i = 1; i <= n; i++) {
itoa(i, numbuf, 10);
strcat(numbuf, "p");
l = ret.size();
while (l--) {
strcpy(buf1, ret.front());
if (strcmp(buf1, "123ppp") == 0) {
int kk = 0;
}
j = get_pos(buf1);
for (; j <= strlen(buf1); j++) {
if (buf1[j] != 'p')
continue;
char* buf2 = new char[255];
strcpy(buf2, buf1);
insert_str(buf2, numbuf, j);
ret.push(buf2);
}
char* buf2 = new char[255];
strcpy(buf2, buf1);
strcat(buf2, numbuf);
ret.push(buf2);
ret.pop();
}
}
}
int main() {
RESULT_SET ret;
PrintStack(6, ret);
std::cout << ret.size() << '\n';
while (!ret.empty()) {
std::cout << ret.front() << std::endl;
ret.pop();
}
getchar();
return 0;
}
恩，我刚才检查了一下我的代码，确实有问题，我在写递归的时候把
else
{
fun(m-1,n+1);
fun(m,n-1);
}
中的fun(m-1,n+1)写成了fun(m-1,n)，所以结果是错的，现在改正过来了 。
正确的递归是：
#include<stdio.h>
int count=0;
int fun(int m,int n)
{
if(m==0)
count++;
else if(n==0)
fun(m-1,n+1);
else
{
fun(m-1,n+1); //此处改正
fun(m,n-1);
}
return 0;
}
int main()
{
fun(5,0);
printf("the result is :%d",count);
return 0;
}
【 在 DarKMoon 的大作中提到: 】
: 结果好像是 (2n n)/n+1;
: 写了代码~~看起来不是很好，但是结果还不错
: #include <iostream>
: ...................