极客观点
项目管理
HarmonyOS
“李白街上走，提壶去买酒，遇店加一倍，见花喝一斗”，途中，遇见5次店，见了10此花，壶中原有2斗酒，最后刚好喝完酒，要求最后遇见的是花，求可能的情况有多少种？希望大家分享一下思路，谢谢！
我的思路很混乱，觉得直接暴力枚举能解决，但是枚举所有的情况比较不现实，希望大家解答啊!
李白喝酒问题的算法
阅读 18.3k
每见一次花喝 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 种。
这样的问题用枚举加剪枝的方式应该是可以接受的吧，下面我写的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
哎……大家都各贴各的代码，也不说说重要的优化思路
翻了一下还几乎没在答案里找到靠谱的优化思路解说，如果这是我在面试的话这里的答案几乎没人到我心理预估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的
_.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));
};
}
我想一个穷举的思路吧~其实不用很多步骤的~
首先要递归
开始2斗，5酒店，10花；
楼上都完整了...
提供优化条件吧
如果酒店完了，并且斗和花不等，就能退出；
如果斗大于花也能退出；
斗已经是0直接退出；
花是零，但没到15步也退出；
额...代码如下(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
自己写不来，让某大神写的枚举代码：
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;
}
让我来个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
给你一段更容易理解的代码，用递归做的：
#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;
}
自己先粗略的写了一下，刚调试了一下，还是有点问题，已经被他折磨了两个小时了，先休息会儿等会儿再来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;
}
新手上路，请多包涵
"""
这是今年蓝桥杯java中的一道填空题，当时我还以为做对了，写了33
结果我忽略了最明显的判断条件，5次店和10次花，少了下面的 check1 函数
简直为自己的智商捉鸡，加了之后就是14了，
最近学python，现用python实现这题，跟大家分享
"""
count=0;
def check(t):
sum = 2;
for ch in t:
if ch=='1':
sum=sum*2;
if ch=='0':
sum=sum-1;
return sum;
def check1(t):
c = 0;
for ch in t:
if(ch=='1'):
c+=1;
if c==5:
return True;
return False;
def f(t):
if(len(t)==15):
if check(t)==0 and t[14:15]=='0' and check1(t):
global count;
count+=1;
print(" ".join(t));
return;
f(t+'1');
f(t+'0');
f('');
print(count);
简单的给一个非递归的python代码：
queue = [(2, 5, 10)]
total = 0
def iter():
global queue
while queue:
i, queue = queue[0], queue[1:]
yield i
for (left, dian, hua) in iter():
if dian == 0:
total += 1 if left == hua else 0
else:
if left > hua or left == 0 or hua ==0:
continue
queue.append((left*2, dian-1, hua))
queue.append((left-1, dian, hua-1))
新手上路，请多包涵
暴力穷举很好做，不再说了
最后一次是见花的话，2经过说明经过14次变换之后值是1,
10次见花之后是0的话，初始是2斗酒，说明一共加了8斗酒
加酒最小值是1，最大是4(11114)，
因为加酒是加倍方法，数列中相邻两个数倍差不能大于2倍，即11114这类被排除，可能加酒的数字在1-3的范围内,同样因为倍差原因,1后面只能是2(但是3后面可是是1)
因为初期值是2,第一次加酒只可能是1或者2斗
于是找有几个满足条件的数列就行
被 1 篇内容引用
推荐问题
云服务器上的Http服务器在8080端口无法从外部访问？
在云服务器上写一个linux上运行的Http服务器时，绑定了任意IP和8080端口，云服务器上的telnet是能直接和这个服务器交互的，但是在浏览器 或者 在我windows上的telnet不能连接这个Http服务器(云服务器的公网ip可以ping通)浏览器向服务器发请求时，我是会把请求的报文全打印出来的，这里没打印是没有连接上我的防火墙全部...2 回答1.7k 阅读✓ 已解决
http协议后端设置了Set-Cookie，前端无法接收到？
后端设置了Set-Cookie: {代码...} 打印出来的response报文也是有set-cookie的但是前端vue这里怎么也接收不到 {代码...} 根本没有这个headers我也允许第三方cookie了，跨域也允许了，httpOnly也删过了也没用，怎么办？求大佬解惑......2 回答1k 阅读✓ 已解决
开发QT项目，可以只学习QML，不学习C++语言吗？
开发QT项目的话，请问：1、可以只学习QML，不学习C++语言吗？2、是否可以指使用QML而不使用Widget?3、QML开发的QT程序，是否性能会比不过Widget开发的呢？如果比不过，会损失多少性能？1 回答1.6k 阅读✓ 已解决
如何在C++中嵌入Python实现混编解决算法问题及效率是否提高？
每种语言并没有好坏之分，但是各具优势，我们为什么不可以采用混编的方式。将问题分成小问题，交给各个语言擅长的地方，例如：矩阵的运算可以使用python的库函数解决。再将结果传回c++方面（c++的运转效力要比python大约高4倍），那我该如何配环境？这样又是否真的提高效率了？那我又该如何证明算法提高了呢？1 回答1.1k 阅读✓ 已解决
为什么使用scanf和printf时输出数据不符合预期？
using namespace std;int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); printf("%d %d",b,c); return 0; }会输出的是变量a的数值1 回答948 阅读
关于c++的一个封闭类的问题 ?
为什么要在 Car 的无参构造函数中 调用 CTyre(); ???? 就算不写 CTyre(); ， 程序也是会默认调用 CTyre 类的无参构造函数的啊 ！！！1 回答1.1k 阅读
请问AI推理加速有推荐的书吗？
请问AI推理加速有推荐的书吗？学习路线是什么？1 回答1.4k 阅读
宣传栏
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种。