精华内容
下载资源
问答
  • 一、N个数依次入栈,出栈顺序有多少种? 我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出: f(1) = 1 //即 1 f(2) = 2 //即 12、21 ...

     一、N个数依次入栈,出栈顺序有多少种?

    我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:

                                         f(1) = 1     //即 1

                                         f(2) = 2     //即 12、21

                                         f(3) = 5     //即 123、132、213、321、231

    然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。

    分析:

     1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3);

     2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2),根据乘法原理,一共的顺序个数为f(1) * f(2);

     3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),根据乘法原理,一共的顺序个数为f(2) * f(1);

     4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即f(3);结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);

    为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:

    f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)

    然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:

    f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)

    即:

     

           但这只是一个递推公式(若编程实现,需要维护一个一维数组,时间复杂度为O(n^2))。怎么把它转化为通项公式呢,复杂度仅为O(1)?

           有这么一个公式:C(2n,n)/(n+1) (C(2n,n)表示2n里取n),并且有个名字叫Catalan数。

     二、Catalan数

    1、是什么?

          卡特兰数是一种经典的组合数,经常出现在各种计算中,其前几项为 : 
          1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,  58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

    2、 计算公式

    卡特兰数一般的计算公式:这里写图片描述 
    另类递推公式:C(n)=C(n-1)*((4*n-2)/(n+1));
    Cn的另一个表达形式为 
    所以,Cn是一个自然数,这一点在先前的通项公式中并不显而易见。 
    这个表达形式也是André对前一公式证明的基础。

    3、一般性质

    卡塔兰数满足以下递推关系 


    它也满足 
     
    这提供了一个更快速的方法来计算卡塔兰数。

    卡塔兰数的渐近增长为 
    它的含义是左式除以右式的商趋向于1当n → ∞。(这可以用n!的斯特灵公式来证明。)

    所有的奇卡塔兰数Cn都满足n = 2^k − 1。 
    所有其他的卡塔兰数都是偶数。
     

    4、实际问题的解决

    经典问题:

    给出一个n,要求一个长度为2n的01序列,使得序列的任意前缀中1的个数不少于0的个数, 
    以下为长度为6的序列: 
    111000 101100 101010 110010 110100 

    证明:

           令1表示进栈,0表示出栈,则可转化为求一个2n位,含n个1,n个0的二进制数, 满足从左往右扫描到任意一位时,经过的0数不多于1数 。显然含n个1,n个0的2n位二进制数共有个,下面考虑不满足要求的数目。
           考虑一个含n个1,n个0的2n位二进制数,扫描到第2m+1位上时有m+1个0和m个1(容易证明一定存在这样的情况), 
    则后面的01排列中必有n-m个1和n-m-1个0 
    将2m+2及其以后的部分0变成1,1变成0,则对应一个n+1个0和n-1个1的二进制数 
    反之亦然(相似的思路证明两者一一对应) 


    从而 

    Cn表示有n+1个叶子的二叉树的个数 


    Cn表示所有不同构的含n个分枝结点的满二叉树的个数(一个有根二叉树是满的当且仅当每个结点都有两个子树或没有子树)。Cn表示所有在n × n格点中不越过对角线的单调路径的个数 。
    一个单调路径从格点左下角出发,在格点右上角结束,每一步均为向上或向右 ,计算这种路径的个数等价于计算Dyck word的个数(同问题1): X代表“向右”,Y代表“向上” 


    Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数 
    下图中为n = 4的情况: 


    Cn表示对{1, …, n}依序进出栈的置换个数 。一个置换w是依序进出栈的当S(w) = (1, …, n), 
    其中S(w)递归定义如下:令w = unv,其中n为w的最大元素,u和v为更短的数列 。再令S(w) =S(u)S(v)n,其中S为所有含一个元素的数列的单位元。

    Cn表示集合{1, …, n}的不交叉划分的个数. 其中每个段落的长度为2。Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数 。下图为 n = 4的情况: 


    5、总结最典型的四类应用:
    (实质上却都一样,无非是递归等式的应用,就看你能不能分解问题写出递归式了)

    (1)括号化问题。

      矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)

    (2)出栈次序问题。


      一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?   

    //模拟过程如下,dfs来填充入栈和出栈的标志
    #include<iostream> 
    #include<cstring>
    #include<cstdio>
    #include<stack>
    #define N 100
    using namespace std;
    
    int a[N];
    int p[2*N];
    int pre[2*N];
    int used[2*N];
    int index[2*N];//如果a[i]==1,那么表示第index[i]个数入栈 
    int n;
    int cnt;//记录多少个出栈的序列 
    
    int C(int n){
        int ans=1;
        int m = 2*n;
        int nn = n;
        for(int i=1; i<=n; ++i){
            ans *= m--;
            ans /= i;
        }
        return ans/(nn+1);
    }
    
    void solve(){
        memset(pre, 0, sizeof(pre));
        memset(used, 0, sizeof(used));
        int prek = 0;
        for(int i=1; i<=2*n; ++i){
            if(a[i] == 1){
                pre[i] = prek;
                prek = i;
            } else {
                int ii = prek;
                while(used[ii]) 
                    ii = pre[ii];
                cout<<p[index[ii]]<<" ";//出栈 
                used[ii] = 1;
                pre[prek] = pre[ii];
            }
        }
        cout<<endl;
    }
    
    void solve1(){
        stack<int>s;
        int k=1;
        for(int i=1; i<=2*n; ++i){
            if(a[i] == 1)
                s.push(p[k++]);
            else {
                cout<<s.top()<<" ";
                s.pop();
            }
        }
        cout<<endl;
    }
    
    void dfs(int k, int cnt0, int cnt1){
        if(k>2*n){
            //solve(); 
            solve1(); 
            ++cnt; 
            return ;
        }
        if(cnt1<n){//入栈 
            a[k] = 1;
            index[k] = cnt1+1;//第几个数入栈 
            dfs(k+1, cnt0, cnt1+1);
        }
        if(cnt0<cnt1){//出栈 
            a[k] = 0;
            dfs(k+1, cnt0+1, cnt1);
        }
    }
    
    int main(){
        cin>>n;
        for(int i=1; i<=n; ++i) 
            cin>>p[i];
        dfs(1, 0, 0);
        cout<<endl<<"模拟个数:"<<cnt<<endl;
        cout<<"公式个数:"<<C(n)<<endl;
        return 0;
    }


      类似: 
      1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)   

    
    //  CSDN.卡特兰数:售票序列问题
    
    // n = 0 时,队列为空,可以认为只有一种;
    
    // n = 1 时,队列:5 ,10  共有1种;
    
    // n = 2 时 ,队列: 5, 10,5,10
    
    //                         5,5,10,10   共有两种
    
    // n = 3时, 队列:5,5,5,10,10,10
    
    //                         5,5,10,5,10,10
    
    //                         5,5,10,10,5,10
    
    //                         5,10,5,5,10,10
    
    //                         5,10,5,10,5,10    共有5种;
    
    // 我门可以认为符合卡特兰数,1,1,2,5,14,42.。。
    
    #include <iostream>
    
    #include <vector>
    
    #include <string>
    
    using namespace std;
    
    
    void genAns(int left, int right, string path, vector<string> &ans){
    
        if(left == 0 && right == 0){  //规则一
    
            path.pop_back(); 
    
            ans.push_back(path);
    
        }
    
        if(left != 0)                 //规则二
    
            genAns(left - 1, right, path + "5-", ans);
    
        if(right != 0 && left < right)      //规则三
    
            genAns(left, right - 1, path + "10-", ans);
    
    }
    
    
    int main(int argc, const char * argv[]) {
    
        // insert code here...
    
        int n;
    
        while(cin>>n){
    
            string path;
    
            vector<string> ans;
    
            genAns(n, n, path, ans);
    
            for(int i = 0; i < ans.size(); i++)
    
                std::cout << ans[i] <<endl;
    
            cout<<"count: "<<ans.size()<<endl;
    
        }
    
        return 0;
    
    }
    

          2)在圆上选择2n个点,将这些点成对连接起来,使得所得到的n条线段不相交的方法数。 

    (3)将多边行划分为三角形问题

      将一个凸多边形区域分成三角形区域的方法数? 
      类似:一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 
      类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 

    import java.math.*;
    import java.util.*;
    public class Main {
    	public static void main(String[] args) {
    		int n,t;
    		int i;
    		BigInteger x,y;
    		Scanner in=new Scanner(System.in);
    		BigInteger []a=new BigInteger[110];
    		a[0]=BigInteger.valueOf(1);
    		a[1]=BigInteger.valueOf(1);
    		
    		for(i=2;i<101;i++) {
    			x=a[i-1];
    			x=x.multiply(BigInteger.valueOf(4*i-2));
    			y=x.divide(BigInteger.valueOf(i+1));
    			a[i]=y;
    		}
    		
    		while(in.hasNext()) {
    			n=in.nextInt();
    			if(n==-1)
    				break;
    			System.out.println(a[n]);
    		}
    	}
    	 
    }
    

     

    (4)给顶节点组成二叉树的问题。 

           给定N个节点,能构成多少种形状不同的二叉树? 
      先去一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(0)*h(n-1) + h(2)*h(n-2) +…+ h(n-1)h(0)=h(n)(能构成h(N)个)

    import java.math.*;
    import java.util.*;
    public class Main {
    	public static void main(String[] args) {
    		int n,t;
    		int i;
    		BigInteger x,y;
    		Scanner in=new Scanner(System.in);
    		BigInteger []a=new BigInteger[110];
    		a[0]=BigInteger.valueOf(1);
    		a[1]=BigInteger.valueOf(1);
    		
    		for(i=2;i<101;i++) {
    			x=a[i-1];
    			x=x.multiply(BigInteger.valueOf(4*i-2));
    			y=x.divide(BigInteger.valueOf(i+1));
    			a[i]=y;
    		}
    		
    		while(in.hasNext()) {
    			n=in.nextInt();
    			System.out.println(a[n]);
    		}
    	}	
     
    }
    

     

     

    展开全文
  • 把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包含数字 2 和 4,一共有多少种不同的分解方法? 注意交换 3 个整数的顺序被视为同一方法,例如 1000+1001+18 和1001+1000+18 被视为同一。 ...

    问题描述

    把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包含数字 2 和 4,一共有多少种不同的分解方法?
    注意交换 3 个整数的顺序被视为同一种方法,例如 1000+1001+18 和1001+1000+18 被视为同一种。
    答案提交

    这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

    输入
    没有输入。

    输出
    输出一个整数。

    思路
    很简单喽,三重循环遍历判断就行了,种数的问题即使会做也特别容易出错,注意题目中的条件, 不要想当然,不要添油加醋,就不会出错,注意以下几点:

    • 题目说是不相等的正整数,所以不包括0,三个数也不相等。
    • 三个整数顺序调换视为同一种方法。
    • 当然最主要的还是相加等于2019和不包括2和4。

    代码呈上;

    #include <stdio.h>
    
    int judge(int n) {
    	int flag = 1;
    //	if(n%10==2 || n%10==4 ||(n/10)%10==2 || (n/10)%10==4 ||(n/100)%10==2 || (n/100)%10==4 || (n/1000)%10==2 || (n/1000)%10==4)
    //		flag=0;
    	//第二种判断方法,推荐!
    	while(n>0) {
    		int k=n%10;
    		if(k==2 || k==4) {
    			flag = 0;
    		}
    		n/=10;
    	}
    	return flag;
    }
    
    int main () {
    	int i,j,k;
    	int num = 0;
    	for(i= 1; i<=2019; i++) {
    		for(j=i+1; j<=2019; j++) {
    			for(k=j+1; k<=2019; k++) {
    				if(i+j+k==2019) {
    
    
    					if(judge(i)==1 && judge(j)==1 && judge(k)==1) {
    						num++;
    
    					}
    				}
    			}
    		}
    	}
    
    	printf("%d",num);
    	return 0;
    }
    

    答案:40785

    展开全文
  •  f(1) = 1 f(2) = 2 f(3) = 5 然后我们来考虑f(4), 我们给4个元素编号为1,2,3,4, 那么考虑:元素1出栈顺序可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如1234,元素1就在1号位置...
    我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:

      f(1) = 1

      f(2) = 2

      f(3) = 5

      然后我们来考虑f(4), 我们给4个元素编号为1,2,3,4, 那么考虑:元素1出栈顺序可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如1234,元素1就在1号位置)。

      分析:

      1) 如果元素1在1号位置,那么只可能1进栈,马上出栈,此时还剩元素2、3、4等待操作,就是子问题f(3);

      2) 如果元素1在2号位置,那么一定有一个元素比1先出栈,即有f(1)种可能顺序(只能是2),还剩3、4,即f(2),     根据排列组合,一共的顺序个数为f(1) * f(2);

      3) 如果元素1在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是2、3),还剩4,即f(1),

      根据排列组合,一共的顺序个数为f(2) * f(1);

      4) 如果元素1在4号位置,那么一定是1先进站,最后出栈,那么元素2、3、4的出栈顺序即是此小问题的解,即         f(3);

      结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);

      为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:

      f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)

      然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:

      f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)

      即

      260x81

    F[n]=∑(i=0,i<=n-1)F[i]*F[n-i](显然初始条件为F[0]=1,F[1]=1)
    

    n个元素的情况可分为三个阶段,先进i个元素入栈出栈(有F[i]种情况),然后第i+1个元素直接入栈出栈,再n-(i+1)个元素入栈出栈(F[n-i-1]种情况),所以是F[i]*F[n-i-1]种情况,显然i的取值范围是[0,n-1],累加即是结果。


    这个的结果有数学公式的 是C(n,2n)-C(n-1,2n),至于公式怎么来,必须将问题转化为数学问题“卡塔兰数”(Catalan).程序员的做法是用递归,要想写出效率高的程序,就得用这个数学问题推导出来的公式.

     

    #include <iostream>
    #include<cstring>
    using namespace std;
    int popnumber(int num)
    {
    	int sum=0;
    	if (num == 0 || num == 1)
    		return 1;
    	else if (num == 2)
    		return 2;
    	for (int i = 0; i < num; i++)
    	{
    		sum += popnumber(i)*popnumber(num-1-i);
    	}
    
    	return sum;
    }
    int main(int argc, char** argv)
    {
    	int len;
       //	string str;
       //	cout<<"输入入栈的元素:"
       // cin>>str;
       // len=str.length(); 
        cout<<"输入入栈元素个数:"; 
        cin>>len;	 
        cout<<"出栈可能结果为:"<<popnumber(len)<<endl;
       return 0;
    }
    
    
    
    
    
    
    
    
    

    展开全文
  • n个元素进栈,共有多少种出栈顺序

    万次阅读 多人点赞 2018-07-03 19:52:14
    2) 如果元素a在2号位置,那么一定一个元素比a先出栈,即f(1)可能顺序(只能是b),还剩c、d,即f(2), 根据乘法原理,一共顺序个数为f(1) * f(2); 3) 如果元素a在3号位置,那么一定两个元素比1先出栈,...

    1.基于栈的问题分析

    我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:

                                      f(1) = 1     //即 1

                                      f(2) = 2     //即 12、21

                                      f(3) = 5     //即 123、132、213、321、231


    然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。

    分析:


    1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3);

    2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2),     根据乘法原理,一共的顺序个数为f(1) * f(2);

    3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),

        根据乘法原理,一共的顺序个数为f(2) * f(1);

    4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即f(3);


    结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);

    为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:

    f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0) 


    然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:

    f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)


     



    但这只是一个递推公式(若编程实现,需要维护一个一维数组,时间复杂度为O(n^2))。怎么把它转化为通项公式呢,复杂度仅为O(1)?

    2. 相关的求解方法

    (1)非常规数值分析

    对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。

    在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。

    不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。

    反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。

    因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。

    显然,不符合要求的方案数为c(2n,n+1)。

          由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)。其中,n为节点的个数。

    (2)从图像上分析

    事实上,可以认为问题是,任意两种操作,要求每种操作的总次数一样,且进行第k次操作2前必须先进行至少k次操作1。我们假设一个人在原点,操作1是此人沿右上角45°走一个单位(一个单位设为根号2,这样他第一次进行操作1就刚好走到(1,1)点),操作2是此人沿右下角45°走一个单位。第k次操作2前必须先进行至少k次操作1,就是说明所走出来的折线不能跨越x轴走到y=-1这条线上!在进行n次操作1和n此操作2后,此人必将到到达(2n,0)!若无跨越x轴的限制,折线的种数将为C(2n,n),即在2n次操作中选出n次作为操作1的方法数。

    折线法

    现在只要减去跨越了x轴的情况数。对于任意跨越x轴的情况,必有将与y=-1相交。找出第一个与y=-1相交的点k,将k点以右的折线根据y=-1对称(即操作1与操作2互换了)。可以发现终点最终都会从(2n,0)对称到(2n,-2)。由于对称总是能进行的,且是可逆的。我们可以得出所有跨越了x轴的折线总数是与从(0,0)到(2n,-2)的折线总数。而后者的操作2比操作1要多0-(-2)=2次。即操作1为n-1,操作2为n+1。总数为C(2n,n-1)。(此处类似于上面的数值角度分析)

    折线法

    (3)卡特兰数介绍

    令h(0)=1,h(1)=1,catalan数满足递推式[1]

    h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)

    例如:h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

    h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

     

    递推关系的解为:

    h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
    递推关系的另类解为:
    h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)

    3.类似的问题

    (1)买票找零

    有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)

    (2)一个有n个1和n个-1组成的字串,且前k个数的和均不小于0,那这种字串的总数为多少?

    (3)饭后,姐姐洗碗,妹妹把姐姐洗过的碗一个一个地放进碗橱摞成一摞。一共有n个不同的碗,洗前也是摞成一摞的,也许因为小妹贪玩而使碗拿进碗橱不及时,姐姐则把洗过的碗摞在旁边,问:小妹摞起的碗有多少种可能的方式?

    最终结果:C(2n,n)-C(2n,n+1)

    展开全文
  • n个元素进栈,共有多少种出栈顺序

    千次阅读 2017-03-22 11:11:21
    3个元素进栈,5出栈顺序,那么一个很自然地问题就是n个元素进栈,共有多少种出栈顺序? 记得原来做过这道题,当时只是记了个公式并没有深究,这次在网上搜到了一个完美解答; 转载自:...
  • 一共有n个不同的碗,洗前也是摞成一摞的,也许因为小妹贪玩而使碗拿进碗橱不及时,姐姐则把洗过的碗摞在旁边,问:小妹摞起的碗有多少种可能的方式? 2.给定n个数,有多少种出栈序列? 3.一个n个1和n个-1组成的...
  • N个数依次入栈,出栈顺序有多少种

    千次阅读 2017-08-14 21:48:21
    2) 如果元素a在2号位置,那么一定一个元素比a先出栈,即f(1)可能顺序(只能是b),还剩c、d,即f(2), 根据乘法原理,一共顺序个数为f(1) * f(2); 3) 如果元素a在3号位置,那么一定两个元素比1先出栈...
  • n个元素进栈,共有多少种出栈顺序?

    千次阅读 2014-06-04 10:44:03
    复习数据结构看到栈的时候,看到一个有意思的问题:n个元素依次进栈,共有多少种出栈顺序?  (其实结果是一个“卡塔兰数”Catalan,C(2n,n)/(n+1) ,在组合数学中介绍)  发现1个元素进栈,1出栈顺序...
  • 有关堆栈和Catalan数的思考...问题的由来:编号为 1 到 n 的 n 个元素,顺序的进入一个栈,则可能的出栈序列有多少种? 对问题的转化与思考:n 个元素进栈和出栈,总共要经历 n 次进栈和 n 次出栈。这就相当于对这 2
  • 举例说明,共有一个1,2,3,4四个数,入栈方式 1入,2入,3入,4入,4出,3出,2出,1出 故出栈顺序4,3,2,1 1入,1出,2入,3入,4入,4出,3出,2出 故出栈顺序1,4,3,2 1入,1出,2入,2出,3入,4入,...
  • n个元素进栈,共有多少种出栈顺序(公式)

    万次阅读 多人点赞 2017-03-08 23:44:13
    出栈顺序 1 1 2 2 3 5 … … n ? 然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号...
  • 如果元素a在2号位置,那么一定一个元素比a先出栈,即f(1)可能顺序(只能是b),还剩c、d,即f(2), 根据乘法原理,一共顺序个数为f(1) * f(2); 如果元素a在3号位置,那么一定两个元素比1先出栈,即...
  • 第十届蓝桥杯省赛题:把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包含数字 2 和 4,一共有多少种不同的分解方法?题目我的思路上代码心得体会这次的纠错过程整个就俩字儿 题目 【问题描述】 ...
  • 一:暴力(这个可以) #include using namespace std; int main() { cout"00000"; cout"00001"; cout"00010"; cout"00011"; cout"00100"; cout"00101"; co
  • C语言_04 三程序结构 顺序, 选择(分支), 循环结构

    万次阅读 多人点赞 2018-02-06 18:31:49
    在C语言程序中,一共有程序结构:顺序结构、选择结构(分支结构)、循环结构; 顺序结构,从头到尾一句接着一句的执行下来,直到执行完最后一句; 选择结构,到某个节点后,会根据一次判断的结果来决定之后向哪...
  • 动态规划之n个元素出栈顺序种

    千次阅读 2016-04-19 17:25:24
    n个元素依次进栈,共有多少种出栈顺序? 算法分析 1个元素进栈,1出栈顺序;2个元素进栈,2出栈顺序;3个元素进栈,5出栈顺序 我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出: f...
  • 0,4,9,21从上面四个数字中选出三个,一共有多少组合?不重复的 0,4,9和0,9,4和4,9,0都算相同的 gfx3.2-狼人杀(228446613) 15:04:39你们可以这么想 如果说 取出的数 前后顺序无所谓的话 从四个里面取3个 就相当于 ...
  • 这个问题属于卡特兰数( h(n)=C(2n,n)/(n+1) (n=1,2,3,...) ...括号配对有多少种配对方式也是这种问题,其实配对方式正确问题也可以简化为堆栈进出栈问题来进行解决,然后用卡特兰数来进行解决即可。  
  • 线程一共有状态?

    千次阅读 2019-02-19 14:43:44
    一、线程的6中状态: 1、New(初始) 2、Runnable ...1、顺序执行线程,代码片段如下   五:synchronized 存在哪里? synchronized 保存在对象头(对象在内存里的布局->对象头)里
  • 中国字一共有多少个?

    千次阅读 2007-01-17 23:19:00
    在国外,聊天的时候,老外经常会问到这个问题“中国字一共有多少个” ,依稀不知在哪里看到的,回答“常用的一般4-5千,一共可能3,4万多”。刚好在百度的知道里面看到一个较详细的解答,随手拷过来好了。说文解字》...
  • 对于长度为5位的一个01串,每一位都可能是0或1,一共有32可能。它们的前几个是: 00000 00001 00010 00011 00100 请按从小到大的顺序输出这3201串。 输入格式 本试题没有输入。 输出格式 输出32行,按...
  • 红黄蓝白黑五颜色的小球若干个,每次从里面任意取三个小球,总共有多少种取法 2.问题分析 1.首先,题中所描述的是一次性取三小球,所以不考虑取的顺序问题,对于所给的五中球进行编号为 0,1,2,3,4,分别代表...
  • 那么,星球大战相关的电影,电视剧,动画一共有哪些?又应该按照各种顺序观看? 观看顺序分为两,一是按照真实的上映顺序,第二是按照故事时间线,即是在星战世界里,历史和事件发生的顺序。 真实的上映时间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 127,256
精华内容 50,902
关键字:

一共有多少种顺序