数据结构
网络
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 已查看
广告