这是一道经典的喝汽水问题, 根据问题的表述, 有多种不同的场景, 但是问题考察点都是一样的.
一, 问题引入
一瓶汽水单价 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/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/BottleReplaceTest2.java
通过以上分析, 可考虑更高级应用, 比如最优路径问题, 最短时间问题等等.
posted on 2018-04-24 17:04 天行者之眼 阅读 (...) 评论 (...) 编辑 收藏
来源: https://www.cnblogs.com/zengfa/p/8931711.html