本文共 3029 字，大约阅读时间需要 10 分钟。
JAVA算法：李白遇花喝酒游戏JAVA DFS 算法设计
看到了这样的一道题目，还挺有意思，可以通过不同的算法设计来求解。
话说大诗人李白，一生好饮。一日，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
通过题目描述，我们可以获得信息：
于是题目可以简化为，李白从家里出来，有2斗酒，遇店5次，遇花9次，最后还剩1斗酒。
1. 采用递归算法
/* * 递归算法 */ public static int func(int bistro, int flower, int amount) { /* * 处理小酒馆数量、花的数量、酒的余量异常情况 * */ if (bistro < 0 || flower < 0 || amount < 0) { return 0; } if (bistro == 0 && flower == 1 && amount == 1) { return 1; // 保证最后一个遇见花并且把酒喝光 } // 逢店加一倍，遇花喝1斗 return func(bistro - 1, flower, 2 * amount) + func(bistro, flower - 1, amount - 1); } 完整的程序执行结果（递归算法）：
package com.bean.algorithmbasic;public class LiBaiHeJiu3 { private static int ANSWER = 0; public static void main(String[] args) { int answer=func(5,10,2); System.out.println("answer = " + answer); } /* * 递归算法 */ public static int func(int bistro, int flower, int amount) { /* * 处理小酒馆数量、花的数量、酒的余量异常情况 * */ if (bistro < 0 || flower < 0 || amount < 0) { return 0; } if (bistro == 0 && flower == 1 && amount == 1) { return 1; // 保证最后一个遇见花并且把酒喝光 } // 逢店加一倍，遇花喝1斗 return func(bistro - 1, flower, 2 * amount) + func(bistro, flower - 1, amount - 1); } } answer = 14
2. 采用DFS算法
/* * DFS算法设计： * 参数选择：amount代表酒量；bistro代表小酒馆；flower代表花；flag为标记 flag=0表示结束条件 * */ public static void dfs(int amount,int bistro,int flower,int flag) { if(bistro==0&&flower==0) { if(flag==0&&amount==0)//标记最后一次遇到的是花 { ANSWER++; } //return;//已经没有店家和花，此时不管是否情况正确，都退出递归 } if(bistro > 0) { //amount*2，满足条件逢店加倍；bistro-1：小酒馆数-1； dfs(amount*2,bistro-1,flower,1); //标记遇到的是店家 } if(amount > 0 && flower > 0) { //amount-1，满足条件逢花喝1斗；flower-1：遇到花的次数-1； dfs(amount-1,bistro,flower-1,0); // 标记遇到的是花 } } 完整的程序执行结果：
package com.bean.algorithmbasic;public class LiBaiHeJiu2 { private static int ANSWER=0; public static void main(String[] args) { /* * 调用DFS算法，设定条件 * 初始时酒2都，遇到5次店，10次花，最后就没有了，设定标记为flag=0 */ dfs(2,5,10,0); System.out.println("ANSWER = "+ANSWER); } /* * DFS算法设计： * 参数选择：amount代表酒量；bistro代表小酒馆；flower代表花；flag为标记 flag=0表示结束条件 * */ public static void dfs(int amount,int bistro,int flower,int flag) { if(bistro==0&&flower==0) { if(flag==0&&amount==0)//标记最后一次遇到的是花 { ANSWER++; } //return;//已经没有店家和花，此时不管是否情况正确，都退出递归 } if(bistro > 0) { //amount*2，满足条件逢店加倍；bistro-1：小酒馆数-1； dfs(amount*2,bistro-1,flower,1); //标记遇到的是店家 } if(amount > 0 && flower > 0) { //amount-1，满足条件逢花喝1斗；flower-1：遇到花的次数-1； dfs(amount-1,bistro,flower-1,0); // 标记遇到的是花 } } } ANSWER = 14
转载地址：http://cntdi.baihongyu.com/