首页 > 代码库 > 蓝桥杯——李白打酒（正式版）
蓝桥杯——李白打酒（正式版）
看了很多人对于此题的解题报告，对于他们的代码风格，我实在无法忍受，网上的代码大都是暴力求解——枚举，我自觉很无脑，但我得说，这是很简单的方法。我尽量优化了速度和代码可读性，原来的代码运行速度为（1 5 10）—— 3.5秒改进后变为2秒左右，暂时只能想到这些了，其他优化方法没有想到，暂时就先以此出为正式版，估计以后不会有很多改进，如果有更好的方法，可在下评论，我会及时整理
/×
Description
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店m次，遇到花n次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。
例如：这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
Input
输入一个整数T，包括T组数据，每组数据包括遇到店的次数m，花的次数n。
Output
对于每组数据，输出李白遇到店和花的可能次序的个数。
Sample Input
1 5 10
Sample Output
14
*/
原来的代码：
#include<stdio.h>
int sum;//可能的种数
int main()
{
int T;
scanf("%d",&T);
while(T--)//案例组数
{
sum=0;
int m,n;//m代表酒店，n代表花
scanf("%d%d",&m,&n);
void achol(int a,int m,int n);//递归函数声明
achol(2,m,n);调用
printf("%d\n",sum);
}
return 0;
}
void achol(int a,int m,int n)
{
if(a>0)//这行想必不用解说
{
if(m>0)遇酒店
achol(a*2,m-1,n);
if(n>0)//遇花
achol(a-1,m,n-1);
}
else if(a==0&&m==0&&n==0)//判断
sum+=1;
}
优化的代码：
#include<stdio.h>
int sum;//可能种数
int main()
{
int T;
scanf("%d",&T);//输入数据组数
while(T--)
{
sum=0;//每次输入数据将可能种数清零
int m,n;//m代表酒店，n代表花
scanf("%d%d",&m,&n);
void achol(int a,int m,int n);
achol(2,m,n);
printf("%d\n",sum);
}
return 0;
}
void achol(int a,int m,int n)
{
if(m>0&&n&&a)//遇见的只有两种可能，要么是酒店，要么是花
achol(a*2,m-1,n);
if(n>2&&a)
achol(a-1,m,n-1);
if(a==2&&m==0&&n==2)//最后两次都是花，可自己验证
sum+=1;
}
在此段代码中，我仍有几点不解：
一：若递归函数中所有的内容写成：
if(a>0)
{
if(m>0&&n)//遇见的只有两种可能，要么是酒店，要么是花
achol(a*2,m-1,n);
if(n>2)
achol(a-1,m,n-1);
if(a==2&&m==0&&n==2)//最后两次都是花，可自己验证
sum+=1;
}
理论上说，a的限制可改为a>=2,但是，改了后就不行了，sum永远为零，我考虑不周请各位好心指出；
二：
在一的基础上，我可在对m加限制，a*2<=n,即是说酒的总数不能超过n，在递归之前解决这个可能。但是加了也是出错的。
蓝桥杯——李白打酒（正式版）