wayne 发表于 2019-1-10 14:41:05

群体狂乱全部死亡的概率是多少？

玩过《炉石传说》的可能好理解了。有这张卡牌，叫做群体狂乱，施用后，场上的$7$个随从，$1//1, 2//2,3//3, 4//4,5//5,6//6,7//7$将随机的互相攻击，直到剩下最后一个或者0个随从。问，场上随从全部都死亡的概率是多少？


简单说明：
1）一个随从的身材$n//m$,的意思就是说他的攻击力是$n$，体力值是$m$。
2）当一个随从$n//m$与另一个随从$x//y$战斗的时候，战斗结束后，二者各自的体力值分别是$m-x, y-n$，攻击力保持不变，即$n//m$变成了$n//(m-x)$，$x//y$变成了$x//(y-n)$。 当某随从体力值小于等于$0$的时候，立刻死亡。
3) 卡牌施用的时候，电脑将重复操作多次，每次随机挑选场上一名幸存的随从，攻击其他幸存的随从，死亡的随从将消失，不再投入战斗，直到场上幸存的随从个数小于2个。

lsr314 发表于 2019-1-10 16:17:08

不玩炉石，第三点里面，“每次随机挑选场上一名幸存的随从，随机攻击其他幸存的随从，直到场上幸存的随从个数小于2个”可否理解为：随机选两名幸存的随从，二者战斗，结束后重新随机选两名幸存的随从战斗，直到场上幸存的随从个数小于2个？

mathe 发表于 2019-1-10 16:56:52

计算结果是幸存一个人的概率是1/56700
如果总共只有2，3，4，5，6人，对应概率分别为1,1/3,1/18,1/180,1/2700
这是一个总状态数不超过8!的题目，穷举即可

wayne 发表于 2019-1-10 17:11:47

我自己写了个程序。穷举了下。
解释一下： 每一次战斗至少有一个随从死亡。原则上是攻击力小的随从必然死亡，攻击力大的随从有可能死亡。所以可以是7的全排列，根据路径挨个计算。

n = 7; Length[
Select[Table[{i,
    NestWhile[
   If[#[] ==
      0, {{Max[#[]],
         Abs]]]]}, #[]},
       If[#[] > #[],
      If[#[] > #[[2,
            1]], {{#[], #[] - #[]}, #[[2,
            2 ;; -1]]}, {{0,
         0}, #[]}], {{#[[2,
            1]], #[] - #[]}, #[]}]] &, {{0,
       0}, i}, ((#[] == 0 &&
          Length[#[]] > 1) || (#[] > 0 &&
          Length[#[]] > 0)) &]}, {i, Permutations]}],
Length[#[]] == 0 &]]

$n$个随从都被全部消灭，对应的概率如下：
{3,6,1,1.}
{4,12,1/2,0.5}
{5,72,3/5,0.6}
{6,624,13/15,0.866667}
{7,4152,173/210,0.82381}
{8,27172,6793/10080,0.673909}
{9,250052,62513/90720,0.689076}
{10,2839552,11092/14175,0.782504}

mathe 发表于 2019-1-10 17:17:08

看来我的理解和你不同，你是不是每次攻击结束，没死的人体力自动恢复?这样状态可以更少。我以为每次体力不恢复

mathe 发表于 2019-1-10 17:24:06

体力自动恢复肯定不对，因为最高体力者不死。查看三人情况，只有第一轮体力小的两人先对杀，三号选手才幸存，所以概率为1/3

mathe 发表于 2019-1-11 07:38:19

#include <gmpxx.h>
#include <iostream>
#include <stdio.h>
#define MAXN 9
#define DS   3628800/*10!*/
//v[]代表各人余下的体力值
//index2vec和vec2index在体力值分布和唯一编号之间转化
//由于第一个选手体力值只有0和1两种，第二个有0,1,2三种等等，所以可以使用
//v+2*(v+3*(v+...))里转化为一个紧凑的编号，使得不同的编号对应的体力值分布各不相同
void index2vec(int ind, char v)
{
    int i;
    for(i=0;i<MAXN;i++){
      v=ind%(i+2);
      ind/=i+2;
    }
}

int vec2index(const char v)
{
    int r=0;
    int i;
    for(i=MAXN-1;i>=0;i--){
       r*=(i+2);
       r+=v;
    }
    return r;
}

mpq_class data;//data保存标号为i的体力值分布下最终会余下一个人的概率，用分数表示

//这个函数计算编号为index的体力值分布最终会余下一个人的概率并且设置data
//这个函数假设对于所有i<index,data已经计算出
void set_data(int index)
{
    char v;
    int i,j;
    int c=0;
    index2vec(index, v);
    for(i=0;i<MAXN;i++)if(v>0)c++;
    if(c==0){
      mpq_class r(0);
      data=r;
      return;
    }
    if(c==1){
      mpq_class r(1);
      data=r;
      return;
    }
    c=0;
    mpq_class r(0);
    for(i=0;i<MAXN;i++)for(j=i+1;j<MAXN;j++){
       if(v>0&&v>0){
          c++;
          { //第i和第j个选手对攻的情况，需要注意第i个选手攻击力是i+1,而第j个选手的攻击力大于第i个选手的体力，所以第i个选手必然灭亡
            int old_vi=v,old_vj=v;v=0;
            v-=i+1;if(v<0)v=0;
            int new_index = vec2index(v);//计算相互攻击后的编号
            r+=data;//求各种攻击后状态的概率和
            v=old_vj;v=old_vi;//恢复状态
          }
       }
    }
    if(c==0){
       std::cerr<<"Invalid\n";
       exit(-1);
    }
    r/=c;//求概率的平均
    data=r;
}

void output_index(int index)
{
    char v;
    int i;
    int first=1;
    index2vec(index,v);
    std::cout<<'[';
    for(i=0;i<MAXN;i++){
      if(v!=0){
            if(first){ first = 0;}
            else std::cout<<' ';
            std::cout<<(int)v<<'/'<<i+1;
      }
    }
    std::cout<<"]==>"<<data<<'\n';
}

int main()
{
    int i;
    int curds=1, nextm=2;
    for(i=0;i<DS;i++){
       set_data(i);
       if(i==curds-1){
         output_index(i);
         curds*=nextm;nextm+=1;
       }
    }
    return 0;
}

mathe 发表于 2019-1-11 07:57:55

d=1/3
d=1/3
d=2/3
d=1
d=1/3
d=1/3
d=1/3
d=1/3
d=1/18
d=1/3
d=2/3
d=1
d=1/3
d=1/3
d=1/3
d=1/3
d=1/18
d=2/3
d=1
d=2/3
d=1
d=1
d=1/3
d=1/6
d=1/3
d=2/9
d=1/3
d=1/3
d=1/3
d=1/3
d=1/18
d=1/3
d=1/3
d=1/9
d=1/3
d=1/6
d=1/3
d=1/3
d=1/18
d=1/3
d=1/18
d=1/18
d=1/18
d=1/180
d=1/3
d=2/3
d=1
d=1/3
d=1/3
d=1/3
d=1/3
d=1/18
d=2/3
d=1
d=2/3
d=1
d=1
d=1/3
d=1/6
d=1/3
d=2/9
d=1/3
d=1/3
d=1/3
d=1/3
d=1/18
d=1/3
d=1/3
d=1/9
d=1/3
d=1/6
d=1/3
d=1/3
d=1/18
d=1/3
d=1/18
d=1/18
d=1/18
d=1/180
d=2/3
d=1
d=2/3
d=2/3
d=2/3
d=1/6
.......
d=1/56700
d=1/56700
d=1/1587600
d=1/180
d=1/2700
d=1/2700
d=1/28350
d=1/2700
d=1/18900
d=1/2700
d=1/28350
d=1/2700
d=1/18900
d=1/2700
d=1/18900
d=1/56700
d=1/529200
d=1/56700
d=1/396900
d=1/2700
d=1/2700
d=1/56700
d=1/2700
d=1/56700
d=1/56700
d=1/56700
d=1/1587600
d=1/2700
d=1/56700
d=1/56700
d=1/793800
d=1/56700
d=1/529200
d=1/56700
d=1/56700
d=1/1587600
d=1/56700
d=1/1587600
d=1/1587600
d=1/1587600
d=1/57153600

mathe 发表于 2019-1-11 11:03:39

前面计算的确不会，判断过程中遗漏了关键的同归于尽的中间过程
更新以后结果如下
d[]=0
d=1
d=1
d=1/3
d=5/18
d=14/45
d=23/100
d=563/5670
d=34933/793800
d=56059/2116800
d=3888637/285768000
代码只需要将set_data中 if(v>i+1)改为if(v>=i+1)

wayne 发表于 2019-1-11 19:14:49

mathe可否打印出有效的完整的战斗匹配的路径出来。
我发现我前面4#的计算有误。忽略了一种情况，就是每次战斗后，受伤的角色不一定在下一轮必然选上加入战斗。所以，实际上样本空间是$C_n^2C_{n-1}^2C_{n-2}^2C_{n-3}^2...$，考虑同归于尽的场合，最终的事件空间略小于这个数目。
{3,2,3,2/3}
{4,11,18,11/18}
{5,57,152,3/8}
{6,394,1696,197/848}
{7,6090,24068,3045/12034}
{8,151555,433660,30311/86732}
{9,4105581,9691096,4105581/9691096}


比如$n=8$的情况，我随便挑选了$20$组。
比如这种情况${{{2,2}},{{{7,7},{8,8}},{{1,1},{4,4}},{{5,5},{6,6}},{{4,3},{8,1}},{{3,3},{6,1}}}}$ ,最终幸存的是$2$号，体力值为$2$， 经历了$5$轮战斗，$(7,8), (1,4),(5,6),(4,8),(3,6)$
比如这种情况${{{5, 4}}, {{{2, 2}, {3, 3}}, {{3, 1}, {6, 6}}, {{6, 3}, {8, 8}}, {{4, 4}, {7, 7}}, {{7, 3}, {8, 2}}, {{1, 1}, {5, 5}}}}$ , 最终幸存的是$5$号，体力值为$4$， 经历了$6$轮战斗，$(2,3), (3,6),(6,8),(4,7),(7,8),(1,5)$
比如这种情况${{{8,1}},{{{1,1},{2,2}},{{2,1},{3,3}},{{3,1},{4,4}},{{4,1},{5,5}},{{5,1},{6,6}},{{6,1},{7,7}},{{7,1},{8,8}}}}$ ,最终幸存的是$8$号，体力值为$1$， 经历了$7$轮战斗，$(1,2), (2,3),(3,4),(4,5),(5,6),(6,7),(7,8)$
比如这种情况${{},{{{3,3},{5,5}},{{2,2},{4,4}},{{4,2},{6,6}},{{7,7},{8,8}},{{5,2},{6,2}},{{1,1},{8,1}}}}$ , 最终无人幸存， 经历了$6$轮战斗，$(3,5), (2,4),(4,6),(7,8),(5,6),(1,8)$

{{{2,2}},{{{7,7},{8,8}},{{1,1},{4,4}},{{5,5},{6,6}},{{4,3},{8,1}},{{3,3},{6,1}}}}
{{{5,4}},{{{2,2},{3,3}},{{3,1},{6,6}},{{6,3},{8,8}},{{4,4},{7,7}},{{7,3},{8,2}},{{1,1},{5,5}}}}
{{{8,1}},{{{1,1},{2,2}},{{2,1},{3,3}},{{3,1},{4,4}},{{4,1},{5,5}},{{5,1},{6,6}},{{6,1},{7,7}},{{7,1},{8,8}}}}
{{{7,3}},{{{1,1},{2,2}},{{6,6},{8,8}},{{2,1},{5,5}},{{3,3},{4,4}},{{4,1},{7,7}},{{5,3},{8,2}}}}
{{{6,3}},{{{3,3},{6,6}},{{1,1},{4,4}},{{4,3},{2,2}},{{4,1},{5,5}},{{7,7},{8,8}},{{8,1},{5,1}}}}
{{},{{{3,3},{5,5}},{{2,2},{4,4}},{{4,2},{6,6}},{{7,7},{8,8}},{{5,2},{6,2}},{{1,1},{8,1}}}}
{{},{{{1,1},{6,6}},{{2,2},{5,5}},{{7,7},{8,8}},{{8,1},{5,3}},{{4,4},{6,5}},{{6,1},{3,3}}}}
{{{5,5}},{{{6,6},{7,7}},{{1,1},{2,2}},{{3,3},{8,8}},{{2,1},{4,4}},{{4,2},{8,5}},{{8,1},{7,1}}}}
{{{5,1}},{{{4,4},{8,8}},{{8,4},{2,2}},{{3,3},{5,5}},{{6,6},{7,7}},{{1,1},{5,2}},{{7,1},{8,2}}}}
{{{7,4}},{{{4,4},{6,6}},{{1,1},{8,8}},{{2,2},{3,3}},{{6,2},{8,7}},{{3,1},{7,7}},{{5,5},{8,1}}}}
{{},{{{5,5},{6,6}},{{1,1},{8,8}},{{8,7},{3,3}},{{2,2},{4,4}},{{4,2},{6,1}},{{7,7},{8,4}}}}
{{},{{{1,1},{4,4}},{{3,3},{8,8}},{{4,3},{7,7}},{{5,5},{6,6}},{{6,1},{2,2}},{{7,3},{8,5}}}}
{{{7,1}},{{{4,4},{5,5}},{{1,1},{2,2}},{{6,6},{7,7}},{{2,1},{8,8}},{{8,6},{3,3}},{{8,3},{5,1}}}}
{{{8,2}},{{{3,3},{5,5}},{{1,1},{2,2}},{{5,2},{7,7}},{{2,1},{6,6}},{{4,4},{7,2}},{{6,4},{8,8}}}}
{{{5,5}},{{{1,1},{8,8}},{{4,4},{6,6}},{{3,3},{7,7}},{{6,2},{8,7}},{{2,2},{7,4}},{{7,2},{8,1}}}}
{{{6,1}},{{{1,1},{4,4}},{{4,3},{8,8}},{{3,3},{7,7}},{{5,5},{6,6}},{{2,2},{8,4}},{{8,2},{7,4}}}}
{{},{{{2,2},{8,8}},{{1,1},{7,7}},{{5,5},{8,6}},{{8,1},{3,3}},{{4,4},{6,6}},{{6,2},{7,6}}}}
{{{6,1}},{{{1,1},{5,5}},{{2,2},{6,6}},{{6,4},{3,3}},{{5,4},{7,7}},{{4,4},{8,8}},{{8,4},{7,2}}}}
{{},{{{5,5},{7,7}},{{1,1},{4,4}},{{3,3},{8,8}},{{2,2},{6,6}},{{7,2},{8,5}},{{4,3},{6,4}}}}
{{{7,3}},{{{5,5},{8,8}},{{2,2},{6,6}},{{6,4},{8,3}},{{1,1},{3,3}},{{3,2},{4,4}},{{4,1},{7,7}}}}


附上我的代码：
fight :=
Module[{pair = pair0},
Select[{{pair[], pair[] - pair[]}, {pair[],
   pair[] - pair[]}}, #[] > 0 &]
]

sss = Table[{n, data = {{{#, #} & /@ Range, {}}};
   Do[data =
   Flatten[Table[
       If]] > 1,
      Table[{Join, Complement], i]],
          Join], {i}]}, {i,
          Subsets], {2}]}], {round}], {round, data}],
      1], {n - 1}]; t = Select]] == 0 &];
   Length, Length, Length/Length, data}, {n, 1, 7}]

页: [1] 2
查看完整版本: 群体狂乱全部死亡的概率是多少？