李白打酒有什么解法

廿五
  • 17

李白打酒

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

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

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

回复
阅读 5.2k
4 个回答
✓ 已被采纳

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

leo126
  • 1
新手上路,请多包涵
#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的值要改回来,否则会影响下面语句的执行。

咱当年用的递归。

反正是个填空题。

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

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏