安徽房和城乡建设部网站,wordpress媒体库 插件,推广一个网站需要什么,o2o模式是什么意思通俗讲题目
有一个单端封闭的管子#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;
}
