注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

李白喝酒问题的算法

OC/C/C++ 开心洋葱 2385次浏览 已收录 0个评论 手机上查看

“李白街上走,提壶去买酒,遇店加一倍,见花喝一斗”,途中,遇见5次店,见了10此花,壶中原有2斗酒,最后刚好喝完酒,要求最后遇见的是花,求可能的情况有多少种?

思路:

只是这一句“所以问题转化为把 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种。
用枚举加剪枝的方式,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++写的枚举代码:

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


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明李白喝酒问题的算法
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
开心洋葱,开心洋葱头,水墨

您必须 登录 才能发表评论!

……
加载中……