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

Question

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

Answer 1

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 2

每见一次花喝 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 3

这样的问题用枚举加剪枝的方式应该是可以接受的吧，下面我写的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

Answer 4

哎……大家都各贴各的代码，也不说说重要的优化思路

翻了一下还几乎没在答案里找到靠谱的优化思路解说，如果这是我在面试的话这里的答案几乎没人到我心理预估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 5

我想一个穷举的思路吧~其实不用很多步骤的~
首先要递归
开始2斗，5酒店，10花；
楼上都完整了...
提供优化条件吧
如果酒店完了，并且斗和花不等，就能退出；
如果斗大于花也能退出；
斗已经是0直接退出；
花是零，但没到15步也退出；

Answer 6

额...代码如下(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 7

自己写不来，让某大神写的枚举代码：

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<<cnt<<endl;
    return 0;
}

Answer 8

让我来个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

Answer 9

给你一段更容易理解的代码，用递归做的：

#include <iostream>
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 ] = '\0';
        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 10

自己先粗略的写了一下，刚调试了一下，还是有点问题，已经被他折磨了两个小时了，先休息会儿等会儿再来debug！
结果debug了好久，也没我想的那么简单，也没人提示，今天又花了半个小时左右的时间，终于找到了问题的所在！

#include <iostream>

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 <iostream>

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;
}