recherche

Maison  >  Questions et réponses  >  le corps du texte

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

李白打酒

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

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

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

PHPzPHPz2807 Il y a quelques jours1031

répondre à tous(4)je répondrai

  • PHPz

    PHPz2017-04-17 15:19:05

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

    répondre
    0
  • 迷茫

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

    répondre
    0
  • 迷茫

    迷茫2017-04-17 15:19:05

    咱当年用的递归。

    反正是个填空题。

    répondre
    0
  • 巴扎黑

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

    répondre
    0
  • Annulerrépondre