Count number of ways player 1 can win in a 2 player game

I came across this following question,

2 players play a game. In each turn both players receive points in the range -x to +x (both included). Player 1 starts from score p1 and player 2 starts from score p2. If they play a total of k turns, find the total number of ways in which player 1 can win the game ie at the end of k turns, player 1 has more points than player 2.

So in short my understanding is that we need to find total number of combination set of points for player1 and player2 such that (sum of points set of player 1)-(sum of points set of player 2) >= p2-p1+1

I am not sure how to tackle this problem. Please suggest an approach. Thanks in advance.

---

Solve this recursively. Using your variables, let's look at the cases:. Let

score_range = [-x : x]

Call the function win_count

Base case, k==1

if k == 1 , there is one turn to go. The score difference is p2-p1. If player 2 scores n2 points in this round, then player 1 needs to finish with at least (p2 + n2) - p1 + 1 points this round. Now, how many combinations of that are available with p1, p2 in score_range ? You can compute that directly from the given integers.

Return that count as the functional value.

Recursion case, k > 1

Walk through all of the possible scores for this round. Recur to count possibilities for the remainder of the game.

count = 0
for n1 in score_range
    for n2 in score_range
        count += win_count(p1+n1, p2+n2, k-1, x)

Can you take it from there?

链接地址: http://www.djcxy.com/p/30706.html

上一篇: 寻找放置块的最佳策略的算法

下一篇: 玩家1可以在2人游戏中获胜的方法数量