c++ - 李白喝酒问题的算法

Question

“李白街上走，提壶去买酒，遇店加一倍，见花喝一斗”，途中，遇见5次店，见了10此花，壶中原有2斗酒，最后刚好喝完酒，要求最后遇见的是花，求可能的情况有多少种？希望大家分享一下思路，谢谢！
我的思路很混乱，觉得直接暴力枚举能解决，但是枚举所有的情况比较不现实，希望大家解答啊!

巴扎黑 · Answer

henix的思路非常好，只是這一句「所以問題轉化為把 8 拆成 5 個 2 的冪」略有問題，漏掉了類似12311的組合（即漏掉了可能＋3的情形）。
加3鬥的狀況會在以下情境中觸發：當前酒為2鬥時候，遇店加至4鬥，遇花喝掉一鬥，此時有3鬥，再遇店加3鬥。所以這個組合中3必須緊鄰2，在2的後面，相當於"23"捆綁在一起。此種情況下有C(4,1) = 4種。總答案為C(5,2)＋C(4,1)為14種。

黄舟 · Answer

每見一次花喝 1 鬥，由於最開始有 2 鬥，總共見了 10 次花，說明總共喝了 10 鬥。所以因為遇見店而增加的酒為 8 鬥。

所以問題轉換成把 8 拆成 5 個 2 的冪，也就是考慮每次遇見店增加多少鬥。有兩種：

1 1 2 2 2
1 1 1 1 4

但是沒有 2 直接出現 4 是不可能的，所以只有 1 1 2 2 2 是可行的。

所以問題轉換為 1 1 2 2 2 這 5 個數字有多少種排列方法，共 C(5,2) = 10 種。

天蓬老师 · Answer

這樣的問題用枚舉加上剪枝的方式應該是可以接受的吧，下面我寫的python程式碼：

#! /usr/bin/env python
# *-* coding: utf-8 -*-

dou = 2
dian = 5
hua = 10
num = 0
def walk(dou, dian, hua, path):
    global num
    if dou < 0 or dian < 0 or hua < 0:
        return
    if dou == 1 and dian == 0  and hua == 1:
        print path
        num += 1
    walk(dou+dou, dian-1, hua, path + ['dian']) #遇到店
    walk(dou-1, dian, hua-1, path + ['hua']) # 遇到花

walk(dou, dian, hua, [])
print num

似乎樓主用C++，那個路徑可以stack實作。補充一下運行結果（共14種）：

['dian', 'hua', 'dian', 'hua', 'hua', 'hua', 'hua', 'hua', 'dian', 'hua', 'dian', 'hua', 'dian', 'hua']
['dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua', 'dian', 'hua', 'dian', 'hua']
['dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua', 'dian', 'dian', 'hua', 'hua', 'hua', 'dian', 'hua']
['dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua', 'dian', 'hua', 'dian', 'dian', 'hua', 'hua', 'hua']
['dian', 'hua', 'hua', 'hua', 'dian', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua', 'dian', 'hua']
['dian', 'hua', 'hua', 'hua', 'dian', 'dian', 'hua', 'hua', 'hua', 'dian', 'dian', 'hua', 'hua', 'hua']
['dian', 'hua', 'hua', 'hua', 'dian', 'hua', 'dian', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua']
['hua', 'dian', 'dian', 'hua', 'dian', 'hua', 'hua', 'hua', 'hua', 'hua', 'dian', 'hua', 'dian', 'hua']
['hua', 'dian', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua', 'dian', 'hua']
['hua', 'dian', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua', 'dian', 'dian', 'hua', 'hua', 'hua']
['hua', 'dian', 'dian', 'hua', 'hua', 'hua', 'dian', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua']
['hua', 'dian', 'hua', 'dian', 'dian', 'hua', 'dian', 'hua', 'hua', 'hua', 'hua', 'hua', 'dian', 'hua']
['hua', 'dian', 'hua', 'dian', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'dian', 'hua', 'hua', 'hua']
['hua', 'dian', 'hua', 'dian', 'hua', 'dian', 'dian', 'hua', 'dian', 'hua', 'hua', 'hua', 'hua', 'hua']
14

PHP中文网 · Answer

哎…大家都各貼各的程式碼，也不說說重要的最佳化思路

翻了一下還幾乎沒在答案裡找到可靠的優化思路解說，如果這是我在面試的話這裡的答案幾乎沒人到我心理預估60分……

為了方便描述，定義一下李白(x, y, z) => 還有x次花，y次店，z鬥酒的答案

先說不重要的吧，剪枝條件是可以比各位的答案更激進一些的，比如z > x的時候玩命喝也喝不完了可以剪，同理z * (2 ^ y) < x的時候即使馬上狂打酒也不夠喝了可以剪。

正文分隔線

這個問題最明顯的特徵就是有規模，並且大規模版本的答案是和小規模版本的答案密切相關的，也就是已知李白(x, y, z)，我們馬上就能知道李白(x+1, y, z+1) 或李白(x, y+1, 2z)的答案。
不知道到這裡有沒有人能想起菲波納契數列和對應的經典電腦演算法動態規劃。動態規劃是非常經典的空間換時間的演算法，可以把這類問題最笨拙的暴力遞歸演算法瞬間改造成性能相當良好的演算法。

實際上，不用動態規劃的話，這類問題的遞歸演算法會很快隨著規模的增長而崩潰,具體O多少還給算法老師了，反正肯定是逆天指數級的。動態規劃以後基本上可以降到多項式等級

最後給我的實現，嗯，JS的

http://jsfiddle.net/e3Ns4/

_.memoize(fn, hasher)是underscore裡的一個helper，作用是產生一個新的函數，呼叫時會先用haser計算一個hash，然後把結果緩存在這個hash裡，下次相同hash值就不調用fn了，也就是動態規劃。原始碼我抄過來

  function (func, hasher) {
    var memo = {};
    hasher || (hasher = _.identity);
    return function() {
      var key = hasher.apply(this, arguments);
      return _.has(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
    };
  }

高洛峰 · Answer

我想一個窮舉的思路吧~其實不用很多步驟的~
首先要遞歸
開始2鬥，5飯店，10花；
樓上都完整了...
提供最佳化條件吧
如果飯店結束了，並且鬥和花不等，就能退出；
如果鬥大於花也能退出；
鬥已經是0直接退出；
花是零，但沒到15步也退出；

大家讲道理 · Answer

額...代碼如下(python版)：

def w(f,d,h): return (1 if f==h else 0) if d==0 else (0 if f*h==0 or f>h else w(f*2, d-1, h)+w(f-1, d, h-1))

執行w(2,5,10) 結果14

怪我咯 · Answer

自己寫不來，讓某大神寫的枚舉碼：

int main()
{
    int cnt=0;
    for (int i=0; i<1<<15; i++)
    {
        int k=2;
        int n=0;
        int x=i;
        int flag=1;
        for (int j=1; j<=15; j++)
        {
            if (x&1)
                k*=2;
            else
                k--;
            if (k==0&&x)
            {
                flag=0;
                break;
            }
            n+=x&1;
            x>>=1;
        }
        if ( n !=5 || (i & (1<<14)) || !flag || k != 0)
            continue;
        cnt++;
    }
    cout<

迷茫 · Answer

讓我來個haskell遞歸版的

drink :: Int -> Int -> Int -> Int
drink 1 0 1 = 1
drink wine inn flower
 | wine < 0 = 0
 | inn < 0 = 0
 | flower < 0 = 0
 | otherwise = drink (wine-1) inn (flower-1) + (drink (wine*2) (inn-1) flower)

*Main> drink 2 5 10
14

PHPz · Answer

給你一段比較容易理解的程式碼，用遞迴做的：

#include 
using namespace std;
int count = 0;
int path[ 20 ];

void dfs( int m, int n, int r, int c )//m 遇店的次数，n 遇花的次数
{
    if( m < 0 || n < 0 || r < 0 )
        return ;
    if( m ==0 && n == 0 && r == 1 )
    {
        path[ c ] = 'rrreee';
        cout << path << endl;
        count++;
    }
    path[ c ] = 'a';
    dfs( m -1 , n, r * 2, c + 1 ); 
    path[ c ] = 'b';
    dfs( m, n - 1, r - 1 , c + 1 ); 
}

int main() 
{
    dfs( 5, 9, 2, 0 );
    cout << count << endl;
    return 0;
}

阿神 · Answer

自己先粗略的寫了一下，剛調試了一下，還是有點問題，已經被他折磨了兩個小時了，先休息會兒等會兒再來debug！
結果debug了好久，也沒我想的那麼簡單，也沒人提示，今天又花了半小時左右的時間，終於找到了問題的所在！

#include 

using namespace std;

int counting = 0;
int A[15];
int sum = 2;

int  collectArray()
{
int collect = 0;
for(int i =0;i<15;++i)
{
    if(A[i] == 0)
    collect++;
}
return collect;
}

void enumAll(int pos)
{
if(pos == 15)
{
    if(sum ==0 && A[14] == 1 )
    {
        counting++;
    }
}else{
    if(collectArray() <= 5)
    {
        A[pos] = 0;
        sum *= 2;
        enumAll(pos+1);
        A[pos] = 1;
        sum -= 1;
        enumAll(pos+1);
    }
    /*if(   <= 10)
    {
        A[pos] = 1;
        enuAll(pos+1);
        A[pos] = 0;
        enumAll(pos+1);
    }*/
    }
}

int main()
{
    for(int i =0;i<15;++i)
    {
        A[i] = -1;
    }
    enumAll(0);
    cout << counting;
    return 0;
}

更新版本,已通過測試：

#include 

using namespace std;

int counting = 0;
int A[15];
int sum = 2;

int  collectArray()
{
    int collect = 0;
    for(int i =0;i<15;++i)
    {
        if(A[i] == 0)
        collect++;
    }
    return collect;
}

void enumAll(int pos,int sonSum)
//直接采用枚举方法，A[]中每个元素不是0就是1
//若采用if判断则会产生15层嵌套
//因此采用树的深度优先遍历
//建议我使用栈来操作
//问题已经被发现，我TMD就是个天才，sum是个全局变量，在递归的时候，已经变不回来    //了！
{
    if(pos == 15)
    {
        if(sonSum == 0 && A[14] == 1 &&  collectArray() == 5)
        {
            counting++;
            for(int i =0;i<15;++i)
            cout << A[i] << "  ";
            cout << endl;
            return;
        }
    }else{
        //if(collectArray() <= 5)
            A[pos] = 0;
            sonSum  *= 2;
            enumAll(pos+1,sonSum);
            A[pos] = 1;
            sonSum = sonSum / 2;
            sonSum -= 1;
            enumAll(pos+1,sonSum);
            return;
    //}
    /*if(   <= 10)
    {
        A[pos] = 1;
        enuAll(pos+1);
        A[pos] = 0;
        enumAll(pos+1);
    }*/
    }
}

int main()
{
    for(int i =0;i<15;++i)
    {
        A[i] = -1;
    }
    enumAll(0,sum);
    cout << counting << endl;
    return 0;
}

c++ - 李白喝酒问题的算法

全部回覆(13)我來回復

正文分隔線