李白打酒
话说大诗人李白,一生好饮。幸好他从不开车。 一天,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱: 无事街上走,提壶去打酒。 逢店加一倍,遇花喝一斗。 这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。 请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。 注意:通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
我想到过暴力枚举,但是效果似乎不是很好。这个题用DFS算法解决是很好,但是不理解递归的使用。而且回溯的时候,也不知道这样能不能跑完所有情况。在此求助。
这个问题用递归法可以得到答案是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次(缓存中间结果,形式相同的调用只算一次)。
![](http://img.php.cn/upload/image/000/000/000/071816d4e7f72c2aa6130746706b23af-0.gif)
下图是正推法调用树,标识都省去了。总递归调用1051次,其中大部分调用都在做无用功。
![](http://img.php.cn/upload/image/000/000/000/55d7e75acd149f3f383e768b90713c30-1.gif)
最后一次遇到花,且酒正好喝光,所以我们把最后的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的值要改回来,否则会影响下面语句的执行。
咱当年用的递归。
反正是个填空题。
可以用二进制枚举子集来解.
以上解法是在计蒜客上蓝桥杯课程里面摘录的, 本人不是水军, 是计蒜客的一个普通学员, 看到 gmail sf推送然后偶遇这个问题. 故此来答, 题主要打蓝桥杯的话不妨考虑下加计蒜客的那个课程, 非常多的题, 也有 world final27名的老师带飞. 上面的那个链接是推广链接, 注册后双方各有优惠券的......