递归求组合数和递推求一般性问题的practice

梦里梦外; 2022-03-30 03:19 191阅读 0赞

### 考新郎 ###

Time Limit: 1000 ms Memory Limit: 32768 KiB

[Submit][] [Statistic][] [Discuss][]

Problem Description

在一场盛大的集体婚礼中,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:

![1021.gif][]

首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;  
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.  
最后,揭开盖头,如果找错了对象就要当众跪搓衣板...  
  
看来做新郎也不是容易的事情...  
  
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1 < M <= N <= 20)

Output

对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。

Sample Input

2
    2 2
    3 2

Sample Output

1
    3

/**
        本题既用到了递归也用到了递推
        需要用递归计算组合数同时也要用递推计算错排数
        题号：1021
    
        **/ 
    
        #include<stdio.h>
        #include<stdlib.h>
    
        //递归计算组合数(从N个数中选出M 个数的算法))
        long long int C(int n,int m){
            if(m==0){
                return 1;
            }else if(n==1){
                return 1;
            }else if(m==n){
                return 1;
            }else {
                //注意这个地方用递归   分治法(如果第一个位置选中了  那么剩余的m-1个在剩余 的n-1个位            
      置上选，否则
                //在剩余的n-1个位置上选m个数  两种情况相加即可)
                return (C(n-1,m-1)+C(n-1,m));
            }
        }
    
    
    
        //用递推公式计算m个数的错排，同见烽火台那个题
        long long int sum(int m){
            long long int s[25];
            s[0]=s[1]=0;
            s[2]=1;
            if(m<=2){
                return s[m];
            }
            for(int i=3;i<=m;i++){
                s[i]=(i-1)*(s[i-1]+s[i-2]);
            }
            return s[m];
        }
    
    
        int main(){
            int  t;
            scanf("%d",&t);
            while(t--){
                int m,n;
                scanf("%d %d",&n,&m);
                long long int summ,x1,x2;
    
                x1=C(n,m);
        //        printf("x1时%lld\n",x1);
                x2=sum(m);
                summ=x1*x2;
                printf("%lld\n",summ);
            }
    
            return 0;
        }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/1021.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/status/pid/1021.html
[Discuss]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Discuss/discusslist/pid/1021.html
[1021.gif]: http://acm.sdut.edu.cn/image/1021.gif