c++ - 李白喝酒问题的算法
“李白街上走，提壶去买酒，遇店加一倍，见花喝一斗”，途中，遇见5次店，见了10此花，壶中原有2斗酒，最后刚好喝完酒，要求最后遇见的是花，求可能的情况有多少种？希望大家分享一下思路，谢谢！
我的思路很混乱，觉得直接暴力枚举能解决，但是枚举所有的情况比较不现实，希望大家解答啊!
“李白街上走，提壶去买酒，遇店加一倍，见花喝一斗”，途中，遇见5次店，见了10此花，壶中原有2斗酒，最后刚好喝完酒，要求最后遇见的是花，求可能的情况有多少种？希望大家分享一下思路，谢谢！
我的思路很混乱，觉得直接暴力枚举能解决，但是枚举所有的情况比较不现实，希望大家解答啊!
巴扎黑2017-04-17 11:24:48
henix's idea is very good, but there is a slight problem with this sentence "So the problem is transformed into dividing 8 into five powers of 2", which misses combinations similar to 12311 (that is, it misses the possible +3 situation).
The situation of adding 3 buckets of wine will be triggered in the following situation: when the current amount of wine is 2 buckets, Yudian increases it to 4 buckets, Yuhua drinks one bucket, and now there are 3 buckets, and Yudian increases it to 3 buckets. So in this combination, 3 must be next to 2, and behind 2, which is equivalent to "23" bundled together. In this case, there are C(4,1) = 4 ways. The total answer is C(5,2)+C(4,1), which is 14 ways.
黄舟2017-04-17 11:24:48
Drink 1 dou each time you see a flower. Since there were 2 dou at the beginning, you saw a total of 10 flowers, which means you drank 10 dou in total. Therefore, the increase in wine due to meeting the store is 8 buckets.
So the problem is transformed into dividing 8 into 5 powers of 2, that is, considering how many buckets are added each time you meet the store. There are two types:
1 1 2 2 2
1 1 1 1 4
But it is impossible for 4 to appear directly without 2, so only 1 1 2 2 2 is feasible.
So the question is transformed into how many ways can these 5 numbers 1 1 2 2 2 be arranged, a total of C(5,2) = 10 ways.
天蓬老师2017-04-17 11:24:48
It should be acceptable to use enumeration and pruning for such a problem. The python code I wrote below:
#! /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
It seems that the original poster uses C++, and that path can be implemented using stack. Supplement the running results (14 types in total):
['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中文网2017-04-17 11:24:48
Hey... everyone posts their own code, and they don’t talk about important optimization ideas
After looking through it, I almost couldn’t find any reliable explanation of optimization ideas in the answers. If this were me in an interview, almost no one here would give me the answers that I expected to score 60 points...
For the convenience of description, define it 李白(x, y, z) => There are also answers to x flowers, y shops, and z drinks
Let’s talk about the unimportant things first. The pruning conditions can be more radical than your answers. For example, when z > x is drunk and you can’t finish it, you can prune it. Similarly, when z * (2 ^ y) < x is pruned, you can prun it immediately. If you don’t have enough wine, you can cut it off.
The most obvious feature of this question is that it has a scale, and the answer to the large-scale version is closely related to the answer to the small-scale version, that is, it is known 李白(x, y, z), and we will know it right away李白(x+1, y, z+1) or 李白(x, y+1, 2z) answers.
I don’t know if anyone here can remember the Fibonacci sequence and the corresponding classic computer algorithm dynamic programming. Dynamic programming is a very classic space-for-time algorithm that can instantly transform the most clumsy violent recursive algorithm for this type of problem into an algorithm with quite good performance.
In fact, if dynamic programming is not used, the recursive algorithm for this type of problem will quickly collapse as the scale increases. The exact number of O is left to the algorithm teacher. Anyway, it must be exponential. Dynamic programming can basically be reduced to the polynomial level in the future
Finally give me my implementation, um, JS
http://jsfiddle.net/e3Ns4/
_.memoize(fn, hasher) is a helper in underscore. Its function is to generate a new function. When calling, it will first use haser to calculate a hash, and then cache the result in this hash. The same hash value will not be called next time. fn, that is, dynamic programming. I copied the source code
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));
};
}
高洛峰2017-04-17 11:24:48
I want to give you an exhaustive idea~ Actually it doesn’t require many steps~
First, recurse
Start with 2 buckets, 5 hotels, 10 flowers;
Everything upstairs is complete...
Provide optimization conditions
If the hotel is finished and the buckets and flowers are not equal, you can exit;
You can also exit if the bucket is bigger than the flowers;
If the number is 0, exit directly;
The flower is zero, but I quit before reaching 15 steps;
大家讲道理2017-04-17 11:24:48
Well...the code is as follows (python version):
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))
Executionw(2,5,10) Result14
怪我咯2017-04-17 11:24:48
I couldn’t write it myself, so I asked a master to write the enumeration code:
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;
}
迷茫2017-04-17 11:24:48
Let me make a haskell recursive version
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
PHPz2017-04-17 11:24:48
Give you a piece of code that is easier to understand, using recursion:
#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 ] = '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;
}
阿神2017-04-17 11:24:48
I wrote it roughly first, and just debugged it, but there are still some problems. It has been tortured by him for two hours. Let’s take a rest and come back to debug later!
It turned out that after debugging for a long time, it was not as simple as I thought, and no one prompted me. It took me about half an hour today to finally find the problem!
#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;
}
Updated version, passed the test:
#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;
}