全部情况的打书概率与期望计算详解

a129312931293

这是致敬 oO0檐水穿墙 大神的帖子，使用数学方式来展现打书的本质。首发在贴吧

a129312931293

首先确立一个原则：当我们用若干种兽决来打书时，总是从价值最低的书打到价值最高的书。
这个原则不管特殊技能是否存在，都成立。因为当打书完成时，越早打的书，总是承担越高地被打掉的风险，所以为了使总成本最低，必定是先打价值低的书。而当存在须弥等特殊技能时，也不认为不遵守该原则有什么收益。
既然这个原则成立，那么我们发现，只要当宝宝处于一种技能状态时，总是会去打固定的书 （并不相信所谓打书技巧，因为没有任何理由认为某种状态是特殊的，故打书掉的技能应该是完全随机的，即每个技能掉的概率相同）。通俗地讲，当我们打第二本书却掉了第一本时，我们只会选择下一本打掉了的第一本，而不会选择其他。

a129312931293

此时，若我们将宝宝的技能状态的所有可能性记作一个状态空间，那么每次打书实际上就是状态空间之间的概率转移，而且这种转移是确定的（因为打的书是确定的，而打书掉的技能概率是平均的，同时也是确定的），所以可以作出一个马尔科夫链。故每一种打书都是某种形式的马尔科夫链，计算目标的概率和成本期望的关键就是得出状态空间的概率转移矩阵。
为了使概率转移矩阵直观且易于计算，必须选择恰当的状态空间。由于在打书的过程中，我们不关心技能的顺序关系（没有打书玄学），同时，我们也不关心那些预计被顶替的技能是什么。
所以，可以用0和1来表示没有打上某本书或者打上了某本书。而根据前面的原则，我们打书是有一个固定的顺序的，将打书的顺序从后往前排，就可以用0和1的序列来表达宝宝当前的技能状态。比如，我们打书的顺序是1.偷袭2.必杀3.夜战4.吸血，那么1010就表示目前状态是四个格子中，有吸血无夜战有必杀无偷袭。以这种表示方式，我们就能用二进制数字来表达宝宝目前的状态了。对于任意一种打书，我们都能得到相应的状态空间。比如5个格子的宝宝，要打上必连夜偷吸，那么就用00000-11111总共2^5次方种（即32种）状态来表示。然后，我们可以发现，状态的概率转移矩阵变得显而易见了。

裸奔的蛋蛋

有吸血无夜战有必杀无偷袭

a129312931293

1. 先从简单的例子开始演示，比如四蓝鬼将的打书，打书状态有16种，概率转移矩阵是16*16的矩阵，如下：
这个矩阵生成的matlab代码如下：

>> x=zeros(16)
x(1,1)=1
for i=2:16
x(:,i)=B*x(:,i-1)
End
第一行到第十六实际表示了0000的状态到1111的状态。其中第i行j列项数据的意思是，从i这个状态打一本书的话（实际上已经确定是某本了），到达j这个状态的概率。
那么我们从某种状态出发打书，实际就是将上面这个矩阵（记为B）与当前的概率状态向量相乘，比如我们从四个垃圾技能开始打四蓝，就是将B不断与x=（1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0）的转置作矩阵乘法（从其他状态出发，只需要将1放到相应位置），下面作一个演示：
这个表说明的是，从第一次打书到第十五次打书，得到各个状态的技能的概率，第j列的数据就是打书j-1次以后各个状态的概率分布，可以看到，打10本书内得到四蓝鬼将的概率是78.06%，打15本书内得到四蓝鬼将的概率是94.67%。这样，我们已经得到了打书k本内得到目的技能状态的概率了，但是，如果我们想知道平均需要打几本书才能得到一个四蓝鬼将，就要用另外一种算法，给出matlab代码：
>> S=0,c(1,1:16)=1,c(1,16)=0
x(1:16,:1)=0,x(1,1)=1
for i=0:99
S=S+c*B^i*x
End
可以得到结果S=8.3333……，把99换更大的数，结果依然不变，因为期望是收敛的。这里的x是初始状态，c是成本向量，这里为了算打书数目，故统一为1，表示除了最后打书成功的状态不用打书以外，其他状态都需要打1本书。
如此，我们就已经知道所有打书方式的概率计算了（有特殊技能的情况在下面讨论），若是改书，则只需要改变计算时的初始状态，若不需要全部书都打上，只要满足一定情况就能用，也只需要稍微改变成本向量和概率矩阵，关于概率矩阵的改变和生成方法，将在下面给出。

a129312931293

然后讨论完成打书所需要的成本计算问题，这个由上一段代码即可计算，不过需要对成本向量作出具体修正，假设偷袭61w，必杀62w，夜战63w，吸血64w，那么成本向量c应当如下：
c=（61,62,61,63,61,62,61,64,61,62,61,63,61,62,61,0）
即使对于更大的状态空间，或者不同的数值，也可以用简单的操作得出成本向量，具体操作根据具体问题而定，这里就不给出了。

a129312931293

现在，我们有一个问题，怎么对任意数量的格子，给出相应的概率转移矩阵呢？当有n个格子时，我们容易知道，需要求出一个2^n*2^n的方阵，这里给出一种生成函数：
function [A] = creat(n)
A=zeros(2^n);
for i=1:2^n-1
number=i-1;
c=bitget(number,1:n);
m=find(c);
k=find(c==0,1);
t=sum(c);
A(i+2^(k-1),i)=(n-t)/n
for q=1:t
A(i+2^(k-1)-2^(m(q)-1),i)=1/n;
end
end
A(2^n,2^n)=1;
end
其中，n为技能数目，当然不要输入太大的数（比如在一般的家庭电脑输入10以上），因为会因为内存空间不足而卡死电脑或者申请时间过长。（当然在matlab中使用多重for是很难受的事，但这里为了省事，直接这样写）

a129312931293

最后，就是关于有特殊技能的情况了，这种情况需要对概率转移矩阵作改造
比如，对8技能的须弥胚子打书，则用00000001来表示只有须弥，没有其他辅助书，那么当打书打到须弥没了的时候，我们就认为打书已经完成，没有打书的必要了，所以最后一位为0的数（即偶数）的状态就全部为吸收态，用下面的代码改造：
>> K=creat(8)
>>for i=3:2:255
K(:,i)=0;
K(i,i)=1;
end
这样得到的矩阵K就是8技能须弥打书的概率转移矩阵，K^i的第j列，表示打书i-1次后，从j的状态出发，得到的状态的概率分布。我们由此可以算出从任意状态出发打书任意次后的状态概率了。而且，由于打书次数较大时，状态必然趋向稳定，故可以算出不计成本打书，打成这个胚子的概率。

比如上表就说明了4技能须弥打书15次后，从不同状态出发的话，得到的状态概率。

a129312931293

再提供几个小场景：

作为一个09平民，想要一个爆炸资质的宝宝，当然要选变异鬼将，但是攻宠五大技能，必连夜吸偷，起码要打4个蓝技能（强烈建议连击用高连套，不要用连击打宝宝上面），但是现在我有两只鬼将可以选择，一只是没打书的四技能满攻满成长鬼将，一只是打完4技能的鬼将，但是比第一只贵，作为一个运气不好不坏的平民，应该选择哪只呢？

答案：请把蓝书价格*8.333加到没打书的鬼将身上，再比较

a129312931293

作为一个09平民，变异鬼将用得好好的，被楼主蛊惑，认为连击是辣鸡，要改书成必夜偷吸，那么到底平均要花多少钱呢？

答案：平均要打4本蓝书

a129312931293

作为一个09大爷，我就是喜欢变异鬼将的帅气，我就是忍受不了一点蓝色，我就是要打4技能全红！但是，作为一个机智的大爷，我想知道打书到底按什么顺序打，花的钱预计最少。

答案：从最便宜的打到最贵的

a129312931293

作为一个09大爷，我现在知道按什么顺序打红书了，但是我有一组五开号，我要全部配上4红鬼将，我要打很多次，所以要算算到底一般需要多少钱，方便我充钱，那么成本到底是多少呢？

答案：假设按a，b，c，d的顺序拍书，那么打一个四技能全红鬼将的成本是2.4666*a+2.2666*b+2.0*c+1.6*d

我来说句公道话

答应我，日后请继续这么吊！