蓝桥杯-找钱问题

问题描述：

　　公园票价为5角。假设每位游客只持有两种币值的货币：5角、1元。再假设持有5角的有m人，持有1元的有n人。由于特殊情况，开始的时候，售票员没有零钱可找。我们想知道这m+n名游客以什么样的顺序购票则可以顺利完成购票过程。显然，m < n的时候，无论如何都不能完成；m>=n的时候，有些情况也不行。比如，第一个购票的乘客就持有1元。请计算出这m+n名游客所有可能顺利完成购票的不同情况的组合数目。

注意：只关心5角和1元交替出现的次序的不同排列，持有同样币值的两名游客交换位置并不算做一种新的情况来计数。

问题分析：

　　对于此题，采用递归思想，我们可以从最后一个人购票开始考虑，假设（m+n-1）个人已经买好票了，对于第m+n个人他有两种买票情况，持5角买票，或持1元买票，因此得到关系式solve(m-1,n)或solve(m,n-1),f是购票函数，而对于第（m+n-1）个人，因为已经假设此时（m+n-2）个人已买好票了，则其买票情况也有两种，持5角买票，或持1元买票，....，最后当第二个人买票时，他有两种买票情况，持5角买票，或持1元买票，最后直到第一个人，也同上述所述。

　　接下来，我们研究函数出口:

　　在买票过程中，如果m<n，则一定买票失败，这是第一种递归出口，则直接return。

　　观察第二个人买票情况可以发现，如果他持的是5角(m=1)，则第一个人一定持的是1元，因为m>=n,此时n一定为1，此时只有一种情况，...51，这是第二种递归出口，则count++，再执行return。

　    当买票的人中，持有的是1元的人都没有了，此时剩下的人都持有5角，则只有一种情况，...5555，才能使关系式成立,这是第三种递归出口，count++，再执行return。

代码描述：

 1 #include<stdio.h>
 2 int count=0;
 3 void solve(int m,int n){
 4     /*
 5     m表示持有5角的人数，n表示持有1元的人数 
 6     以最后一个人为研究点 
 7     */
 8     if(m<n) return;//人数减少过程中,m<n则不无法找钱，递归出口 
 9     if(m==1){//当倒数第二个人为5角时，只有一种情况....51 
10         count++;
11         return;
12     }
13     if(n==0)//当1元的人数为0时，只有一种情况...55555... 
14     {
15         count++;
16         return;
17     }
18     /*各return起到函数结束的作用*/ 
19     solve(m-1,n);//5角的人买票
20     solve(m,n-1);//1元的人买票 
21 
22 } 
23 int main(){
24     solve(3,2);
25     printf("%d",count);
26     return 0;
27 }

 

 运行结果如下: