UC知道A栈的一个问题
来源：百度知道 编辑：UC知道 时间：2024/05/29 12:55:25
描述
宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n。
现在可以进行两种操作：
1.将一个数，从操作数序列的头端移动到栈的头端（对应数据结构栈的push操作）
2.将一个数，从栈的头端移动到输出序列的尾端（对应数据结构的pop操作）
使用这2个操作，由一个操作数序列就可以得到一系列的输出序列，下面为由1 2 3 到 2 3 1 的过程：
操作数：1 2 3
栈：
输出端：
操作数：2 3
栈：1（栈底）
输出端：
操作数：3
栈：2 1（栈底）
输出端：
操作数：3
栈：1（栈底）
输出端：2
操作数：
栈：3 1（栈底）
输出端：2
操作数：
栈：1（栈底）
输出端：2 3
操作数：
栈：
输出端：2 3 1
现在对于任意一个N，输入端的数据一定是1，2，3...N
求出可能出现的输出端数据序列的种数。
输入
第一行为一个数字T，表示有T组数据。
每组数据只含一个整数n（1≤n≤9）
输出
对于每组数据，输出可能得到的输出序列的总数目
样例输入
1
3
样例输出
5
宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n。
现在可以进行两种操作：
1.将一个数，从操作数序列的头端移动到栈的头端（对应数据结构栈的push操作）
2.将一个数，从栈的头端移动到输出序列的尾端（对应数据结构的pop操作）
使用这2个操作，由一个操作数序列就可以得到一系列的输出序列，下面为由1 2 3 到 2 3 1 的过程：
操作数：1 2 3
栈：
输出端：
操作数：2 3
栈：1（栈底）
输出端：
操作数：3
栈：2 1（栈底）
输出端：
操作数：3
栈：1（栈底）
输出端：2
操作数：
栈：3 1（栈底）
输出端：2
操作数：
栈：1（栈底）
输出端：2 3
操作数：
栈：
输出端：2 3 1
现在对于任意一个N，输入端的数据一定是1，2，3...N
求出可能出现的输出端数据序列的种数。
输入
第一行为一个数字T，表示有T组数据。
每组数据只含一个整数n（1≤n≤9）
输出
对于每组数据，输出可能得到的输出序列的总数目
样例输入
1
3
样例输出
5
楼上写的有问题，它需要多组测试样例。
其实这个问题转换过来就是求卡特兰数极
#include<stdio.h>
double fun(int n);
int main()
{
int n,m, sum, i = 0, temp;
scanf("%d", &n);
int *mul = new int[n];
temp = n;
while(n--)
{
scanf("%d", &m);
if(m == 1)
mul[i] = 1;
else
{
sum = (int)fun(m);
mul[i] = sum;
}
i++;
}
for(i = 0; i < temp; i++)
printf("%d\n", mul[i]);
return 0;
}
double fun(int n)
{
double sum = 0;
if(n == 1)
return 1;
sum += ((4*n - 2)*1.0 / (n + 1)) * fun(n - 1);
return sum;
}
你想问什么?
给，已经编译运行确认：
宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n，栈A的深度大于n
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
int n;
scanf("%d",&n);
int *d = (int *)mal