程序员的算法趣题:Q23 二十一点通吃(Java版)

题目说明

赌场经典的二十一点游戏中,每回合下注 1 枚硬币,
赢了可以得到 2 枚硬币(+1枚),输了硬币会被收走(-1枚)。
假设最开始只拥有 1 枚硬币,并且每回合下注 1 枚,
那么 4 回合后还能剩余硬币的硬币枚数变化情况如图所示,
共有 6 种(圆形中间的数字代表硬币枚数)
程序员的算法趣题:Q23 二十一点通吃(Java版)
求最开始拥有 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

上一篇:PHP二维数组按某个字段键值排序


下一篇:凑零钱问题 多种解法 递归&动态规划