李白喝酒问题的算法


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

编程 C++ 算法

鹏翔二斋少年 10 years, 4 months ago

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种。

瀬能なつる answered 10 years, 4 months ago

Your Answer