文档章节

一个算法笔试题引发的思考---喝汽水问题

o
 osc_z1hvg4cu
发布于 2018/04/24 17:04
字数 1975
阅读 27
收藏 0

精选30+云产品,助力企业轻松上云!>>>

这是一道经典的喝汽水问题,根据问题的表述,有多种不同的场景,但是问题考察点都是一样的。
一、 问题引入
一瓶汽水单价2元,4个瓶盖可换一个汽水,2个空瓶可换一个汽水。给定金额得出一共能喝几瓶汽水?
二、 问题分析
1,金额是一次性的,全部买完汽水后就不能再买了,后续金额也不会添加
2,有两条规则,“4个瓶盖换汽水”和“2个空瓶换汽水”,这两条规则没有先后顺序。
3,对给定的金额没有具体限制,只需大于0就可以,这里考虑整数。
4,不考虑经济学思路,单纯数学角度(经济学思路是,比如4块钱,买2瓶汽水,然后用2个空瓶换一瓶汽水,这时喝了3瓶,再向老板借一个空瓶,加上剩下的一个空瓶换一瓶汽水,剩下空瓶还给老板,总共喝了4瓶)
 
三、 过程分析
1,拿到金额,算出金额可以买多少瓶汽水,同时可得到空瓶数量和瓶盖数量。
2,拿到空瓶数量,算出所有空瓶可换多少瓶汽水,这时剩余的空瓶数量是没有换的空瓶数量和换了汽水的数量,瓶盖数量为换前瓶盖数量加上换了汽水的数量,总共喝的汽水数量为上一步累加喝的数量加上这次换的汽水数量。
3,拿到瓶盖数量,算出所有瓶盖可换多少瓶汽水,这时剩余的瓶盖数量是没有换的瓶盖数量和换了汽水的数量,空瓶数量为换前空瓶数量加上换了汽水的数量,总共喝的汽水数量为上一步累加喝的数量加上这次换的汽水数量。
4,当空瓶数量或瓶盖数量满足换汽水条件时,分别执行2或3步骤,都不满足时,过程结束返回总共喝的汽水数量。
 
简单举例:
金额 步骤 总共汽水数量
1 第一步,当前喝汽水数量:0 ,空瓶数量: 0,瓶盖数量:0,已喝汽水数量: 0 0
2 第一步,当前喝汽水数量:1 ,空瓶数量: 1,瓶盖数量:1,已喝汽水数量: 1 1
3 第一步,当前喝汽水数量:1 ,空瓶数量: 1,瓶盖数量:1,已喝汽水数量: 1 1
4 第一步,当前喝汽水数量:2 ,空瓶数量: 2,瓶盖数量:2,已喝汽水数量: 2;第二步,当前喝汽水数量:1 ,空瓶数量: 2-2+1=1,瓶盖数量:2+1=3,已喝汽水数量: 2+1=3 3
5 第一步,当前喝汽水数量:2 ,空瓶数量: 2,瓶盖数量:2,已喝汽水数量: 2;第二步,当前喝汽水数量:1 ,空瓶数量: 2-2+1=1,瓶盖数量:2+1=3,已喝汽水数量: 2+1=3 3
6 第一步,当前喝汽水数量:3 ,空瓶数量: 3,瓶盖数量:3,已喝汽水数量: 3第二步(换空瓶),当前喝汽水数量:1 ,空瓶数量: 3-2+1=2,瓶盖数量:3+1=4,已喝汽水数量: 3+1=4第三步(换瓶盖),当前喝汽水数量:1 ,空瓶数量: 2+1=3,瓶盖数量:4-4+1=1,已喝汽水数量: 4+1=5第四步(换空瓶),当前喝汽水数量:1 ,空瓶数量: 3-2+1=2,瓶盖数量:1+1=2,已喝汽水数量: 5+1=6第五步(换空瓶),当前喝汽水数量:1 ,空瓶数量: 2-2+1=1,瓶盖数量:2+1=3,已喝汽水数量: 6+1=7 7
... ... ...
 
对金额为6的步骤
步骤 当前喝汽水数量 空瓶数量 瓶盖数量 总共喝汽水数量
1 3 3 3 3
2换空瓶 1 3-2+1=2 3+1=4 3+1=4
3换瓶盖 1 2+1=3 4-4+1=1 4+1=5
4换空瓶 1 3-2+1=2 1+1=2 5+1=6
5换空瓶 1 2-2+1=1 2+1=3 6+1=7
 
四、 抽象
 
针对以上步骤,按照抽象化思想,将过程如下表示:
这里抽象一个篮子概念,也可以理解成抽屉,里面存放空瓶数、瓶盖数、已喝数,首先要对篮子初始化,通过金额初始空瓶数、瓶盖数和已喝数,然后对篮子依次调用换空瓶和换瓶盖操作,对篮子里数量进行消耗。
 
五、 实现
通过以上分析,完成代码实现,代码git地址:https://github.com/zengfa1988/study/blob/master/src/main/java/com/tsh/exam/bottle/BottleReplaceTest.java
public static Integer getBottleDrink(Integer money){
        Integer drinkNum = money / 2;//已喝数量
        Integer emptyNum = drinkNum;//空瓶数量
        Integer capNum = drinkNum;//瓶盖数量
        Map<String,Integer> pocket = new HashMap<String,Integer>();
        pocket.put("drinkNum", drinkNum);
        pocket.put("emptyNum", emptyNum);
        pocket.put("capNum", capNum);
        
        while(emptyNum >=2 || capNum >=4){
            //调用空瓶替换方法消耗空瓶
            emptyBottleReplace(pocket);
            //调用瓶盖替换方法消耗瓶盖
            capReplace(pocket);
            emptyNum = pocket.get("emptyNum");
            capNum = pocket.get("capNum");
        }
        drinkNum = pocket.get("drinkNum");
        return drinkNum;
    }

 

 
/**
	 * 空瓶替换汽水
	 * @param pocket
	 */
	public static void emptyBottleReplace(Map<String,Integer> pocket){
		Integer emptyNum = pocket.get("emptyNum");
		if(emptyNum < 2){
			return;
		}
		Integer curDrinkNum = emptyNum / 2;//当前空瓶可替换汽水数量
		emptyNum = curDrinkNum + emptyNum % 2;
		pocket.put("emptyNum", emptyNum);
		//已喝数量累加
		Integer drinkNum = pocket.get("drinkNum");
		drinkNum = drinkNum + curDrinkNum;
		pocket.put("drinkNum", drinkNum);
		//瓶盖累加
		Integer capNum = pocket.get("capNum");
		capNum = capNum + curDrinkNum;
		pocket.put("capNum", capNum);
	}

 

/**
     * 瓶盖替换汽水
     * @param pocket
     */
    public static void capReplace(Map<String,Integer> pocket){
        Integer capNum = pocket.get("capNum");
        if(capNum < 4){
            return;
        }
        Integer curDrinkNum = capNum / 4;//当前空瓶可替换汽水数量
        capNum = curDrinkNum + capNum % 4;
        pocket.put("capNum", capNum);
        //已喝数量累加
        Integer drinkNum = pocket.get("drinkNum");
        drinkNum = drinkNum + curDrinkNum;
        pocket.put("drinkNum", drinkNum);
        //瓶盖累加
        Integer emptyNum = pocket.get("emptyNum");
        emptyNum = emptyNum + curDrinkNum;
        pocket.put("emptyNum", emptyNum);
    }

 

main方法调用:
public static void main(String[] args) {
        Integer drinkNum = getBottleDrink(10);
        System.out.println(drinkNum);
    }

 

 
五、 思考
1,在实际的项目中,规则可能会根据实际情况随时变动,考虑到灵活性,可以使用规则引擎,具体使用可参考规则引擎部分。
2,在上面的两条规则,消耗的属性是独立的,可加条规则消耗的属性重叠,比如1个空瓶和3个瓶盖换一瓶汽水,可添加如下方法:
/**
     * 1个空瓶和3个瓶盖换一瓶汽水
     * @param pocket
     */
    public static void capAndEmptyReplace(Map<String,Integer> pocket){
        Integer capNum = pocket.get("capNum");
        Integer emptyNum = pocket.get("emptyNum");
        if(emptyNum<1 || capNum<2){
            return;
        }
        Integer curDrinkNum = capNum / 3;//当前空瓶可替换汽水数量
        if(curDrinkNum > emptyNum){//如果瓶盖算的汽水数量大于空瓶数量,说明没有足够的空瓶同所有瓶盖消耗,则本次消耗为空瓶数量
            curDrinkNum = emptyNum;
        }
        capNum = capNum - curDrinkNum * 3;//剩余瓶盖数量
        pocket.put("emptyNum", emptyNum - curDrinkNum + curDrinkNum);
        pocket.put("capNum", capNum + curDrinkNum);
        //已喝数量累加
        Integer drinkNum = pocket.get("drinkNum");
        drinkNum = drinkNum + curDrinkNum;
        pocket.put("drinkNum", drinkNum);
    }

 

修改getBottleDrink方法:在capReplace后面添加capAndEmptyReplace方法
public static Integer getBottleDrink(Integer money){
        Integer drinkNum = money / 2;//已喝数量
        Integer emptyNum = drinkNum;//空瓶数量
        Integer capNum = drinkNum;//瓶盖数量
        Map<String,Integer> pocket = new HashMap<String,Integer>();
        pocket.put("drinkNum", drinkNum);
        pocket.put("emptyNum", emptyNum);
        pocket.put("capNum", capNum);
        
        while(emptyNum >=2 || capNum >=4 || (emptyNum >=1 && capNum>=3)){
            //调用空瓶替换方法消耗空瓶
            emptyBottleReplace(pocket);
            //调用瓶盖替换方法消耗瓶盖
            capReplace(pocket);
            //1个空瓶和3个瓶盖换一瓶汽水
            capAndEmptyReplace(pocket);
            emptyNum = pocket.get("emptyNum");
            capNum = pocket.get("capNum");
        }
        drinkNum = pocket.get("drinkNum");
        return drinkNum;
    }

 

但是这里有些问题,capAndEmptyReplace放在emptyBottleReplace前和后,跟capAndEmptyReplace放在capReplace后结果都不一样,也就是说 三条规则顺序执行结果不一样。
对整个思路再进行优化。
对某一个有着优先级的规则序列,先获得优先级高的规则方法,再调用获得的规则。
这里就不上代码了,直接看链接https://github.com/zengfa1988/study/blob/master/src/main/java/com/tsh/exam/bottle/MutilRuleBottleReplaceTest.java
通过以上分析,可考虑更高级应用,比如最优路径问题,最短时间问题等等。
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
1.27 华为上机测试题汽水瓶

title: 华为软件笔试---汽水瓶编程 localimage: image1 urlname: huawei-qishuiping categories: summary tags: [writen, exam] date: 2019-9-18 14:57:00 --- 摘要 更多文章请移步我的博客网......

竹风清
2019/10/08
0
0
1.27 华为上机测试题汽水瓶

---title: 华为软件笔试---汽水瓶编程localimage: image1urlname: huawei-qishuipingcategories: tags: [writen, exam] date: 2019-9-18 14:57:00 摘要 更多文章请移步我的博客网站: Porter.......

porterpan
2019/10/08
2
0
今天我们来聊聊递归喝汽水问题

君子食无求饱,居无求安,敏于事而慎于言,就有道而正焉,可谓好学也已 递归直通车 再识帝龟 面试题警告 题1解 题2解 最后 再识帝龟 大家好,我是帝龟,好久不见!!! 关于我的基本介绍,大...

古阙月
06/27
0
0
今天我们来聊聊递归喝汽水问题

君子食无求饱,居无求安,敏于事而慎于言,就有道而正焉,可谓好学也已 递归直通车 再识帝龟 面试题警告 题1解 题2解 最后 再识帝龟 大家好,我是帝龟,好久不见!!! 关于我的基本介绍,大...

osc_xrcp50yl
06/28
3
0
华为机试题-汽水瓶python实现

本来想着用递归或者其他算法实现,后来发现别人早就有更巧妙的方法解决问题了,唉,人生何尝不是如此呢,也许换个角度想想,山穷水尽也会变得柳暗花明了… 题目: 有这样一道智力题:“某商店...

osc_2kahpclc
01/11
2
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-11

更新时间: 2020-07-11 00:00 Scientists make precise edits to mitochondrial DNA for first time - (nature.com) 科学家首次对线粒体DNA进行精确编辑 得分:66 | 评论:4 LibreOffice: The N......

FalconChen
43分钟前
95
0
是否有可能从另一个git存储库中挑选一个提交? - Is it possible to cherry-pick a commit from another git repository?

问题: I'm working with a git repository that needs a commit from another git repository that knows nothing of the first. 我正在使用一个git存储库,需要从另一个不知道第一个存储库......

技术盛宴
昨天
26
0
【LeetCode】53 盛最多水的容器

题目 解题思路 双指针法: https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 代码 public class Solution { ......

JaneRoad
昨天
20
0
阿里云OSS配置CDN加速

首先购买CDN流量包 然后添加域名 添加好后 然后将域名OSS.xxxx.com 解析到 生成的CDN域名上 这样就完成了

可达鸭眉头一皱
昨天
16
0
js 整数与小数正则替换片段

说明 /(\d+)/g 整数 /(\d+\.\d+)rem/g 小数 /(\d+\.\d+|\d+)rem/g 其中 | 或 条件 例子 全局查找带 rem 单位的,替换成 px 单位 let text = text.replace(/(\d+\.\d+|\d+)rem/g, function(s......

DrChenXX
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部