题目
标题：李白打酒
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
题目分析
关于方案数量的问题往往都是使用深搜. 使用递归实现深搜可以使我们不必关心遍历的具体过程, 只需要把题目中给出的条件转换成程序语言即可.
根据题目信息, 变量有”店”, “酒”和”花”, 因此我们的递归函数必须包含这三个变量, 即:
void f(int dian, int hua, int jiu)...
根据”逢店加一倍，遇花喝一斗。”可以得出如下两个对函数 f() 自身进行调用的语句:
if(遇到店){
f(dian-1,hua,jiu*2);
}
if(遇到花){
f(dian,hua-1,jiu-1);
}
递归的边界是遇到了 5 次店, 10 次花, 并且最后酒喝光了, 即:
dian==0&&hua==0&&jiu==0
但是上面的分析过程 (对递归边界的定义) 是存在错误的. 我们根据上面的分析过程可以写出下面这个 (错误的) 程序:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int ans=0;
void f(int dian, int hua, int jiu){
if(dian>0&&jiu>=0){
f(dian-1,hua,jiu*2);
}
if(hua>0&&jiu>=1){
f(dian,hua-1,jiu-1);
}
if(dian==0&&hua==0&&jiu==0){
ans++;
}
}
int main(){
f(5,10,2);
cout<<ans<<endl;
return 0;
}
上面这个程序的运行结果是:
27
“27”看上去也”像是”一个正确答案. 但是, 如果我们仔细分析题目就会发现, 上面这个程序没有满足题目中给出的下面这个条件:
已知最后一次遇到的是花，他正好把酒喝光了
也就是说, 李白最后一次遇到的是花, 而且在刚遇到的花的时候, 他的酒壶里还剩 1 斗酒, 随后”遇花喝一斗”把酒壶里面的酒都喝光了. 至此, 李白一共遇到了 5 次店, 10 次花, 并且喝完了全部的酒.
但是, 在上面的程序中, 计算的仅仅是李白”遇到了 5 次店, 10 次花, 并且喝完了全部的酒”, 存在李白最后连续遇到了两次花, 每次喝一斗, 最后把酒喝完的情况, 也存在李白最后连续遇到了四次花, 每次喝一斗, 最后把酒喝完的情况(题目中没有提到酒壶容量的上限).
为了满足这个”已知最后一次遇到的是花，他正好把酒喝光了”的条件, 我们先把最后一次遇到花并喝一斗酒的情况减去, 这样只需要计算李白遇到 5 次店, 9 次花, 并剩下了 1 斗酒有多少种情况就可以了, 正确的程序如下:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int ans=0; //定义全局变量用于计数
void f(int dian, int hua, int jiu){
/*模拟李白遇到店的情况
若要遇到店, 则剩下的店的数量必须大于 0
遇到店的时候, 剩下的花的数量不变但必须不为负数
遇到店之前不能把酒壶里面的酒喝成负数*/
if(dian>0&&jiu>=0&&hua>=0){
f(dian-1,hua,jiu*2);
}
/*模拟李白遇到花的情况
若要遇到花, 则剩下的花的数量必须大于 0
遇到花的时候, 剩下的店的数量不变但必须不为负数
遇到花之前酒壶里面的酒至少要剩 1 斗以便于遇到花时喝*/
if(hua>0&&jiu>=1&&dian>=0){
f(dian,hua-1,jiu-1);
}
if(dian==0&&hua==0&&jiu==1){
ans++;
}
}
int main(){
f(5,9,2);
cout<<ans<<endl;
system("pause");
return 0;
}
本题正确答案:
14