算法题——投篮比赛获胜概率问题

简介: 问题描述: 甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。

问题描述:

甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。假定甲投进的概率为P1(0<P1<1),乙投进的概率为P2(0<P2<1)。那么这场投篮比赛,甲获胜的概率P为多少?

 

 

很显然的,甲获胜的概率P是和P1、P2、N相关的。

P1越大,P越大

P2越大,P越小

N越大,P越小

 

不失一般性,假设P1=0.7,P2=0.3,N=4,求甲获胜的概率P

 

解法一:大数量模拟法(10000000次)

 

在前文 算法题——投篮比赛获胜的概率 中介绍的就是这种方法。

用计算机模拟10000000次比赛的过程,统计甲获胜的次数。然后甲获胜的次数比上总次数接近甲获胜的概率。

一共模拟了10批次的比赛,每批次模拟10000000次比赛的过程(P1=0.7,P2=0.3,N=4)

第1批次,甲获胜8282467次

第2批次,甲获胜8282839次

第3批次,甲获胜8283808次

第4批次,甲获胜8281636次

第5批次,甲获胜8282652次

第6批次,甲获胜8283432次

第7批次,甲获胜8281948次

第8批次,甲获胜8284125次

第9批次,甲获胜8284626次

第10批次,甲获胜8283720次

 

平均10个批次,平均甲获胜8283125次。那么甲获胜的概率大约是82.83125%

 

 

解法二:矩阵法

 

解法一是建立在大量的模拟上,所得的数据离理论值还是有一定的偏差的(模拟的次数越多,偏差值越小)。那么,本方法就是从理论上来计算甲获胜的概率P的。

 

分析该问题,可以得出整个问题存在8个状态(状态的个数和N有关,状态的个数为2N个)

分别是

积分0分,乙获胜

积分1分,乙要投篮;积分1分,甲要投篮

积分2分,乙要投篮;积分2分,甲要投篮

积分3分,乙要投篮;积分3分,甲要投篮

积分4分,甲获胜

 

这8个状态之间的关系可以用下图表示(为了后文表述方便,给这8个状态起了名字,分别是S1、S2、S3、……、S7、S8)

image

 

如图,比赛初始是在S1状态,比赛结束在S7(甲获胜)或S8(乙获胜)状态,状态之间有转换箭头。

例如:当前是S3状态(积分3,甲投篮),那么下一个状态可能是S6(甲投失,换成积分3,乙投篮的状态)或者是S7(甲投进,积分4,甲获胜的状态)。再比如当前是S6状态(积分3,乙投篮),那么下一个状态可能是S5(乙投进,换成积分2,乙投篮的状态)或者是S3(乙投失,换成积分3,甲投篮的状态)

 

 

用A1、A2、A3、A4、A5、A6、A7、A8表示某次投篮后,各个状态所占的比重。那么再投篮一次后,各个状态的所占比重计算如下(等号左边是新的比重,等号右边是原来的比重):

A1=A4(1-P2)

A2=A1P1+A5(1-P2)

A3=A2P1+A6(1-P2)

A4=A5P2+A1(1-P1)

A5=A6P2+A2(1-P1)

A6=A3(1-P1)

A7=A3P1+A7

A8=A4P2+A8

 

可以把上面的计算式子转换为矩阵的形式

令向量Ti=(A1、A2、A3、A4、A5、A6、A7、A8)表示第i次(i=0时表示初始状态)投篮各状态所占比重的向量,则

Ti+1=Ti×A

 

其中,A为8*8的矩阵,如下图所示

image

 

因为

T1=T0×A

T2=T1×A=T0×A×A=T0×A2

T3=T2×A=T0×A2×A=T0×A3

……

TM=T0×AM

 

实际上,本题中的甲获胜的概率就是当M趋向于无穷时,TM的A7分量。同时,TM的A8分量表示乙获胜的概率

把上面的矩阵A分成四个小矩阵Q1、Q2、Q3、Q4,如下图所示:

image

 

image

 

 

由于TM=T0×AM,故在这儿分析AM

 

image

 

 

由于矩阵I-Q1可逆,则上述的表达式可以简化为

Q1M-1+Q1M-2+…+Q1+I=(Q1M-1+Q1M-2+…+Q1+I)(I-Q1)(I-Q1)-1

=(Q1M-1+Q1M-2+…+Q1+I-Q1M-Q1M-1-…-Q1)(I-Q1)-1

=(I-Q1M)(I-Q1)-1

 

 

于是矩阵AM就简化成如下形式

image

 

 

对于矩阵Q1来说。由于是非负矩阵,根据G. Frobenius可知,它的谱半径ρ满足不等式,r≤ρ≤R。其中r表示G1矩阵中所有行和值(一行所有元素加起来的值)的最小值,R表示G1矩阵中所有行和值最大值。可知R=1,r=MIN(1-P1,1-P2)

 

而在李华所著的《非负矩阵谱半径的一个新估计》中,将谱半径的范围缩小

 

得到如下的不等式

r≤ρ≤R-(1-P2)(R-r)/R

 

由此可以得知Q1的谱半径ρ<1

而利用谱半径的性质可知,当谱半径ρ<1时,矩阵Q1的M次方趋向于0矩阵

image

 

于是本问题就得出了结论,令T为TM中M趋向无穷大时的向量,A*为AM中M趋向无穷大时的矩阵。可知

 

T=T0×A*

 

 

本题中P1=0.7,P2=0.3,T0=(1,0,0,0,0,0,0,0)

 

矩阵A和矩阵A*分别为

image

 

于是

T=T0×A*=(0,0,0,0,0,0,0.828302342,0.171697658)

 

甲获胜的概率是82.8302342%,乙获胜的概率是17.1697658%

 

和方法一的结论比较(82.83125%),还是非常接近的。也间接说明了方法一的可行性。

 

 

本方法从理论的角度给出了问题的解。本示例中,P1=0.7,P2=0.3,N=4

本方法的计算难点就是求(I-Q1)-1,这是一个消耗大量计算时间的过程。Q1是一个2N-2*2N-2的稀疏矩阵,I-Q1也是一个2N-2*2N-2的稀疏矩阵,求它的逆矩阵是非常耗时的

 

 

可以在本方法的理论基础上,给出简化的计算方法,也就是接下来讲的迭代法

 

解法三:迭代法

迭代法的理论基础在解法二上

依次计算向量T1、T2、……、TM等等

若TM+1-TM≈0(若每个分量小于10-9,我们就认为两个向量相等),

 

还是以上面的示例为例(P1=0.7,P2=0.3,N=4)

 

T1=(0,0.7,0,0.3,0,0,0,0)

T2=(0.21,0,0.49,0,0.21,0,0,0.09)

T3=(0,0.294,0,0.126,0,0.147,0.343,0.09)

T4=(0.0882,0,0.3087,0,0.1323,0,0.343,0.1278)

T5=(0,0.15435,0,0.06615,0,0.09261,0.55909,0.1278)

T6=(0.046305,0,0.172872,0,0.074088,0,0.55909,0.147645)

T7=(0,0.0842751,0,0.0361179,0,0.0518616,0.6801004,0.147645)

T8=(0.02528253,0,0.09529569,0,0.04084101,0,0.6801004,0.15848037)

T9=(0,0.046286478,0,0.019837062,0,0.028588707,0.746807383,0.15848037)

T10=(0.013885943,0,0.05241263,0,0.022462556,0,0.746807383,0.164431489)

T11=(0,0.025443949,0,0.01090455,0,0.015723789,0.783496224,0.164431489)

T12=(0.007633185,0,0.028817417,0,0.012350321,0,0.783496224,0.167702854)

T13=(0,0.013988454,0,0.005995052,0,0.008645225,0.803668415,0.167702854)

T14=(0.004196536,0,0.015843576,0,0.006790104,0,0.803668415,0.169501369)

……

T71=(0,4.08706E-10,0,1.7516E-10,0,2.52594E-10,0.828302342,0.171697657)

T72=(1.22612E-10,0,4.6291E-10,0,1.9839E-10,0,0.828302342,0.171697658)

 

T72≈T71,故可以认为T=(0,0,0,0,0,0,0.828302342,0.171697658)

 

也就是甲获胜的概率是82.8302342%,乙获胜的概率是17.1697658%

 

本方法相比解法二,计算上来得简单,仅仅通过迭代计算(加加乘乘),就计算出最后的结果。相比求矩阵的逆来说,要简单的多。

相关文章
|
11月前
|
数据采集 人工智能 自然语言处理
Qwen-Video-8B与LLaMA-Factory联动实现垂类视频理解
Qwen-Video-8B联合LLaMA-Factory,通过垂类知识注入与多模态融合优化,提升视频时序理解与专业场景分析能力,助力城市风光、工业、教育等领域实现精准视频智能解析,推动通用模型向行业专用“视觉顾问”进化。
798 0
|
5月前
|
供应链 监控 Cloud Native
子不语 x Quick BI:“爆款飞轮”高速增长背后的数字化助推力
子不语集团(2420.HK)借助瓴羊Quick BI构建数字化底座,打通数据孤岛,将报表开发从两周缩至1天,支撑智能销售、库存预警与语义分析,年降本增效显著。
|
8月前
|
存储 监控 数据处理
浏览器自动化能干嘛?三个零门槛实操案例
本文介绍零代码浏览器自动化工具如何解放重复劳动:教培老师作业归档、个人账单统计、打印店接单等场景,仅需拖拽配置即可实现全自动操作。无需编程,识别按钮、提取数据、处理文件、自动回复一气呵成,每天轻松省下数小时。(239字)
|
编解码 人工智能 运维
南加大提出全新通用时间序列基础模型TimeDiT!基于扩散模型创新物理约束机制
 【10月更文挑战第10天】南加大提出TimeDiT模型,创新融合扩散模型与Transformer架构,针对真实世界时间序列数据的复杂性,如多分辨率、缺失值等问题,提供高效解决方案。该模型通过新颖的掩码机制和无微调编辑策略,实现多任务处理及物理知识集成,显著提升预测和异常检测的准确性和鲁棒性。
743 3
|
11月前
|
测试技术 芯片 C++
Python 安装
本文介绍Windows下安装Python 3.14.2的方法,包括版本选择、自定义安装选项、环境变量配置及安装验证,帮助用户快速搭建Python环境。
3859 8
Python 安装
|
10月前
|
弹性计算 人工智能 大数据
阿里云服务器是做什么的?ECS介绍及租赁配置价格整理,一文看懂~
阿里云ECS是IaaS级弹性计算服务,提供虚拟服务器,支持按需租赁、弹性扩缩容,适用于网站搭建、应用部署、大数据处理等场景,具备高可用、成本可控等优势,助力个人与企业高效上云。
1742 1
|
11月前
Excel工具-HUTOOL-读取Excel
Hutool提供ExcelReader封装,支持读取Excel为List、Map或Bean。针对大数据量,提供Excel03SaxReader和Excel07SaxReader,基于SAX模式高效流式读取,避免内存溢出,支持按行处理数据,适用于xls和xlsx格式。
318 0
|
机器学习/深度学习 数据采集 存储
技术赋能下的能源智慧管理:MyEMS 开源系统的架构创新与应用深化
在全球能源转型与“双碳”战略推动下,MyEMS作为基于Python的开源能源管理系统,凭借模块化架构与AI技术,助力重点用能单位实现数字化、智能化能源管理。系统支持多源数据采集、智能分析、设备数字孪生与自适应优化控制,全面满足国家级能耗监测要求,并已在制造、数据中心、公共建筑等领域成功应用,助力节能降碳,推动绿色可持续发展。
520 0
|
机器学习/深度学习 自然语言处理 搜索推荐
智能语音交互:技术原理与应用前景####
【10月更文挑战第25天】 一句话概括本文主旨,并引发读者兴趣。 智能语音交互技术,作为人工智能领域的重要分支,正以前所未有的速度融入我们的生活,从简单的语音助手到复杂的多轮对话系统,它不仅重塑了人机交互的方式,还为多个行业带来了革命性的变化。本文将深入浅出地探讨智能语音交互的技术原理、当前主流技术路线、面临的挑战及未来发展趋势,为读者揭开这一高科技领域的神秘面纱。 ####
|
算法 JavaScript 前端开发
84坐标系、02坐标系、百度坐标之间相互转换算法
最近有同学反馈之前的坐标系转换有问题,对之前的工具类进行了修正。 一、地图坐标转换java工具类 包含84坐标系、02坐标系、百度地图、高德地图、腾讯地图坐标之间相互转换的算法 wgs84ToGcj02:将 WGS84 坐标系下的经纬度转换为 GCJ02 坐标系下的经纬度。 gcj02ToWgs84:将 GCJ02 坐标系下的经纬度转换为 WGS84 坐标系下的经纬度。 gcj02ToBd09:将 GCJ02 坐标系下的经纬度转换为 BD09 坐标系下的经纬度。 bd09ToGcj02:将 BD09 坐标系下的经纬度转换为 GCJ02 坐标系下的经纬度。
2772 0
84坐标系、02坐标系、百度坐标之间相互转换算法