题目说明
赌场经典的二十一点游戏中,每回合下注 1 枚硬币,
赢了可以得到 2 枚硬币(+1枚),输了硬币会被收走(-1枚)。
假设最开始只拥有 1 枚硬币,并且每回合下注 1 枚,
那么 4 回合后还能剩余硬币的硬币枚数变化情况如图所示,
共有 6 种(圆形中间的数字代表硬币枚数)
求最开始拥有 10 枚硬币时,持续 24 回合后硬币还能剩余的硬币枚数变化情况共有多少种?
题目转化为:
10枚硬币,每次下注1枚。
赢了+1枚,输了-1枚。
硬币输完了则立刻结束游戏。
求:能坚持24轮且还有剩余硬币的情况有多少种?
思路
用递归方法表示一轮下注,记录“硬币数量”和“距离成功还剩多少轮”
当硬币数量为0时,表示失败;当剩余轮数为0时,表示成功。
记录失败+成功的总数
代码
public static void main(String[] args) {
// 10枚硬币,需要持续24轮下注才算成功
System.out.println(game(10, 24));
}
/**
* 每调用一次该方法,表示进行了一轮下注。
* @param coin 剩余硬币数
* @param depth 还要进行多少轮才算成功
* @return 有多少种情况
*/
private static int game(int coin, int depth){
if(coin == 0) return 0; // 没有硬币了,退出游戏
if(depth == 0) return 1; // 成功情况+1
// 本轮赢了的情况
int win = game(coin + 1, depth - 1); // 硬币数量+1,剩余轮数-1
// 本轮输了的情况
int lose = game(coin - 1, depth - 1); // 硬币数量+1,剩余轮数-1
return win + lose;
}
结果
16051010