C ++中的新21游戏

假设Rima玩以下游戏，该游戏大致基于纸牌游戏“ 21”。因此，Rima从0分开始，并在她少于K分时画数字。现在，在每次绘制期间，她从[1，W]的范围内随机获得整数个点，其中W是给定的，那是整数。现在，每个抽签都是独立的，并且结果具有相等的概率。当Rima获得K点或更多点时，她停止绘制数字。我们必须找到她的N分或更少的概率吗？

因此，如果N = 6，K为1，W为10，那么答案将为0.6，因为Rima得到一张牌，然后停止，在10个概率中有6个，她等于或低于N = 6分。

为了解决这个问题，我们将遵循以下步骤-

• 如果k为0，或者N> = K + W，则返回1

• 制作大小为N + 1的数组dp，设置dp [0]：= 1

• 设置wsum：= 1.0，ret：= 0.0

• 当我在1到N的范围内

• dp [i]：= wsum / W

• 如果i <K，则wsum：= wsum + dp [i]，否则ret：= ret + dp [i]

• 如果i – W> = 0，则wsum：= wsum – dp [i-W]

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   double new21Game(int N, int K, int W) {
      if(K == 0 || N >= K + W) return 1.0;
      vector <double> dp (N + 1);
      dp[0] = 1;
      double Wsum = 1.0;
      double ret = 0.0;
      for(int i = 1; i <= N; i++){
         dp[i] = Wsum / W;
         if(i < K){
            Wsum += dp[i];
         }else ret += dp[i];
         if(i - W >= 0) Wsum -= dp[i - W];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.new21Game(6, 1, 10));
}

输入项

6
1
10

输出结果

0.6