首页 > 代码库 > 醉酒螳螂问题

醉酒螳螂问题

2024-07-03 11:23:36   219人阅读

醉酒螳螂问题
        记得去年上概率论的时候最后一章讲述的是马尔科夫过程，当时只会做题。完全不知道这是干甚么。其实就是矩阵的遍历性问题。今天介绍的醉酒螳螂也是关于遍历性的问题。
        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 MAX5000
//房间的长和宽
#define X10
#define Y10
#define NOTEND-1

int matrix[X][Y];

int judgeMatrixEnd(void);//判断矩阵是否每个方格进入一次
void showMatrix(void);//显示矩阵

void showMatrix(void)
{
    int i, j;

    for(i = 0; i < X; i ++)
    {
        for(j = 0; j < Y; j++)
            printf("%3d", matrix[i][j]);
        printf("\n");
    }
}

int judgeMatrixEnd(void)
{
    int i, j;

    for(i = 0; i < X; i++)
        for(j = 0; j < Y; j++)
        {
             if(matrix[i][j] <= 0)
                 return NOTEND;//没有结束
        }

    return END;//结束
}

int main(void)
{
    int x, y;
    int moveCount = 0;//移动次数
    clock_t start = 0, end = 0;//移动起始和终止时间
    double moveTime;//移动时间
    int choose;//选择的方向
    int lastx, lasty;//最后一次合理的坐标

    //下面的两个数组成对出现代表着随机点对应的八个方向
    int xmove[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
    int ymove[8] = {1, 1, 1, 0, -1, -1, -1, 0};
    /* 右  右 右 下 左  左  左  上
      上  边 下 边 下  边  上  边
     */ 
    memset(matrix, 0, sizeof(matrix));//把矩阵初始化为0
    x = rand() % X;//随机定位横坐标
    y = rand() % Y;//随机定位纵坐标
    matrix[x][y]++;//随机定位的次数加1
    showMatrix();
    //当某个位置出现的次数超过最大次数或者每个方格至少进入一次时，实验结束
    while(moveCount < MAX && judgeMatrixEnd() == NOTEND)
    {
        choose = rand() % 8;

        //蟑螂的移动位置不能超过四个边界
        if(x + xmove[choose] >= 0 && y + ymove[choose] >= 0
        && x + xmove[choose] < X && y + ymove[choose] < Y)
        {
             //改变蟑螂的位置
              x += xmove[choose];
              y += ymove[choose];
              matrix[x][y]++;//该位置次数加1
             //保存当前坐标
             lastx = x;
             lasty = y;
        }
        else
        {
             //如果不合理则返回到上一次位置
             x = lastx;
             y = lasty;
             continue;
        }

        system("CLS");
        showMatrix(); 
       moveCount++;
    }
 
    end = clock();

    moveTime = (double)(end - start) / CLK_TCK;
    printf("\n移动的次数为:%d", moveCount);
    printf("\n所花费的时间为：%lf", moveTime);
    getch();
    return 0;
}


联系
我们