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을 반환합니다.
• 배열 dp를 N + 1 크기로 만들고 dp[0] :=1로 설정
• set wsum :=1.0, ret :=0.0
• 1~N
  범위의 i에 대해
  • dp[i] :=wsum / W
  • i
  • i – W>=0이면 wsum :=wsum – dp[i - W]
• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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