说明

该程序模拟了“四枚硬币”游戏的概率计算，用于确定在1到20轮游戏后，玩家A获胜、玩家B获胜或平局的概率。游戏规则基于两名玩家每轮抛掷两枚硬币的结果，根据特定得分规则累积分数。程序通过动态规划计算每种结果的可能性，并输出概率表格。

算法标签

• 动态规划
• 概率统计

解题思路

1. 问题分析：游戏每轮由两名玩家各抛两枚硬币，根据结果得分。玩家A的得分规则更有利。需要计算在1到20轮后，A、B的胜负或平局的概率。
2. 动态规划：使用三维数组dp[i][j][k]表示第i轮后，A得分为j，B得分为k的概率。初始化第0轮双方得分为0的概率为1。
3. 状态转移：对于每轮，遍历所有可能的得分组合，根据9种抛硬币结果的概率（way数组）更新下一轮的得分概率。
4. 结果统计：每轮结束后，统计A得分高于B、低于B或等于B的总概率，输出百分比。

分析

• 得分规则：A和B的得分变化由抛硬币结果决定，共9种组合，每种组合的概率和得分变化存储在way、a、b数组中。
• 动态规划数组：dp[i][j][k]中，j和k的范围为-20到40（初始偏移20以避免负索引），表示A和B的可能得分。
• 概率计算：每轮的概率通过前一轮的概率乘以当前轮的可能结果概率累加得到。
• 输出：每轮结束后，遍历所有得分组合，统计A胜、B胜和平局的概率，格式化输出。

实现步骤

1. 初始化：设置dp[0][20][20] = 1，表示初始状态（双方得分0）。
2. 动态规划填充：
   • 对于每轮i（1到20），遍历所有可能的得分j和k。
   • 如果dp[i-1][j][k] > 0，则根据9种抛硬币结果更新dp[i][j+a[s]][k+b[s]]的概率。
3. 统计结果：
   • 每轮结束后，遍历所有j和k，比较A和B的得分（j-20和k-20），统计A胜、B胜和平局的总概率。
4. 输出表格：按格式输出每轮的胜负和平局概率，保留4位小数。

代码解释

• 数组定义：
  • way：9种抛硬币结果的概率。
  • a和b：A和B在每种结果下的得分变化。
• 动态规划数组dp：记录每轮后的得分概率分布。
• 主循环：
  • 外层循环遍历轮数（1到20）。
  • 内层循环遍历所有可能的得分组合，更新下一轮的概率。
• 结果统计与输出：
  • 每轮结束后，统计A胜、B胜和平局的总概率，格式化输出。

该程序通过动态规划高效地模拟了游戏的多轮概率变化，并输出详细的概率表格。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
using namespace std;
double way[9]= {0.0625,0.125,0.0625,0.125,0.25,0.125,0.0625,0.125,0.0625};
int a[9]= {1,1,2,0,0,1,-1,0,0};
int b[9]= {0,-1,-1,1,0,0,2,0,-1};
double dp[22][66][66];
void solve()
{
    memset(dp,0,sizeof(dp));
    dp[0][20][20]=1;      //dp[i][j][k],表示第i个回合，A得j分，B得k分的概率，j或k最小为-20，所以+20
    for(int i=1; i<=20; i++)
        for(int j=60; j>=0; j--){
            int score1=j-20;
            for(int k=60; k>=0; k--){
                int score2=k-20;
                if(dp[i-1][j][k]>0){
                    for(int s=0; s<9; s++)
                        dp[i][score1+20+a[s]][score2+20+b[s] ]+=dp[i-1][j][k]*way[s];
                }

            }
        }
    printf("Round   A wins    B wins    Tie\n");
    for(int i=1; i<=20; i++)
    {
        double a_win = 0 , b_win = 0 , tie = 0 ;
        for(int j=0; j<=60; j++){
            for(int k=0; k<=60; k++){
                if(j>k) a_win+=dp[i][j][k] ;
                else if(j<k)    b_win += dp[i][j][k] ;
                else tie += dp[i][j][k] ;
            }
        }
        printf("%5d%10.4f%%%9.4f%%%9.4f%%\n",i,a_win*100,b_win*100,tie*100);
    }
}
int main()
{
    solve();
}