当前位置: 代码迷 >> 综合 >> JAVA算法:李白遇花喝酒游戏JAVA DFS 算法设计
  详细解决方案

JAVA算法:李白遇花喝酒游戏JAVA DFS 算法设计

热度:25   发布时间:2024-01-15 19:30:33.0

JAVA算法:李白遇花喝酒游戏JAVA DFS 算法设计

看到了这样的一道题目,还挺有意思,可以通过不同的算法设计来求解。

话说大诗人李白,一生好饮。一日,他提着酒壶,从家里出来,酒壶中有酒2斗。他边走边唱:
 无事街上走,提壶去打酒。
 逢店加一倍,遇花喝一斗。
 这一路上,他一共遇到店5次,遇到花10次,已知最后一次遇到的是花,他正好把酒喝光了。 
 请你计算李白遇到店和花的次序,可以把遇店记为a,遇花记为b。则:babaabbabbabbbb 就是合理的次序。

像这样的答案一共有多少呢?请你计算出所有可能方案的个数(包含题目给出的)。


问题分析

通过题目描述,我们可以获得信息:

  • 初始条件:酒壶中有酒2斗
  • 逢店加一倍,遇花喝一斗
  • 遇到店5次,遇到花10次
  • 最后一次遇到的是花,喝光了酒壶中的酒(隐含信息是酒壶中剩余的1斗酒被喝光了,结束)。

于是题目可以简化为,李白从家里出来,有2斗酒,遇店5次,遇花9次,最后还剩1斗酒。


算法设计

1. 采用递归算法

	/** 递归算法*/public static int func(