蓝桥杯-找钱问题
2018-06-18 03:52:25来源:未知 阅读 ()
问题描述:
公园票价为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【转】
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
- 用C++实现:完美的代价 2020-04-15
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 用C++实现:FJ的字符串打印 2020-04-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash