屠龙刀的概率升级问题

wayne

在纸上画了一下升级过程的决策二叉树,很有规律

wayne

10# 056254628
设g(n,m) 表示经过n次升级后级别为m的所有可能情况，
升级到9级将停止尝试升级。
则

g（n，1）=g（n-1,2）+g（n-1,1）
g（n，9）=g（n-1,8）
g（n，8）=g（n-1,7）
g（n，k）=g（n-1,k-1）+g（n-1,k+1）

可以算出，n次升级后，仍然停留在1级的情况有
g(n,1) = C(n,floor(n/2))  种
，然后所有的情况都可以用g(n,1) 表达

056254628

楼上的计算公式与概率无关，必然得不到正确的结果。

zYr

这样如何 直接模拟这个过程

1. 
   
2. void main()
   
3. {
   
4.         double n=1,k=0;        //n为实验总次数 k为实验成功（即1000次内升到九级）的次数
   
5.         int shiyan();
   
6.         double p;                        //p为概率
   
7. C:
   
8.         n++;
   
9.         int b=shiyan();       
   
10.         if (b)
    
11.         {
    
12.                 k++;
    
13.         }
    
14.         p=k/n;
    
15.         cout<<p<<endl;
    
16.         goto C;
    
17. }
    
18. 
    
19. int shiyan()
    
20. {
    
21.         int l=1;        //l为屠龙刀等级
    
22.         int i=1;        //升级次数
    
23.         int roll();
    
24.         while(i<=1000)        //执行1000次升级操作
    
25.         {
    
26.                 int r=roll();
    
27.                 if (r<=3)                //30%
    
28.                 {
    
29.                         l++;
    
30.                 }
    
31.                 else                        //70%
    
32.                 {
    
33.                         if(l==1)
    
34.                         {
    
35.                                 l=1;
    
36.                         }
    
37.                         else
    
38.                         {
    
39.                                 l--;
    
40.                         }
    
41.                 }
    
42.                 if (l==9)
    
43.                 {
    
44.                         break;
    
45.                 }
    
46.                 else
    
47.                 {
    
48.                         i++;
    
49.                 }
    
50.         }
    
51.         if (l==9)        //实验成功
    
52.         {
    
53.                 return 1;
    
54.         }
    
55.         else                //实验失败
    
56.         {
    
57.                 return 0;
    
58.         }
    
59. }
    
60. 
    
61. int roll()        //随机一个1到10的整数
    
62. {
    
63.         srand( (unsigned)time( NULL ) );
    
64.         int num = 1 + rand() % 10;
    
65.         return num;
    
66. /*
    
67. 这个随机数的函数目前没想好
    
68. C语言不支持随机数
    
69. 用时间作种子做伪随机数的话
    
70. 要是程序执行得太快 1秒内就跳出了循环
    
71. 随机数就一样了 会影响结果
    
72. 我用上面的伪随机数代码做了一下 概率大概在0.3左右
    
73. */
    
74. }
    

复制代码

zYr

电脑计算的速度确实太快了
一秒钟能做好几遍
我又试了几次概率大概在0.35附近
我觉得0.3几比较符合经验
用那么多次机会升8级应该也就这么大概率 但肯定不够精确
因为电脑会因一次随机结果给k和n都连续自加好几次 或只给n连续自加好几次
要是能改进随机数的算法就好了

zYr

换了一下代码

1. int roll()
   
2. {
   
3.         srand( (unsigned)time( NULL ) );
   
4.         int num = 1 + (rand() * ((int)n + (int)k) + ((int)n * (int)k)) % 10;
   
5.         return num;
   
6. }

复制代码

我用双核笔记本开了10个控制台同时运行
开始几分钟不知为何 十个的结果都在0.15上下浮动
后来在某一时刻后先后开始有规律地上涨 到0.3几
小数点后第二位一直浮动较大
直到大概90分钟以后才比较稳定
但小数点后第三位的变化还经常变动
为什么在运行这么长时间以后每次实验还会对概率有比较大的影响？
会不会n自加超过double型的范围了？

zYr

有图有真相

KeyTo9_Fans

设矩阵$A=[(0.7,0.3,0,0,0,0,0,0,0),(0.7,0,0.3,0,0,0,0,0,0),(0,0.7,0,0.3,0,0,0,0,0),(0,0,0.7,0,0.3,0,0,0,0),(0,0,0,0.7,0,0.3,0,0,0),(0,0,0,0,0.7,0,0.3,0,0),(0,0,0,0,0,0.7,0,0.3,0),(0,0,0,0,0,0,0.7,0,0.3),(0,0,0,0,0,0,0,0,1)]$，

然后计算$A^1000$，结果记为$P$。

即$P=A^1000$。

然后取$P$的第$1$行第$9$列就是最终结果。

KeyTo9_Fans

zYr：

“srand(time( NULL ));”语句只能执行$1$次，不能多次执行。

由于你多次执行该语句，导致随机数质量太差，结果误差很大。

正确结果应该是$0.228556827413$。

$19#$的参考代码：

1. #include<cstdio>
   
2. #include<memory>
   
3. 
   
4. double a[9][9],b[9][9],c[9][9];
   
5. int i,j,k;
   
6. 
   
7. void mult()
   
8. {
   
9.         for(i=0;i<9;i++)
   
10.                 for(j=0;j<9;j++)
    
11.                 {
    
12.                         c[i][j]=0;
    
13.                         for(k=0;k<9;k++)
    
14.                                 c[i][j]+=a[i][k]*b[k][j];
    
15.                 }
    
16.         memcpy(a,c,sizeof(c));
    
17. }
    
18. 
    
19. void p10()
    
20. {
    
21.         memcpy(b,a,sizeof(a));
    
22.         mult();
    
23.         memcpy(b,a,sizeof(a));
    
24.         mult();
    
25.         mult();
    
26.         mult();
    
27.         mult();
    
28. }
    
29. 
    
30. int main()
    
31. {
    
32.         for(i=1;i<8;i++)
    
33.         {
    
34.                 a[i][i-1]=0.7;
    
35.                 a[i][i+1]=0.3;
    
36.         }
    
37.         a[0][0]=0.7;
    
38.         a[0][1]=0.3;
    
39.         a[8][8]=1;
    
40.         p10();
    
41.         p10();
    
42.         p10();
    
43.         printf("%.12lf\n",a[0][8]);
    
44.         return 0;
    
45. }

复制代码

输出结果：

1. 0.228556827413

复制代码

wayne

19# KeyTo9_Fans
漂亮，状态转移矩阵比递推公式的表达更简洁。