資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究用 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
- i 範圍從 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
更新於：05-May-2020
274 已檢視
廣告