Heim > Fragen und Antworten > Hauptteil
李白打酒
话说大诗人李白,一生好饮。幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。
注意:通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
我想到过暴力枚举,但是效果似乎不是很好。这个题用DFS算法解决是很好,但是不理解递归的使用。而且回溯的时候,也不知道这样能不能跑完所有情况。在此求助。
PHPz2017-04-17 15:19:05
这个问题用递归法可以得到答案是14:
bababaababbbbbb
babaabbabbabbbb
babaababbbbbabb
baabbbaabbabbbb
baabbabbbaabbbb
baabbabbabbbabb
baababbbbbababb
abbbabaabbabbbb
abbbaabbbaabbbb
abbbaabbabbbabb
abbabbbabaabbbb
abbabbbaabbbabb
abbabbabbbababb
ababbbbbabababb
除了正向递归,还可以反向递归:
正向:从(花,店,酒) = (0,0,2)
出发,递归到(10,5,0)
结束。
反向:从(10,5,0)
倒推,(10,5,0) -> (9,5,1) -> (8,5,2)
……直到(0,0,2)
结束。
试着手工推导两三步就会发现,倒推法可能更好。因为只有当酒量为偶数时,我们才需要考虑用店将酒量减半。而正推法每一步都要考虑花和店两种情况。实际执行也发现倒推法明显优于正推法。
下图是倒推法调用树。圆圈里的数字是每一步递推后的酒量,箭头上的字母 P(ub)=酒店,F(lowe)r=花。红色路径是符合要求的顺序。总递归调用149次(缓存中间结果,形式相同的调用只算一次)。
下图是正推法调用树,标识都省去了。总递归调用1051次,其中大部分调用都在做无用功。
迷茫2017-04-17 15:19:05
#include <cstdio>
int count=0;
void dfs(int a, int b, int wine) {
// printf("%d %d %d\n",a, b, wine);
if(!a && !b && wine == 1) count++;
else {
b--; wine--;
if(a >= 0 && b >= 0 && wine >= 1)
dfs(a, b, wine);
b++; wine++;
a--; wine *= 2;
if(a >= 0 && b >= 0 && wine >= 1)
dfs(a, b, wine);
a++; wine /= 2;
}
}
int main() {
int a=5, b=9, wine=2;
dfs(a, b, wine);
printf("%d\n",count);
return 0;
}
最后一次遇到花,且酒正好喝光,所以我们把最后的b固定,问题简化为5个a和9个b的条件排列,最后剩余1斗酒。
题中只有两种情况,当b-1时,wine-1,dfs进入下一层检查是否满足a=0,b=0且wine=1;当a-1时同理;
要注意的是,在b-1,wine-1,dfs进入下一层后,b和wine的值要改回来,否则会影响下面语句的执行。
巴扎黑2017-04-17 15:19:05
可以用二进制枚举子集来解.
int ans = 0;
for (int i = 0; i < (1<<14); ++i) {
int tot_1 = 0;
int tot_0 = 0;
int num = 2;
for (int j = 0; j < 14; ++j) {
if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1位是否为1
tot_1++;
num = num*2;
} else {
tot_0++;
num = num - 1;
}
}
if (tot_1 == 5 && tot_0 == 9 && num == 1) {
++ans; //记录合法方案书
}
}
以上解法是在计蒜客上蓝桥杯课程里面摘录的, 本人不是水军, 是计蒜客的一个普通学员, 看到 gmail sf推送然后偶遇这个问题. 故此来答, 题主要打蓝桥杯的话不妨考虑下加计蒜客的那个课程, 非常多的题, 也有 world final27名的老师带飞. 上面的那个链接是推广链接, 注册后双方各有优惠券的......