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名的老師帶飛. 上面的那個鏈接是推廣鏈接, 註冊後雙方各有優惠券的..... .