c++ - 李白打酒有什么解法

问题描述

问 题

李白打酒

话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

我想到过暴力枚举，但是效果似乎不是很好。这个题用DFS算法解决是很好，但是不理解递归的使用。而且回溯的时候，也不知道这样能不能跑完所有情况。在此求助。

解决方案

这个问题用递归法可以得到答案是14：

1. bababaababbbbbb

2. babaabbabbabbbb

3. babaababbbbbabb

4. baabbbaabbabbbb

5. baabbabbbaabbbb

6. baabbabbabbbabb

7. baababbbbbababb

8. abbbabaabbabbbb

9. abbbaabbbaabbbb

10. abbbaabbabbbabb

11. abbabbbabaabbbb

12. abbabbbaabbbabb

13. abbabbabbbababb

14. 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次，其中大部分调用都在做无用功。

这篇关于c++ - 李白打酒有什么解法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！