问题描述：
公园票价为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 }
运行结果如下:
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
