蓝桥杯-找钱问题

2018-06-18 03:52:25来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

问题描述:

  公园票价为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 }


 

 运行结果如下:

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:随笔

下一篇:HashTree【转】