|
|
发表于 2009-8-1 21:36:00
|
显示全部楼层
Re:求教一个装备精练+10的概率问题！数值高手请帮忙看看
楼主说“平均”的含义就是求数学期望。
如果失败不掉级，用古典概率方法直接求就行了。就题目而论题目，最简单的就是1颗宝石“平均”相当于升1×0.6 + 0×0.4=0.6级，升10级就需要10/0.6=16.667。前面已经有同学给出答案了。精确些的公式我是这样推的：
1） 题目的意思即是求升10级恰好需要10，11，12，…，n-1，n颗宝石概率，这些概率再分别乘以所需的宝石数，即求其数学期望。
2） 我们看n个宝石升级序列（O表示成功，×表示失败）：
×××OOOO××××………O
只要O的数目达到10个就ok了。并且最后一个格必须是O。这样的序列组合是数目是C(n-1, 9)，所以恰好需要n颗宝石的概率就是(p表示成功的概率)：
P (n)= C(n-1, 9)×( p^10 )×( (1-p)^(n-10) ) ， n>=10
这是个无穷数列，从n=10开始，计算该数列和为1，说明我们所计算的事件是一个完备空间，可以肯定没有算错哈。
3) 其数学期望为：
E = 10× (10) + 11×P(11) + 12×P(12)……
算得结果为16.667。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
第二题的思路是受到25楼的荒原开导才知道可以这样做的，所以专门去看了相关的教科书恶补了下。荒原给出了开始和结果，中间的部分我把自己的理解给出，节省有兴趣的但无相关知识的人学习时间哈。
先利用第一题的方法估计一下上限。E = 10 / ( P×0.6+( -1×0.4) ) = 50。该期望值最多不超过50，因为按照这个公式的话，装备降到0级还可以继续下降到-1，-2级，如此的话就需要更多的宝石来补正了。所以上限为50。可以作为结果是否正确的大致估算。
该题是有一个反射壁和一个吸收壁的马尔可夫过程。我们可以在数轴上假设0为装备0级，10为装备10级，有一个点s在0-10之间游动。每次可以移动一格，有60%的概率向右走，有40%的概率向左走，碰到0会反弹，遇到10就被吸收了。
接下来该需要了解转移矩阵的意思。参看25楼给出的第一个矩阵图：
0.4 0.6 0 0 0 0 0 0 0 0 0
0.4 0 0.6 0 0 0 0 0 0 0 0
0 0.4 0 0.6 0 0 0 0 0 0 0
0 0 0.4 0 0.6 0 0 0 0 0 0
0 0 0 0.4 0 0.6 0 0 0 0 0
0 0 0 0 0.4 0 0.6 0 0 0 0
0 0 0 0 0 0.4 0 0.6 0 0 0
0 0 0 0 0 0 0.4 0 0.6 0 0
0 0 0 0 0 0 0 0.4 0 0.6 0
0 0 0 0 0 0 0 0 0.4 0 0.6
0 0 0 0 0 0 0 0 0 0 1
转移矩阵P的每一行，每一列代表0，1，2…10装备等级状态。对于某个点，比如第2行第3列位置其值为0.6，表示的是s原来处在处在装备等级状态1的位置，下一次会游动到装备等级2的位置的概率为0.6。再如第2行第4列位置其值为0，即表示从等级1游动到等级3的概率为0（显然的，因为每次只能移动一格）。P^n代表的游走n步后，从状态i转移到状态j的概率。
再来了解禁忌概率矩阵。就本题而论，就是把转移矩阵中的吸收态（装备等级10）去掉后所剩余的状态再组成一个矩阵R。
0.4 0.6 0 0 0 0 0 0 0 0
0.4 0 0.6 0 0 0 0 0 0 0
0 0.4 0 0.6 0 0 0 0 0 0
0 0 0.4 0 0.6 0 0 0 0 0
0 0 0 0.4 0 0.6 0 0 0 0
0 0 0 0 0.4 0 0.6 0 0 0
0 0 0 0 0 0.4 0 0.6 0 0
0 0 0 0 0 0 0.4 0 0.6 0
0 0 0 0 0 0 0 0.4 0 0.6
0 0 0 0 0 0 0 0 0.4 0
本题中禁忌概率矩阵即是那些从i游走到j而不经过吸收态（等级10）的概率矩阵（这样不严谨，将就先吧）。
从禁忌概率推算出从某一状态i到吸收态的数学期望矩阵公式如下：
E = R + R^2 + R^3 + … + R^n
该矩阵E中的第一行之和即是从等级0升到等级10的期望，第二行之和是从等级1升到等级10的期望，依次类推。
3.9130 4.8695 4.8044 4.7067 4.5603 4.3407 4.0114 3.5176 2.7770 1.6662
3.2464 3.8696 4.8044 4.7068 4.5603 4.3408 4.0115 3.5177 2.7771 1.6662
2.1353 3.2030 3.8045 4.7068 4.5604 4.3409 4.0116 3.5178 2.7772 1.6663
1.3946 2.0919 3.1379 3.7069 4.5605 4.3410 4.0117 3.5179 2.7773 1.6663
0.9008 1.3512 2.0269 3.0404 3.5606 4.3411 4.0119 3.5180 2.7774 1.6664
0.5716 0.8574 1.2862 1.9293 2.8941 3.3412 4.0120 3.5182 2.7775 1.6665
0.3522 0.5283 0.7924 1.1887 1.7830 2.6747 3.0121 3.5183 2.7776 1.6665
0.2059 0.3088 0.4632 0.6949 1.0424 1.5636 2.3455 2.5184 2.7776 1.6666
0.1084 0.1625 0.2438 0.3657 0.5486 0.8230 1.2345 1.8518 1.7777 1.6666
0.0433 0.0650 0.0975 0.1463 0.2194 0.3292 0.4938 0.7407 1.1111 0.6666
本题求第一行的和结果为：40.1669。
具体如何得出这个公式大家自己也看看去哈，其中有些证明步骤我也还没搞清楚。
以下用lua写的计算代码（在学这个就顺手用了^_^），写的差，不入法眼莫生气。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
function w(n,k)
if (n<k or n==0) then
print("wrong input w")
return -1
end
local num=1
for v=k, n do
num = num*v
end
return num
end
--组合公式
function c(n,k)
if (n<k or n==0) then
print("wrong input c")
return -1
end
if(n==k) then
return 1
end
local num = w(n,n-k+1)/w(k,1)
return num
end
--2个n阶矩阵相乘
function matrixmult(matrixa,matrixb, nv)
local out = {}
local i, j, k = 1, 1, 1
while(i <= nv) do
out = {}
while(j <= nv) do
out[j] = 0
while(k <= nv) do
out[j] = out[j] + matrixa[k]*matrixb[k][j]
k = k + 1
end
j = j + 1
k = 1
end
i = i + 1
j = 1
end
return out
end
--矩阵的n次幂
function matrixpow(matrix, nv, n)
local out = matrix
local i = 1
while(i < n) do
out = matrixmult(out, matrix, nv)
i = i + 1
end
return out
end
--2个矩阵相加
function matrixadd(matrixa, matrixb, nv)
local out = {}
local i, j = 1, 1
while(i <= nv) do
out = {}
while(j <= nv) do
out[j] = matrixa[j] + matrixb[j]
j = j + 1
end
i = i + 1
j = 1
end
return out
end
--构造n阶单位矩阵
function imatrix(nv)
local im = {}
local i, j = 1, 1
while(i <= nv) do
im = {}
while(j <= nv) do
if(j~=i) then
im[j] = 0
else
im[j] = 1
end
j = j + 1
end
i = i + 1
j = 1
end
return im
end
--构造n阶零矩阵
function zeromatrix(nv)
local out = {}
local i, j = 1, 1
while(i <= nv) do
out = {}
while(j <= nv) do
out[j] = 0
j = j + 1
end
i = i + 1
j = 1
end
return out
end
--n阶矩阵转置,nv是输入矩阵维度
function tranmatrix(matrix, nv)
local out = imatrix(nv)
local i, j = 1, 1
while(i <= nv) do
while(j <= nv) do
out[j] = matrix[j]
j = j + 1
end
i = i + 1
j = 1
end
return out
end
--判断一个状态不属于目标态（一般指吸收态）
function isset(args,a)
for i, v in ipairs(args) do
if (a == v) then
return false
end
end
return true
end
--截取矩阵的某一子集,即除去某些状态集后剩余的状态组成的概率转移矩阵,也就是禁忌概率矩阵
function clipmatrix(v, matrix, ...) --v是输入矩阵维度
local out = {}
local i, j = 1, 1
local i1, j1 = 1, 1
while (i <= v) do
if(isset(arg, i)) then
out[i1] ={}
while(j <= v) do
if(isset(arg, j)) then
out[i1][j1] = matrix[j]
j = j + 1
j1 = j1 + 1
else
j = j + 1
end
end
j = 1
i = i + 1
j1 = 1
i1 = i1 + 1
else
j = 1
i = i + 1
end
end
return out
end
--------------------------------------------------------------------------------------
--题目2：升级失败，装备等级下降一级（下限为0），共10级，每次升级成功概率60%
--------------------------------------------------------------------------------------
--增加一个宝石，可能达到一个新的状态，也可能回到过去的状态，各个状态之间可以相互转移
--该状态空间是有限的，目标是从某一初态到某一终态的首达概率。应用到马尔可夫链的知识。
--构造n=1状态的转移矩阵，一个吸收壁，一个反射壁
m = {}
m[1] = {0.4, 0.6, 0, 0, 0, 0, 0, 0, 0, 0, 0,}
m[2] = {0.4, 0, 0.6, 0, 0, 0, 0, 0, 0, 0, 0,}
m[3] = {0, 0.4, 0, 0.6, 0, 0, 0, 0, 0, 0, 0,}
m[4] = {0, 0, 0.4, 0, 0.6, 0, 0, 0, 0, 0, 0,}
m[5] = {0, 0, 0, 0.4, 0, 0.6, 0, 0, 0, 0, 0,}
m[6] = {0, 0, 0, 0, 0.4, 0, 0.6, 0, 0, 0, 0,}
m[7] = {0, 0, 0, 0, 0, 0.4, 0, 0.6, 0, 0, 0,}
m[8] = {0, 0, 0, 0, 0, 0, 0.4, 0, 0.6, 0, 0,}
m[9] = {0, 0, 0, 0, 0, 0, 0, 0.4, 0, 0.6, 0,}
m[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0.4, 0, 0.6,}
m[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,}
--计算转移矩阵m的9，10，11......n-1，n次幂，分别求出使用n+1颗宝石能够冲到11级的概率并不能如
--题1计算数学期望就可得出答案。这里的各部分概率是转移概率，当n为固定值时，同一行的概率才会构成完备空
--间，不同的n，取某一位置的值的概率组合无意义（我们需要的是首次到达11级的概率，而转移概率计算了n步中
--可能到达过11级的次数）。实际上随着转移矩阵的自相乘次数越来越多将会发现吸收态的转移概率越来越高，本
--题的吸收态即11级处，num[11]列的值逐渐接近1，意味着n趋向无穷大时，吸收态的概率将为1。
--转移矩阵m的n次幂即表示经过n次转移（使用n颗宝石）后，下一次到达各个参数状态（1-11级装备）的转移概率
--nums[1][x]表示使用n+1颗宝石能够从1级升到x级的概率
test = clipmatrix(11, m, 11) --禁忌概率矩阵
function E(n)
local out = zeromatrix(10)
local i = 1
while(i <= n)do
out = matrixadd(matrixpow(test, 10, i), out, 10)
i = i + 1
end
return out
end
nums = E(200)
for i=1, 10 do
print(nums[1], nums[2], nums[3], nums[4], nums[5], nums[6], nums[7], nums[8], nums[9], nums[10])
end
k = 1
for i=1, 10 do
k = nums[1] + k
end
print(k) --k为40.1669 此即为从零级升到10级平均需要的宝石数
一年了,有个错误...改之...
E = R^0 + R + R^2 + R^3 + … + R^n
|
|
