万仓一黍个人页面-阿里云开发者社区

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

问题描述：甲乙两人比赛投篮。约定甲先投篮，每人投篮投进一球，则继续投球，若投失一球，则换人投球。初始积分为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）如图，比赛初始是在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的矩阵，如下图所示因为 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，如下图所示：由于TM=T0×AM，故在这儿分析AM 由于矩阵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就简化成如下形式对于矩阵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矩阵于是本问题就得出了结论，令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*分别为于是 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% 本方法相比解法二，计算上来得简单，仅仅通过迭代计算（加加乘乘），就计算出最后的结果。相比求矩阵的逆来说，要简单的多。

SharpDX之Direct2D教程II——加载位图文件和保存位图文件

本系列文章目录： SharpDX之Direct2D教程I——简单示例和Color（颜色）绘制位图是绘制操作的不可缺少的一部分。在Direct2D中绘制位图，必须先利用WIC组件将位图加载到内存中，再绘制到RenderTarget中去在SharpDX中绘制位图，分成两个部分：利用WIC在SharpDX中加载位图，生成Bitmap对象利用RenderTarget对象的DrawBitmap方法把Bitmap对象绘制到RenderTarget中去利用WIC在SharpDX中加载位图文件利用WIC在SharpDX中绘制位图文件的核心内容就是把位图文件转换为Bitmap对象。它的操作过程如下： 1、创建WIC的ImagingFactory类。 2、根据位图文件创建BitmapDecoder对象（实际上调用系统解码器解析位图文件）。 BitmapDecoder对象有1个属性和1个函数 FrameCount属性：只读属性，说明该位图对象包含的帧数。一般gif文件能包含多个帧，其余格式的一般只有1个帧 GetFrame函数：返回指定帧对象。参数index是整形，说明是第几帧（从0开始）。返回的是BitmapFrameDecode对象 3、利用BitmapDecoder对象的GetFrame函数，返回指定帧的BitmapFrameDecode对象。（参数index一般是0，返回第1帧）一般情况下，到此就可以了。但是，位图格式有很多，你可能不是很确定你的位图格式是否兼容SharpDX的Bitmap对象。因此，比较好的做法是继续下面的步骤，将位图格式转换为兼容SharpDX的Bitmap对象 4、创建FormatConverter对象。该对象负责进行格式转换。 5、调用FormatConverter对象的Initialize方法，进行格式转换。 6、最后，利用Bitmap对象的FromWicBitmap函数将之前的FormatConverter对象转换为SharpDX的Bitmap对象和Windows API Code Pack 1.1中的Direct2D略有不同的是，BitmapFrameDecode对象和FormatConverter对象都继承BitmapSource对象，省去了一个转换的过程下面是代码 Protected Function LoadBitmap(Render As D2D.RenderTarget, File As String, FrameIndex As Integer) As D2D.Bitmap Dim Decoder As New WIC.BitmapDecoder(_ImagingFactory, File, DX.IO.NativeFileAccess.Read, WIC.DecodeOptions.CacheOnLoad) If FrameIndex > Decoder.FrameCount - 1 OrElse FrameIndex < 0 Then FrameIndex = 0 Dim Source As WIC.BitmapFrameDecode = Decoder.GetFrame(FrameIndex) Dim Converter As New WIC.FormatConverter(_ImagingFactory) Converter.Initialize(Source, WIC.PixelFormat.Format32bppPBGRA) Return D2D.Bitmap.FromWicBitmap(Render, Converter) End Function 利用RenderTarget对象的DrawBitmap方法把Bitmap对象绘制到RenderTarget中去下面是DrawBitmap方法的原型定义： Public Sub DrawBitmap(bitmap As D2D.Bitmap, destinationRectangle As DX.RectangleF, opacity As Single, interpolationMode As D2D.BitmapInterpolationMode, sourceRectangle As DX.RectangleF) Public Sub DrawBitmap(bitmap As D2D.Bitmap, opacity As Single, interpolationMode As D2D.BitmapInterpolationMode) Public Sub DrawBitmap(bitmap As D2D.Bitmap, destinationRectangle As DX.RectangleF, opacity As Single, interpolationMode As D2D.BitmapInterpolationMode) Public Sub DrawBitmap(bitmap As D2D.Bitmap, opacity As Single, interpolationMode As D2D.BitmapInterpolationMode, sourceRectangle As DX.RectangleF) 参数的意义如下： bitmap：要绘制的Bitmap对象 destinationRectangle：绘制在RenderTarget对象上的目标范围。缺省是在RenderTarget对象的左上角，宽高是Bitmap对象的宽高 opacity：不透明度 interpolationMode：图像缩放时的插值算法，是个枚举 sourceRectangle：要绘制的源目标范围。缺省是Bitmap对象的整个范围下面是示例代码 Public Class clsSharpDXLoadBitmap Inherits clsSharpDXSampleBase Protected _ImagingFactory As WIC.ImagingFactory Public Shadows Sub CreateDeviceResource(Target As Control) MyBase.CreateDeviceResource(Target) _ImagingFactory = New WIC.ImagingFactory End Sub Public Function LoadBitmap(File As String, Optional FrameIndex As Integer = 0) As D2D.Bitmap Return LoadBitmap(_RenderTarget, File, FrameIndex) End Function Protected Function LoadBitmap(Render As D2D.RenderTarget, File As String, FrameIndex As Integer) As D2D.Bitmap Dim Decoder As New WIC.BitmapDecoder(_ImagingFactory, File, DX.IO.NativeFileAccess.Read, WIC.DecodeOptions.CacheOnLoad) If FrameIndex > Decoder.FrameCount - 1 OrElse FrameIndex < 0 Then FrameIndex = 0 Dim Source As WIC.BitmapFrameDecode = Decoder.GetFrame(FrameIndex) Dim Converter As New WIC.FormatConverter(_ImagingFactory) Converter.Initialize(Source, WIC.PixelFormat.Format32bppPBGRA) Return D2D.Bitmap.FromWicBitmap(Render, Converter) End Function Public Shadows Sub Render() With _RenderTarget .BeginDraw() .Clear(DX.Color.Honeydew.ToColor4) Dim B As D2D.Bitmap = LoadBitmap("216.png") .DrawBitmap(B, 1, SharpDX.Direct2D1.BitmapInterpolationMode.NearestNeighbor, New DX.RectangleF(0, 0, 260, 260)) .EndDraw() End With End Sub End Class 利用WIC保存图片 WIC既能负责图片的解码，也能负责图片的编码。我们也可以利用WIC编码图片。在调试的时候出了问题，先看看下面两段代码 Public Class Class1 Public Shared Sub Test() Dim wicFactory As WIC.ImagingFactory = New WIC.ImagingFactory Dim F As String = "333.png" If (File.Exists(F)) Then File.Delete(F) Dim spStream As WIC.WICStream = New WIC.WICStream(wicFactory, F, NativeFileAccess.Write) Dim spBitmapEncoder As WIC.PngBitmapEncoder = New WIC.PngBitmapEncoder(wicFactory) spBitmapEncoder.Initialize(spStream) End Sub End Class 上面的代码是用VB2010写的，仅仅写到PngBitmapEncoder对象的Initialize方法。再看看下面这段代码，用的是C# 2010写的 class Class1 { public static void test() { ImagingFactory wicFactory = new ImagingFactory(); string F = "333.png"; if (File.Exists(F)) File.Delete(F); WICStream stream = new WICStream(wicFactory, F, NativeFileAccess.Write); PngBitmapEncoder encoder = new PngBitmapEncoder(wicFactory); encoder.Initialize(stream); } } 可以看出，两段代码没什么不同（仅仅是语法上的不同而已），但是VB2010的代码在执行到Initialize时总是报错（内部错误），而C#2010在执行到Initialize方法很顺利的完成了。两段代码引用的是同一个动态库SharpDX的2.5.0的库。我解释不出是什么原因，只能归结于SharpDX自身的原因了。不过，我发现一个问题，写在这儿，给大家一个参考，也许谁能给出解决方案。（或者是我的设置有问题？）在VB2010中，PngBitmapEncoder类的初始方法只能看到两个，New(Object)和New(IntPtr) 在C#2010中，PngBitmapEncoder类的初始方法能看到六个，除了上面的两个，还多了很多打开SharpDX.Direct2D1.xml中也看到PngBitmapEncoder对象的初始方法有六个难道SharpDX真的不能很好的运用于VB2010中么？最后贴一段SharpDX中自带示例中的WIC保存图片的代码 using System; using System.IO; using SharpDX; using SharpDX.Direct2D1; using SharpDX.DXGI; using SharpDX.IO; using SharpDX.WIC; using AlphaMode = SharpDX.Direct2D1.AlphaMode; using Bitmap = SharpDX.WIC.Bitmap; using PixelFormat = SharpDX.Direct2D1.PixelFormat; namespace RenderToWicApp { internal static class Program { private static void Main() { var wicFactory = new ImagingFactory(); var d2dFactory = new SharpDX.Direct2D1.Factory(); string filename = "output.png"; const int width = 512; const int height = 512; var rectangleGeometry = new RoundedRectangleGeometry(d2dFactory, new RoundedRectangle() { RadiusX = 32, RadiusY = 32, Rect = new RectangleF(128, 128, width - 128 * 2, height-128 * 2) }); var wicBitmap = new Bitmap(wicFactory, width, height, SharpDX.WIC.PixelFormat.Format32bppBGR, BitmapCreateCacheOption.CacheOnLoad); var renderTargetProperties = new RenderTargetProperties(RenderTargetType.Default, new PixelFormat(Format.Unknown, AlphaMode.Unknown), 0, 0, RenderTargetUsage.None, FeatureLevel.Level_DEFAULT); var d2dRenderTarget = new WicRenderTarget(d2dFactory, wicBitmap, renderTargetProperties); var solidColorBrush = new SolidColorBrush(d2dRenderTarget, Color.White); d2dRenderTarget.BeginDraw(); d2dRenderTarget.Clear(Color.Black); d2dRenderTarget.FillGeometry(rectangleGeometry, solidColorBrush, null); d2dRenderTarget.EndDraw(); if (File.Exists(filename)) File.Delete(filename); var stream = new WICStream(wicFactory, filename, NativeFileAccess.Write); var encoder = new PngBitmapEncoder(wicFactory); encoder.Initialize(stream); var bitmapFrameEncode = new BitmapFrameEncode(encoder); bitmapFrameEncode.Initialize(); bitmapFrameEncode.SetSize(width, height); var pixelFormatGuid = SharpDX.WIC.PixelFormat.FormatDontCare; bitmapFrameEncode.SetPixelFormat(ref pixelFormatGuid); bitmapFrameEncode.WriteSource(wicBitmap); bitmapFrameEncode.Commit(); encoder.Commit(); bitmapFrameEncode.Dispose(); encoder.Dispose(); stream.Dispose(); System.Diagnostics.Process.Start(Path.GetFullPath(Path.Combine(Environment.CurrentDirectory,filename))); } } }

万仓一黍个人页面-阿里云开发者社区

个人介绍

擅长的技术

利用HTML实现软件的UI

基于Bootstrap的DropDownList的JQuery组件的完善版

用PS设计等高线效果的背景图片

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

SharpDX之Direct2D教程II——加载位图文件和保存位图文件

遍历组合的实现——VB2005

ASP小贴士/ASP Tips

自动识别文字的编码以及读取所有文本——VB2005

正则表达式——去除文本中的非汉字（VB2005）

遍历排列的实现——VB2005

计算机中的颜色I——颜色概述

计算机中的颜色II——VB2005中的Color结构

计算机中的颜色III——HSV表示方法

计算机中的颜色IV——纯色、色相色

计算机中的颜色V——快速计算颜色的色相值

交换函数的陷阱——VB2005

ASP中的EVAL函数

计算字符串的相似度（VB2005）

一道有趣的面试题

计算机中的颜色VII——快速计算纯色的偏转

计算机中的颜色VIII——快速计算颜色的偏转

博客园随笔添加自己的版权信息

计算机中的颜色X——两颜色的偏转值

IQCar的实现II——解题思路

高亮显示不区分大小写的关键字——ASP