银川网站建设志达四方,网页制作基础教程自学,做网站苏州,创意作品设计方案大全题目
有一个单端封闭的管子#xff0c;将N(1N18)个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问#xff1a;倒出来的方法总数有多少种#xff1f;
输入输出格式
输入格式
输入文件只含一个整数n…题目
有一个单端封闭的管子将N(1N18)个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问倒出来的方法总数有多少种
输入输出格式
输入格式
输入文件只含一个整数n1≤n≤18
输出格式
输出文件只有一行即可能输出序列的总数目。
输入输出样例
输入样例
3
输出样例
5
解析
假设i个元素一共有h[i]种出管方式。要求n个元素的出管方式但是其中每一个元素从1到n都可能是最后一个出管的。假设第k个小球是最后一个出管的比k早入管且早出管有k-1个数一共有h[k-1]种出管方式比k晚入管且早出管有n-k个数一共有h[n-k]种出管方式。这种情况下一共就有h[k-1]*h[n-k]种出管方式。当k取不同值的时候产生的出管序列也是独立的。所以可以加起来。k的取值范围可以是从1到n。所以递推式是h(n)h(0)*h(n-1)h(1)*h(n-2)……h(n-1)*h(0),初始条件是h[0]h[1]1。
#includecstdio
int main(){int n,h[20]{1,1};scanf(%d,n);for(int i2;in;i){for(int j0;ji;j){h[i]h[j]*h[i-j-1];}}printf(%d,h[n]);return 0;
}
