醉酒螳螂问题

怼烎@ 2022-08-27 04:43 19阅读 0赞

醉酒螳螂问题

记得去年上概率论的时候最后一章讲述的是马尔科夫过程，当时只会做题。完全不知道这是干甚么。其实就是矩阵的遍历性问题。今天介绍的醉酒螳螂也是关于遍历性的问题。  
        1.问题叙述：  
            在矩形的房间里，铺有m \* n块瓷砖，现将一只（醉酒的）螳螂放在地板中间一个指定的方格里，螳螂在房间中随机的从一块瓷砖漫步到另一块瓷砖（可能是在找一块奶酪，呵呵）。假设它可能从其他所在的瓷砖移动到其周围八块瓷砖中的任何一块（除非碰到墙壁），那么它至少接触每块瓷砖一次，将花费多少时间？  
       2. 强调：  
            这个算法有什么用？使用计算机解决此问题的技术称为模拟，这种技术广泛应用于工业中，用来预测运输流量，存货控制等问题。  
      3.解决思路：  
            用一个m \* n数组作为计数器来表示螳螂到达每一块瓷砖的次数，每个数组单元的初始化值均为0，螳螂在地板的位置用坐标表示（x， y）（可以直接用整型值，也可以用结构体，二者随意），则螳螂的八种可能移动用（x + xmove\[choose\], y + ymove\[choose\]）的瓷砖表示,其中0 <= choose <= 7,    并且：  
                    xmove\[0\] =   -1          ymove\[0\] =  1  
                    xmove\[1\] =   0          ymove\[1\] =   1  
                    xmove\[2\] =    1         ymove\[2\] =   1  
                    xmove\[3\] =    1         ymove\[3\] =   0  
                    xmove\[4\] =     1        ymove\[4\] =  -1  
                    xmove\[5\] =      0       ymove\[5\] =  -1  
                    xmove\[6\] =     -1        ymove\[6\] =  -1  
                    xmove\[7\] =     -1        ymove\[7\] =   0    
           螳螂向其相邻的八个方格的随机漫步通过产生一个随机数choose来模拟，而且，螳螂不能爬出房间，螳螂每进入一次方格，该方格计数器加1，当所有的方格全部为非零时，说明螳螂已经遍历完整个矩阵，是不是和马尔科夫过程非常像的。。。。  
              
  
4.代码如下：

\#include<stdio.h>

\#include<conio.h>

\#include<stdlib.h>

\#include<string.h>

\#include<time.h>

//总共移动的最多次数

\#define MAX 5000

//房间的长和宽

\#define X 10

\#define Y 10

\#define NOTEND \-1

int matrix\[X\]\[Y\];