掷骰子

待我称王封你为后i 2021-11-10 02:42 414阅读 0赞

# 掷骰子 #

#### ####

### Problem Description ###

概率论的起源与赌博问题有关。16世纪，意大利的学者吉罗拉莫&\#8226;卡尔达诺（Girolamo Cardano，1501——1576）开始研究掷骰子等赌博中的一些简单问题。17世纪中叶，当时的法国宫廷贵族里盛行着掷骰子游戏，游戏规则是玩家连续掷 4 次骰子，如果其中没有 6 点出现，玩家赢，如果出现一次 6 点，则庄家（相当于现在的赌场）赢。按照这一游戏规则，从长期来看，庄家扮演赢家的角色，而玩家大部分时间是输家，因为庄家总是要靠此为生的，因此当时人们也就接受了这种现象。那么现在让我们来计算一个概率问题。  
一个骰子有n（4≤n≤8）个面，随机投掷m（1≤m≤32）次，请计算出现连续x个相同面的概率(C)。（结果请四舍五入到小数点后第3位。）

### Input ###

每行3个用空格分开的整数，分别表示n,m,x。

### Output ###

每行一个数，表示概率C。

### Sample Input ###

4 5 3

### Sample Output ###

0.129

### 解释： ###

需要求抛 m次后，连续x次相同面的骰子的概率，我们可以分为一次一次的抛，那么第 i 次 和 第 i - 1 次的状况只有两种。

第一：  两次的点数相同， 那就是 1/n

第二：两次的点数不同，那就是 (n-1)/n

假设连续抛了10次，假设点数为字符，有可能为：

AAABB CCC DD

AAABC CDAAA

AAABC DERTY

AAABC DDDDD

也就是说，存在一个“目前最长相同字符串”（now\_len）。和 “最后相同字符串的长度(last\_len)”.

result = max(now\_len, last\_len)

同时可以知道，当last\_len > now\_len 时， now\_len = last\_len.

根据最后一次抛的情况，我们可以更新 last\_len, 然后更新last\_len 去更新 now\_len，最后得到答案。

当最后一次和前一次不同时， last\_len = 1,  概率为 (n-1)/n

当最后一次和前一次相同时， last\_len = last\_len + 1; 概率为 1 / n

当last\_len > now\_len 时， now\_len = last\_len.

请计算出现连续x个相同面的概率(C)， 就是算，当now\_len = X 的时候， last\_len 从 1 到now\_len 的和。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 
     3 using namespace std;
     4 const int N = 33;
     5 
     6 double dp[N][N][N];
     7 
     8 int main(){
     9     int n, m, c;  
    10     while (cin >> n >> m >> c) {
    11         memset(dp, 0.0, sizeof(dp));
    12         dp[1][1][1] = 1.00;
    13 /*“当前已投掷的次数”、“当前连续出现过最长的相同数字的次数”、“最后投掷的相同的数字的次数” */
    14         for (int i = 1; i <= m; i++) {
    15             for (int j = 1; j <= i; j++) {
    16                 for (int k = 1; k <= j; k++) {
    17                     double cur = dp[i][j][k];
    18                     if (cur > 0){
    19                         if (k + 1 > j){
    20                            
    21                             dp[i + 1][k + 1][k + 1] += cur * (1.0 / n); 
    22                         } else {
    23                             
    24                             dp[i + 1][j][k + 1] += cur * (1.0 / n);
    25                         }
    26                       
    27                         dp[i + 1][j][1] += cur * ((double)(n - 1) / n);
    28                     }
    29                 }
    30             }
    31         }
    32 
    33         double sums = 0.0;
    34         for (int i = 1; i <= c; i++) {
    35             sums += dp[m][c][i];
    36         }
    37         printf("%.3lf\n", sums);
    38     }
    39     return 0;
    40 }

转载于:https://www.cnblogs.com/gznb/p/11207346.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/6ee74d82a84a4bc28f5fa244ba829eaf.png