c++ - 李白打酒有什么解法-PHP中文网问答

讲师中心微信公众号

首页

文章

后端开发 web前端数据库开发工具 php框架常见问题人工智能 Java 系统教程电脑教程硬件教程手机教程软件教程游戏教程自媒体新闻

专题

后端开发 web前端数据库开发工具 php框架人工智能 Java 系统教程电脑教程硬件教程手机教程软件教程游戏教程新闻

AI工具

AI 聊天问答 Agent智能体 AI 文本写作 AI 绘画作图 AI 设计工具 AI 视频创作 AI 音频制作 AI 办公学习 AI 编程开发 AI 提示词

学习

大前端后端开发数据库移动端运维开发计算机基础

编程手册

大前端后端开发数据库移动端运维开发计算机基础

下载

js特效网站源码工具下载类库下载网站素材学习资源插件扩展手机游戏

最近更新

c++ - 李白打酒有什么解法

PHPz 2017-04-17 15:17:05

[C++讨论组]

1292

李白打酒

话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

我想到过暴力枚举，但是效果似乎不是很好。这个题用DFS算法解决是很好，但是不理解递归的使用。而且回溯的时候，也不知道这样能不能跑完所有情况。在此求助。

PHPz

学习是最好的投资！

全部回复(3)

迷茫2017-04-17 15:19:05 3楼

#include <cstdio>

int count=0;

void dfs(int a, int b, int wine) {
//    printf("%d %d %d\n",a, b, wine);
    if(!a && !b && wine == 1) count++;
    else {
        b--; wine--;
        if(a >= 0 && b >= 0 && wine >= 1)
            dfs(a, b, wine);
        
        b++; wine++;
        
        
        a--; wine *= 2;
        if(a >= 0 && b >= 0 && wine >= 1)
            dfs(a, b, wine);
        
        a++; wine /= 2;
    }
}

int main() {
    int a=5, b=9, wine=2;
    
    dfs(a, b, wine);
    
    printf("%d\n",count);
    return 0;
}

最后一次遇到花，且酒正好喝光，所以我们把最后的b固定，问题简化为5个a和9个b的条件排列，最后剩余1斗酒。
题中只有两种情况，当b-1时，wine-1，dfs进入下一层检查是否满足a=0，b=0且wine=1；当a-1时同理；
要注意的是，在b-1，wine-1，dfs进入下一层后，b和wine的值要改回来，否则会影响下面语句的执行。

赞 +0

添加回复

迷茫2017-04-17 15:19:05 2楼

咱当年用的递归。

反正是个填空题。

赞 +0

添加回复

巴扎黑2017-04-17 15:19:05 1楼

可以用二进制枚举子集来解.

int ans = 0;
for (int i = 0; i < (1<<14); ++i) {
    int tot_1 = 0;
    int tot_0 = 0;
    int num = 2;
    for (int j = 0; j < 14; ++j) {
        if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1位是否为1
            tot_1++;
            num = num*2;
        } else {
            tot_0++;
            num = num - 1;
        }
    }
    if (tot_1 == 5 && tot_0 == 9 && num == 1) {
        ++ans; //记录合法方案书
    }
}

以上解法是在计蒜客上蓝桥杯课程里面摘录的, 本人不是水军, 是计蒜客的一个普通学员, 看到 gmail sf推送然后偶遇这个问题. 故此来答, 题主要打蓝桥杯的话不妨考虑下加计蒜客的那个课程, 非常多的题, 也有 world final27名的老师带飞. 上面的那个链接是推广链接, 注册后双方各有优惠券的......

赞 +0

添加回复

专题推荐

更多>

热门话题

热门教程

更多>