【备战蓝桥杯】【递归】【C语言】【排队购票问题】

刺骨的言语ヽ痛彻心扉 2022-10-27 06:21 187阅读 0赞

问题描述：  
售票工作正在进行，每张票为50元，现在有m+n人排队等待购票，其中有m人手持50元，n人手持100元，假设售票处不设找零，那么若想使售票处不会出现找不开零钱的局面，请你帮忙设计不同的排队方案。特别说明的是，拿同样面值的人对换位置为同一种方案。

算法分析：  
一：n=0; 那么说明买票的人都是手持50元，所以不会出现找不开零钱的局面，所以这是一种排队方案；  
二：m=0; 那么说明买票的人都是手持100元，所以一定会找不开零钱，所以没有排队方案；  
三：m<n; 那么说明买票的人中，手持50元的人数少于手持100元的人数，所以肯定会出现找不开零钱的局面，所以同样没有排队方案；  
四：m>n; 此时，买票的人中，手持50元的人数多于手持100元的人数，所以可以有排队方案，我们这里来分析一下第m+n人的位置：  
（1）：第（m+n）人手持100元站在第（m+n-1）人的后面，那么他之前的人有(m)人手持50元，有(n-1)人手持100元，此种情况共有f(m,n-1)种排队方式；  
（1）：第（m+n）人手持50元站在第（m+n-1）人的后面，那么他之前的人有(m-1)人手持50元，有(n)人手持100元，此种情况共有f(m-1,n)种排队方式；

所以通过第（m+n）人就可以分析出递归关系为：

f(m,n)=f(m-1,n)+f(m,n-1)

边界条件： 当m<n时，f(m,n)=0; 当n=0时，f(m,n)=1; 当 m=0时，f(m,n)=0;

#include<bits/stdc++.h>
    using namespace std;
    int paidui(int m,int n){
        //m人手持50元，n人手持100元
        int ans=0;
           if(n==0) return 1;//
          else if(m<n||m==0) return 0;
          else
            ans=paidui(m,n-1)+paidui(m-1,n);
             return ans;
    
    }
    int main(){
        
           int m,n;
           cin>>m>>n;
           //cout<<paidui(m,n);
           printf("排队种类%d",paidui(m,n));
    
    
    return 0;}