1. 从一道“打棒球”的数学题说起最近在LightOJ上刷题碰到了编号1408的“Batting Practice”。这题目名字听起来挺生活化像是讲棒球训练但点进去一看好家伙核心居然是个解方程的问题。很多朋友尤其是刚开始接触概率和期望这类题目的同学一看到“解方程”三个字可能就有点发怵觉得抽象又枯燥。其实不然这道题恰恰是一个绝佳的案例它把抽象的数学期望概念包装进了一个非常具体的体育场景里让我们能通过“打棒球”这个动作直观地理解背后那套数学逻辑。简单来说题目是这样的一个击球手在进行击球练习。每次击球他有两种可能的结果以概率P击出“好球”Good Shot或者以概率(1-P)击出“坏球”Bad Shot。这个练习的规则有点特别当击球手连续击出K1个好球或者连续击出K2个坏球时练习就立即结束。题目要我们求的是在练习结束前击球手预期会进行多少次击球。这个“预期”次数在数学上就是我们常说的“数学期望值”。所以别看它披着“Batting Practice”的外衣内核是一个典型的、带有吸收态的马尔可夫链期望步数计算问题而求解它的关键技巧正是建立并求解方程。我之所以觉得这道题值得深聊不是因为它多难而是因为它完美地展示了如何将一个现实世界的不确定过程击球用严谨的数学模型状态与方程来描述和求解。接下来我们就一步步拆解看看这个方程是怎么列出来的又该怎么巧妙地解出来。2. 问题重述与核心概念什么是“期望击球次数”在直接动手列方程之前我们必须先统一思想彻底理解题目到底在问什么。这能避免我们后续在建模时走偏。首先明确几个参数P: 单次击球打出好球的概率。这是一个介于0和1之间的数。1-P: 单次击球打出坏球的概率。K1: 结束练习所需连续好球的个数。K2: 结束练习所需连续坏球的个数。练习的结束条件是“或”的关系连续好球数先达到K1或者连续坏球数先达到K2满足任一条件则立刻停止。那么“期望击球次数”是什么意思呢想象一下让这个击球手在完全相同的条件下相同的P K1 K2重复进行无数次这样的练习。由于每次击球结果是随机的所以每次练习的实际击球次数也会不同有时运气好很快就连出好球结束有时运气差来回折腾很久。我们把无数次练习的“总击球次数”加起来然后除以“练习的总次数”得到的一个平均次数就是数学期望值Expected Value。它代表了在概率规则下一次练习“平均来看”会进行的击球数。这个值不是一个确定数而是一个基于概率的统计预测。我们的任务就是用一个包含P K1 K2的公式把这个预测值精确地计算出来。3. 状态定义将连续记录转化为离散状态这是解题最关键的一步也是将实际问题“翻译”成数学语言的过程。直接去思考“已经打了多少球”和“当前连续好/坏球数”会很混乱。我们需要定义清晰的状态State。一个非常自然且高效的状态定义是用当前连续好球的次数good_streak和连续坏球的次数bad_streak来描述局面。但这里有一个重要的简化因为一次击球不可能同时既是好球又是坏球所以在任何时刻good_streak和bad_streak中必然有一个为0。击出一个好球good_streak增加bad_streak归零反之亦然。因此我们可以用一个变量x来统一表示当前的“连续趋势”如果x 0表示当前有连续x个好球且连续坏球数为0。如果x 0表示当前有连续|x|个坏球且连续好球数为0。例如x 2表示“连续2个好球”。x -1表示“连续1个坏球”。那么整个击球过程就可以看作是在一条数轴上的随机游走。起点是x0尚未击球无连续趋势。每次击球以概率P如果x0则走到x1如果x0则走到1因为打出一个好球会中断之前的坏球趋势从1个好球开始。以概率1-P如果x0则走到x-1如果x0则走到-1因为打出一个坏球会中断之前的好球趋势从1个坏球开始。练习结束的状态称为吸收态有两个当x K1时表示连续好球数达到K1练习成功结束。当x -K2时表示连续坏球数达到K2练习失败结束。现在我们定义核心函数设E(x)表示从状态x开始直到练习结束到达K1或-K2所需要的期望击球次数。我们最终要求的就是E(0)。4. 建立期望方程下一步的可能性分析有了状态和函数定义我们就可以建立方程了。这是动态规划DP或马尔可夫链中求解期望步数的标准方法从当前状态出发考虑所有可能的下一步将下一步状态的期望值乘以其转移概率求和后再加1代表当前走的这一步就等于当前状态的期望值。让我们分情况讨论E(x)的方程情况一当x 0时当前处于连续好球趋势中从状态x出发以概率P击出好球转移到状态x1。后续还需要E(x1)次击球才能结束。以概率1-P击出坏球这会中断好球趋势。注意这不是转移到x-1因为坏球会清零好球记录并开始坏球记录。所以是转移到状态-1表示有了1个连续坏球。后续还需要E(-1)次击球。无论下一步去哪当前这一步击球是已经发生的所以要1。因此方程如下E(x) P * [1 E(x1)] (1-P) * [1 E(-1)] 其中0 x K1稍微整理一下E(x) 1 P * E(x1) (1-P) * E(-1)... (方程 A)情况二当x 0时当前处于连续坏球趋势中设y -x 0则状态表示连续y个坏球。 从状态-y出发以概率P击出好球中断坏球趋势转移到状态1。后续需要E(1)次击球。以概率1-P击出坏球转移到状态-(y1)即-y-1。后续需要E(-y-1)次击球。同样当前这一步击球要1。因此方程如下E(-y) 1 P * E(1) (1-P) * E(-y-1) 其中0 y K2或者写成E(x) 1 P * E(1) (1-P) * E(x-1) 其中-K2 x 0... (方程 B)边界条件吸收态当到达结束状态时不需要再击球了所以期望次数为0。E(K1) 0E(-K2) 05. 解方程观察规律与化简现在我们有了一个方程组。直接看它似乎涉及很多未知数E(1), E(2), ..., E(K1-1)和E(-1), E(-2), ..., E(-(K2-1))。但仔细观察方程A和B我们可以发现它们能极大地简化。处理方程 A (对于 x 0)方程 A:E(x) 1 P * E(x1) (1-P) * E(-1)注意对于不同的x方程中除了E(x)和E(x1)另一个项是固定的(1-P)*E(-1)。这提示我们E(x)和E(x1)之间存在一个线性关系。我们可以通过递推来找出这个关系。让我们写出相邻两个状态的方程 对于状态i:E(i) 1 P * E(i1) C其中C (1-P)*E(-1)是一个常数。 对于状态i1:E(i1) 1 P * E(i2) C这看起来像一个线性递推。我们可以尝试从边界E(K1)0倒着推回来。但更聪明的方法是我们设D(x) E(x) - E(x1)。那么从方程A可得E(x) - P * E(x1) 1 C [E(x) - E(x1)] (1-P)E(x1) 1 C D(x) 1 C - (1-P)E(x1)这个式子还是包含E(x1)不便于直接求和。换一个思路我们把方程A变形解出E(x1)P * E(x1) E(x) - 1 - CE(x1) [E(x) - 1 - C] / P这个递推式从xK1-1开始因为E(K1)0。E(K1-1) 1 P * 0 C 1 CE(K1-2) 1 P * E(K1-1) C 1 P*(1C) C 1 P C(1P)... 这样递推下去最终E(1)可以表示为一个关于常数C即(1-P)*E(-1)的表达式。我们记这个表达式为E(1) f(C) A B * C其中A和B是由P和K1计算出的常数。实际上通过观察我们可以发现一个更简洁的规律。令C (1-P)*E(-1)。方程A可以写成E(x) - P * E(x1) 1 C。 这是一个非齐次线性递推。它的解可以分解为齐次通解和非齐次特解之和。 齐次方程E(x) - P * E(x1) 0的特征方程为1 - P * r 0通解形式为E_h(x) α * (1/P)^x。 非齐次特解显然是一个常数设E_p(x) d代入得d - P*d 1C所以d (1C)/(1-P)。 因此通解为E(x) α * (1/P)^x (1C)/(1-P)。 利用边界条件E(K1)0可以求出α进而得到E(1)关于C的表达式。这个过程涉及指数运算在编程实现时需要注意精度。处理方程 B (对于 x 0)方程 B:E(x) 1 P * E(1) (1-P) * E(x-1) 其中x 0。 这又是一个递推关系但这次是从更负的方向递推。我们设F P * E(1)是一个新的常数。 方程变为E(x) 1 F (1-P) * E(x-1)。 同样这是一个线性递推。从边界E(-K2)0开始正向递推向0靠近E(-K21) 1 F (1-P)*0 1 FE(-K22) 1 F (1-P)*(1F) (1F)[1 (1-P)]我们可以发现规律E(-K2 m) (1F) * [1 (1-P) (1-P)^2 ... (1-P)^(m-1)]这是一个等比数列求和。 当m K2时我们得到E(0)。但注意我们的状态定义中x0是一个特殊点它不属于方程A或B的范畴。我们需要单独考虑E(0)。连接点状态x0在x0时没有连续趋势。击第一球以概率P打出好球进入状态1。后续需要E(1)次。以概率1-P打出坏球进入状态-1。后续需要E(-1)次。加上当前的第一击。 所以E(0) 1 P * E(1) (1-P) * E(-1)... (方程 C)看方程C中出现了E(1)和E(-1)。而我们从方程A的推导中得到了E(1) f( C )其中C (1-P)*E(-1)。 我们从方程B的推导中可以得到E(-1)关于F的表达式而F P * E(1)。于是我们得到了一个关于E(1)和E(-1)的二元方程组E(1) f( (1-P)*E(-1) )来自方程A系列E(-1) g( P*E(1) )来自方程B系列具体形式为等比数列求和这里f和g都是已知的线性或通过等比求和得到的函数。解这个二元一次方程组就能求出E(1)和E(-1)。最后代入方程C就得到了我们最终想要的E(0)。6. 最终求解公式与推导简化为了避免陷入复杂的符号运算我们可以用一种更清晰、更适合编程的思路来重新梳理。我们定义两个核心的未知量a E(1)从“连续1个好球”状态开始到结束的期望次数。b E(-1)从“连续1个坏球”状态开始到结束的期望次数。我们的目标E(0) 1 P*a (1-P)*b。现在我们分别建立关于a和b的方程。建立关于a的方程利用方程A和边界 E(K1)0考虑从状态1连续1个好球到状态K1连续K1个好球这个过程。只要一直击出好球就能前进。一旦击出坏球就立刻跳到状态-1即b。 设从状态i(1 i K1) 开始到达结束的期望次数为E(i)。我们有E(i) 1 P * E(i1) (1-P) * b 对于 1 i K1-1。E(K1-1) 1 P * 0 (1-P) * b 1 (1-P)b。 我们可以反向递推 令C (1-P)b。E(K1-2) 1 P * E(K1-1) C 1 P*(1C) C 1 P C(1P)E(K1-3) 1 P * E(K1-2) C 1 P*[1PC(1P)] C 1 P P^2 C(1PP^2)... 观察到规律E(K1 - m) (1 P P^2 ... P^(m-1)) C * (1 P ... P^(m-1)) (1C) * (1 P ... P^(m-1)) (1C) * (1 - P^m) / (1-P)等比数列求和公式当m K1-1时E(1) a。 所以a (1 C) * (1 - P^(K1-1)) / (1-P) 其中C (1-P)b。 因此a [1 (1-P)b] * (1 - P^(K1-1)) / (1-P)... (方程1)建立关于b的方程利用方程B和边界 E(-K2)0考虑从状态-1连续1个坏球到状态-K2连续K2个坏球这个过程。只要一直击出坏球就能前进。一旦击出好球就立刻跳到状态1即a。 设从状态-j(1 j K2) 开始到达结束的期望次数为E(-j)。我们有E(-j) 1 (1-P) * E(-(j1)) P * a 对于 1 j K2-1。E(-(K2-1)) 1 (1-P)*0 P*a 1 Pa。 正向递推更直观。令D P*a。E(-1) b是我们要求的。E(-2) 1 (1-P)*E(-3) DE(-3) 1 (1-P)*E(-4) D... 我们可以从E(-(K2-1))反向表示出E(-1)。更简单的方法是利用从-1到-K2的递推关系它与求a的过程完全对称只是概率从P换成了(1-P)目标值从a换成了b边界从K1换成了K2。类比方程1我们可以直接写出b [1 P*a] * (1 - (1-P)^(K2-1)) / P... (方程2)解二元一次方程组现在我们得到了关于a和b的方程组 方程1:a [1 (1-P)b] * S1 其中S1 (1 - P^(K1-1)) / (1-P)方程2:b [1 P*a] * S2 其中S2 (1 - (1-P)^(K2-1)) / P这是一个标准的二元一次方程组。将方程2代入方程1a [1 (1-P) * ( (1P*a)*S2 ) ] * S1a [1 S2*(1-P) S2*(1-P)*P*a ] * S1a [1 S2*(1-P)] * S1 S1*S2*P*(1-P) * a将包含a的项移到一边a - S1*S2*P*(1-P)*a [1 S2*(1-P)] * S1a * [1 - S1*S2*P*(1-P)] S1 * [1 S2*(1-P)]因此a { S1 * [1 S2*(1-P)] } / [1 - S1*S2*P*(1-P)]同理可以解出bb { S2 * [1 S1*P] } / [1 - S1*S2*P*(1-P)]计算最终答案 E(0)E(0) 1 P*a (1-P)*b将上面求得的a和b代入即可。这就是本题的最终解析解公式。在编程实现时我们只需要根据输入的PK1K2计算出S1S2 然后计算ab 最后得到E(0)。注意当P0或P1时公式中会出现除以0的情况需要单独处理。如果P0则永远打不出好球那么从状态0开始必然是一直打坏球直到连续K2次结束这是一个几何分布期望次数就是K2。同理如果P1期望次数是K1。如果K11或K21公式中的S1或S2的求和上限为0其值为0代入公式计算即可一般不需要特殊处理但编程时要注意等比数列求和公式在项数为0时的正确性。7. 编程实现与数值验证理论公式有了我们来看看怎么用代码实现并验证其正确性。这里以C为例因为LightOJ主要支持C/C。首先公式涉及幂运算P^(K1-1)和(1-P)^(K2-1)。K1和K2可以很大题目中未明确但一般可达几十甚至上百直接使用pow函数对于浮点数可能没问题但为了更清晰我们通常用循环或快速幂来计算。由于概率P是浮点数计算等比数列和S1和S2时可以直接用公式(1 - r^n) / (1 - r)但要处理r1的情况即P0或P1我们已经特判。#include bits/stdc.h using namespace std; double solve(double P, int K1, int K2) { // 特判概率为0或1的情况 if (fabs(P) 1e-12) { // P 0 return 1.0 * K2; } if (fabs(P - 1.0) 1e-12) { // P 1 return 1.0 * K1; } double Q 1.0 - P; // 计算 S1 (1 - P^(K1-1)) / (1-P) (1 - r1^n1) / (1-r1) double r1 P; int n1 K1 - 1; double S1; if (fabs(r1 - 1.0) 1e-12) { S1 n1; // 等比数列求和当公比为1时和为 n1 * 1 n1 } else { S1 (1.0 - pow(r1, n1)) / (1.0 - r1); } // 计算 S2 (1 - (1-P)^(K2-1)) / P (1 - r2^n2) / (1-r2) 但注意分母是P double r2 Q; int n2 K2 - 1; double S2; if (fabs(r2 - 1.0) 1e-12) { // 即 Q1也就是P0已特判 S2 n2; } else { S2 (1.0 - pow(r2, n2)) / P; // 公式是除以P // 也可以写成 (1.0 - pow(r2, n2)) / (1.0 - r2) * (1.0 - r2) / P但直接除P更简单 // 注意当P很小时这里除以P可能导致数值不稳定但通常题目数据会避免极端情况。 } double denominator 1.0 - S1 * S2 * P * Q; // 理论上分母不会为0因为P和Q在(0,1)S1和S2是有限正数。 // 但数值计算中可能出现极小值需要判断。 if (fabs(denominator) 1e-12) { // 这种情况理论上不存在如果发生可能是极端参数返回一个较大值或特殊处理 return 1e9; } double a (S1 * (1.0 S2 * Q)) / denominator; double b (S2 * (1.0 S1 * P)) / denominator; double E0 1.0 P * a Q * b; return E0; } int main() { int T, caseNo 1; scanf(%d, T); while (T--) { double P; int K1, K2; scanf(%lf %d %d, P, K1, K2); double ans solve(P, K1, K2); printf(Case %d: %.10f\n, caseNo, ans); } return 0; }数值验证与测试思路简单情况验证P0, K1任意, K25应输出5.0。程序特判处理。P1, K13, K2任意应输出3.0。程序特判处理。K11, K21这意味着只要打出一球无论好坏练习都结束因为连续1个好球或1个坏球就达标。所以期望次数就是1。代入公式S1 (1-P^0)/(1-P)0S2 (1-Q^0)/P0。那么a 0,b0E(0)1001。正确。K12, K22, P0.5可以手动模拟。从0开始50%概率到状态150%到状态-1。然后从状态1有50%概率直接到2结束50%概率到-1。从状态-1对称。通过解小规模状态方程可以算出E(0)3。用程序计算验证。蒙特卡洛模拟验证对于非平凡的参数可以写一个简单的模拟程序随机进行大量实验比如100万次计算平均击球次数与公式解对比。两者应该非常接近。这是验证概率题目答案最直观的方法。import random def simulate(P, K1, K2, trials1000000): total_shots 0 for _ in range(trials): good_streak 0 bad_streak 0 shots 0 while good_streak K1 and bad_streak K2: shots 1 if random.random() P: good_streak 1 bad_streak 0 else: bad_streak 1 good_streak 0 total_shots shots return total_shots / trials # 测试几组数据与C公式计算结果对比8. 常见错误与思维陷阱在解这道题和实现代码时有几个坑很容易掉进去状态定义混淆最开始的思路可能是定义二维状态dp[i][j]表示连续i个好球和j个坏球时期的望。但这忽略了i和j不能同时非零的本质会导致状态空间冗余和转移复杂。抓住“连续趋势”用一维变量表示是简化的关键。方程建立错误在列期望方程时最容易忘记加“1”。E(当前状态) 1 Σ [概率 * E(下一状态)]这个“1”代表了从当前状态走一步到下一个状态的这次击球。少了它答案会整体偏小。边界条件处理方程适用于非吸收态0 |x| K。对于x0这个起始状态需要单独列出方程方程C。不能错误地将x0套用到方程A或B中。忽略公式中的指数项在推导S1和S2时求和项数是K1-1和K2-1而不是K1和K2。这是因为从状态1到状态K1需要连续前进K1-1步好球状态1已经是1个好球了。这个地方的下标很容易写错。数值精度问题当P非常接近0或1或者K1、K2很大时计算pow(P, K1-1)可能会下溢为0。在大多数情况下这恰好是正确的结果因为概率的极高次幂几乎为0。但需要确保你的pow函数能处理浮点数的指数运算。有时为了避免精度误差可以使用exp((K1-1) * log(P))来计算但要注意P0的情况。在竞赛中通常的double精度和pow函数足以应对。分母为零的特判在计算公式中a和b的分母1 - S1*S2*P*Q时理论上在0P1且K1, K2 1时分母是正的不会为零。但编程时为稳健起见可以加一个判断如果分母绝对值极小则说明参数可能使期望值极大例如P0.5 K1,K2很大时S1和S2都很大乘积可能接近1/(PQ)使得分母接近0这时可能需要返回一个非常大的数或者用高精度计算。不过在LightOJ的测试数据中通常不会出现这种极端情况。误解“期望”含义最终答案E(0)是一个浮点数。有些同学可能觉得击球次数应该是整数为什么输出小数这正是数学期望的特点它表示的是平均值可以是小数。例如抛硬币直到出现正面平均需要抛2次期望值就是2.0。这道“Batting Practice”的题目把概率期望、状态转移、方程求解融合得相当巧妙。它不像有些题直接给出状态转移方程让你求期望而是需要你自己从问题描述中识别出状态、建立方程、并最终化简求解。这个过程本身比记住最终的公式更重要。下次遇到类似“连续成功/失败达到一定次数就结束”的期望问题你就能立刻反应过来该用什么样的思路去建模和求解了。