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

Question

李白打酒

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

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

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

Answer 1

这个问题用递归法可以得到答案是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次，其中大部分调用都在做无用功。

Answer 2

#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的值要改回来，否则会影响下面语句的执行。

Answer 3

咱当年用的递归。

反正是个填空题。

Answer 4

可以用二进制枚举子集来解.

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名的老师带飞. 上面的那个链接是推广链接, 注册后双方各有优惠券的......