蟑螂随机走动问题（数据结构图问题）

一、问题概要

1.1 题目：

《随机走动》

1.2 初始条件：

一只贪杯的蟑螂醺醺然在室内地面游荡。地面铺满方砖，共计m*n块，构成大面积矩阵。蟑螂在方砖间随机爬行，可能想撞大运，找片阿司匹林解酒。假定蟑螂从房间中央一块方砖出发，除非撞墙，可以爬向相邻8块方砖的任意一块，且机会均等。问蟑螂多久才可以在所有方砖上留下行迹？

1.3 要求完成的主要任务:

用仿真的方法模拟蟑螂的爬行方向。统计每次蟑螂爬满所有方砖的爬行次数，将程序运行至少1000次，从结果中推导关于在给定m和n的情况下蟑螂爬满方砖的期望值或区间。

1.4 输入：

房间参数2<m≤20和2<n≤40，起点坐标（x, y）。

1.5输出：

蟑螂每达成目标一次，就输出count数组（称为蟑螂的爬行密度）一次，并对count数组求和。将每次的运行结果保存下来，在程序运行至少1000次后，对结果进行统计归纳，指出蟑螂最可能需要多少次才能爬满所有方砖。

二、概要设计

2.1抽象数据类型定义

（1）用于二维密度图的构建数据类型：

typedef struct Walk_data
{int count[MAX_HEIGHT][MAX_LENGTH];
}Walk_data_list;

（2）用于多种数据作为函数返回值的数据类型：

typedef struct Send_data
{int first[MAX_HEIGHT][MAX_LENGTH];int end[MAX_HEIGHT][MAX_LENGTH];int times_count;int mark;int m;int n;
}Send_data_list;

2.2逻辑结构

本程序当中共使用了两种抽象数据类型，构建了3个附加函数，其中抽象数据类型。Walk_data用于构建记录爬行密度的二维数组图，在主函数以及附加函数中均有调用，用于该类数据的统一；Send_data用于多种数据类型作为函数返回值同时返回的情况，主要运用于Crawl_all()函数以及Crawl_rest()函数；Crawl_all()函数是按需遍历图函数，该函数会将用户初次输入的数据进行遍历输出，同时还会记录完成第一次遍历的断点数据以及完成需求次数后的数据；Crawl_rest()函数是在用户输入次数未能完全遍历时调用的函数，该函数会继续接着用户输入要求次数的最后一次图密度情况进行爬行遍历，直到完成第一次图的遍历；Draw_zhentai()函数是用来将第一次完全遍历后的密度图对应的二维正态直方图切面进行可视化输出处理，得到对应的正态分布直方图。

三、详细设计

3.1 数据类型

①抽象数据类型

typedef struct Walk_data
{int count[MAX_HEIGHT][MAX_LENGTH];}Walk_data_list;

②抽象数据类型

typedef struct Send_data
{int first[MAX_HEIGHT][MAX_LENGTH];int end[MAX_HEIGHT][MAX_LENGTH];int times_count;int mark;int m;int n;
}Send_data_list;

③整型类型（用于定义爬行的方向）

int imove[8] = { -1,0,1,1,1,0,-1,-1 };
int jmove[8] = { 1,1,1,0,-1,-1,-1,0 };

④整型类型（用于定义初始的位置）

int m = (int)(max_height / 2);
int n = (int)(max_length / 2);

⑤整型类型（用于定义输入的内容）

int max_height ;
int max_length ;
int loop_times ;

⑥整型类型（用于断点标识的设置）

int u = 0;
int mark = 1;

⑥其它整数类型的定义

int times_loop;
int first_times;
int continues_times = loop_times;
int save_map_data[20];
int tmp_map_data[20];
int tmp_num;
int times = back_data.times_count;
int mark = back_data.mark;
int m = back_data.m;
int n = back_data.n;
int get_order;

3.2 核心操作实现

①Crawl_all函数核心（伪代码）

Send_data_list Crawl_all(Walk_data_list pic, int max_height, int max_length, int loop_times)
{定义爬行方向定义初始化位置定义数据存储返回结构Send_data_list Send_back;随机数定义断点标志定义获取循环次数for (times_loop = 0; times_loop < loop_times; times_loop++){检测标记归操作随机生成方向撞墙操作if (!(0 <= m && m < max_height && 0 <= n && n < max_length)){撞墙还原一步}pic.count[m][n] = pic.count[m][n] + 1;//检测是否遍历完成if (mark == 1) {for (int k = 0; k < max_height; k++){检测操作}if (mark == 1) {存储数据矩阵firstSend_back.first[k][j] = pic.count[k][j];}归零标记}}}for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){存储数据矩阵end}}函数返回设定1.循环次数 2.是否遍历完成标记 3.两个断点的二维数组Send_back.times_count = first_times;Send_back.mark = mark;Send_back.m = m;Send_back.n = n;return Send_back;
}

②Crawl_rest函数核心（伪代码）

Send_data_list Crawl_rest(Walk_data_list pic, int max_height, int max_length, int m, int n, int loop_times)
{定义前行方向Send_data_list Send_back;定义随机数定义断点标注获取已经循环的次数do{检测标记归0mark = 1;随机生成方向撞墙操作if (!(0 <= m && m < max_height && 0 <= n && n < max_length)){撞墙还原一步}pic.count[m][n] = pic.count[m][n] + 1;continues_times++;检测是否遍历完成if (mark == 1) {for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){如果数组存在0数据则让mark递增操作}}if (mark == 1) {for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){存储数据矩阵first}}break;}}} while (1);返回遍历完成数据（二维密度图及循环次数）
}

③Draw_zhengtai()函数核心（伪代码）

int Draw_zhengtai(Walk_data_list pic, int max_height, int max_length)
{定义切面位置定义正态二维图定义切面图最高数据项for (int i = 0; i < max_height; i++){save_map_data[i] = pic.count[i][n];tmp_map_data[i] = pic.count[i][n];} for (int i = 0; i < max_height-1; i++){if (tmp_map_data[i] >= tmp_map_data[i + 1]){一趟冒泡排序求最大值}}存储最大值for (int i = 0; i < max_height; i++){for (int j = 0; j < highest; j++){全图方块遍历}}for (int i = 0; i < max_height; i++){for (int j = 0; j < highest-save_map_data[i]; j++){依据密度结构进行空白补充}}切面正态直方图输出return 切面图最大数据项;
}

四、调试分析

4.1 开发中问题及解决

①问题一：在初次构建按需遍历函数时，发现有时，即使执行很多次，二维密度图中的相对密度也会特别低，而且有时会让程序直接退出导致程序崩溃。

这是因为由中心出发的蟑螂进行爬行，在爬行数次后很有可能会到达二维图的边缘，这个时候就有可能会爬到图的外面，从而使得爬行密度二维图发送数组越界，从而导不能继续遍历，甚至是程序崩溃。

而这一问题的解决方法就是，设置撞墙操作，在蟑螂“撞墙”的时候进行该补的还原，重复操作，直到下一步不撞墙位置。

②问题二：在进行功能完善的时候，希望设置断点，分别记录不同遍历状态的数据，这个偶就必须对爬行密度图进行检查，看它是否已经完成一次遍历。

解决这个问题的方法就是，通过设置mark标记，对二维图进行遍历查“0”，如果存在“0”则执行mark++，再进行检查如果mark==0则断点找到，如果mark！=0 则将mark归零继续进行操作，知道找到断点为止。

③问题三：在附加的功能函数中，需要对多种数据进行操作，而为了方便主函数进行操作结果的调用，就最好能实现多种数据类型的返回。

为了解决这个问题，我特意设置了对应的返回值结构体，定义了多种结构类型，从而满足了返回值的要求。同时如果仅需要返回一个数组，则可以通过指针传递的方式进行。

④问题四：为了方面问题的模型化，以及对相关重要数据的抽取，在定义蟑螂初始位置的时候选择的是爬行密度图的“相对中心点”，由于涉及到对二维正态直方图的分析，所以数据应该中心化，但怎样才能找到完全合适的连续抽取算法，且适用于不同规格的行数和列数（因为奇数行，偶数行，奇数列，偶数列组合后对应的中心相对位置不完全一样）

我发现，对于任意一种行列结构，从中心开始，只要向下先取，就可以完成连续行进的数据遍历。

⑤问题五：在做数据分析的过程中，我发现，整个二维的爬行密度图中对应的数据，确实可以整合成一个大致的多维正态直方图，但这样的一个正态分布图应该是有Z轴建模的，所以在平面的数据可视化中很难表现。针对整体数据相对正确的表示如下图所示：

但在命令行中的输出中受到限制，通过观察可以看到，这样一个三维模型，其中心切面正好是一个二维的正态分布图，而且具有对称性，可以在一定程度上反映出数据的大致分布情况。因此，在对数据的处理中，我选择了爬行密度图中心对应的列为基准数据列，进行数据可视化处理。

这里同样还是采用的二维数组的方式，只不过数组的每一个元素变成了空白或者是方块，这样输出以后就可以形成一个大概的直方图。如下图所示：

在这里，由于我还想做进一步的数据分析，想找到这些数据中的最大值，这个时候就用到了一趟冒泡排序求取最大值的方法。

4.2 主要算法时空分析

在整个程序中，最复杂的结构只有两层循环，以冒泡排序为例分析，可得算法的时间复杂度为O（n2），空间复杂度为O（1）。

五、用户使用说明

5.1 按行次需求完成地图遍历的情况

蟑螂第一次爬行完成所有砖块的数据：一个二维矩阵back_data.first[k][j]
蟑螂爬行输入要求次数后的数据:一个二维矩阵back_data.end[k][j]
蟑螂完成所有砖块的爬行一共进行了times次
输入4则继续获取完成要求次数后的大致正态直方图（以下是依据爬行密度得出的二维正态分布图的切面图map_pic[i][j]正态切面的最大值为zhengtai_map）
输入5则重新开始执行次程序
输入6则退出程序

5.2 按行次需求未完成遍历的情况

蟑螂爬行输入要求次数后的数据:一个二维矩阵back_data.end[k][j]
共进行了times次爬行，但没有完成全部砖块的遍历
输入4则继续爬行完成一次遍历
输入5则继续获取完成要求次数后的大致正态直方图（以下是依据爬行密度得出的二维正态分布图的切面图map_pic[i][j]正态切面的最大值为zhengtai_map）
输入6则重新开始执行次程序
输入7则退出程序

六、测试结果

**6.1 测试一（5*5）**

①未完成遍历

②完成遍历

6.2 测试二（10*10）

①未完成遍历

②完成遍历

七、源代码（C语言）

#include<stdio.h>
#include<stdlib.h>
#include<time.h>//对矩阵各维长度进行限制
#define MAX_LENGTH 20	
#define MAX_HEIGHT 20typedef struct Walk_data
{int count[MAX_HEIGHT][MAX_LENGTH];}Walk_data_list;typedef struct Send_data
{int first[MAX_HEIGHT][MAX_LENGTH];int end[MAX_HEIGHT][MAX_LENGTH];int times_count;int mark;int m;int n;
}Send_data_list;//遍历爬行函数
Send_data_list Crawl_all(Walk_data_list pic, int max_height, int max_length, int loop_times)
{//定义爬行方向int imove[8] = { -1,0,1,1,1,0,-1,-1 };int jmove[8] = { 1,1,1,0,-1,-1,-1,0 };int m = (int)(max_height / 2);int n = (int)(max_length / 2);//定义数据存储结构Send_data_list Send_back;//初始化位置pic.count[m][n] = 1;srand(time(NULL));int u = 0;int mark = 1;int times_loop;int first_times;for (times_loop = 0; times_loop < loop_times; times_loop++){//检测标记归0if (mark != 0){mark = 1;}//随机生成方向u = rand() % 8;m = m + imove[u];n = n + jmove[u];//撞墙操作if (!(0 <= m && m < max_height && 0 <= n && n < max_length)){times_loop = times_loop - 1;m = m - imove[u];n = n - jmove[u];continue;}pic.count[m][n] = pic.count[m][n] + 1;//检测是否遍历完成if (mark == 1) {for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){if (pic.count[k][j] == 0){mark++;}}}if (mark == 1) {first_times = times_loop + 1;for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){//存储数据矩阵firstSend_back.first[k][j] = pic.count[k][j];}}mark = 0;}}}//存储数据矩阵endfor (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){Send_back.end[k][j] = pic.count[k][j];}}//函数返回1.循环次数 2.是否遍历完成标记 3.两个断点的二维数组Send_back.times_count = first_times;Send_back.mark = mark;Send_back.m = m;Send_back.n = n;return Send_back;
}Send_data_list Crawl_rest(Walk_data_list pic, int max_height, int max_length, int m, int n, int loop_times)
{int imove[8] = { -1,0,1,1,1,0,-1,-1 };int jmove[8] = { 1,1,1,0,-1,-1,-1,0 };Send_data_list Send_back;srand(time(NULL));int u = 0;int mark = 1;int continues_times = loop_times;do{//检测标记归0mark = 1;//随机生成方向u = rand() % 8;m = m + imove[u];n = n + jmove[u];//撞墙操作if (!(0 <= m && m < max_height && 0 <= n && n < max_length)){m = m - imove[u];n = n - jmove[u];continue;}pic.count[m][n] = pic.count[m][n] + 1;continues_times++;//检测是否遍历完成if (mark == 1) {for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){if (pic.count[k][j] == 0){mark++;}}}if (mark == 1) {for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){//存储数据矩阵firstSend_back.end[k][j] = pic.count[k][j];}}break;}}} while (1);Send_back.times_count = continues_times;return Send_back;
}int Draw_zhengtai(Walk_data_list pic, int max_height, int max_length)
{int m = (int)(max_height / 2);int n = (int)(max_length / 2);int save_map_data[20];int tmp_map_data[20];int tmp_num;for (int i = 0; i < max_height; i++){save_map_data[i] = pic.count[i][n];tmp_map_data[i] = pic.count[i][n];}int highest;//一趟冒泡排序求最大值for (int i = 0; i < max_height-1; i++){if (tmp_map_data[i] >= tmp_map_data[i + 1]){tmp_num = tmp_map_data[i+1];tmp_map_data[i + 1] = tmp_map_data[i];tmp_map_data[i] = tmp_num;}}highest = tmp_map_data[max_height - 1];int map_pic[200][20];for (int i = 0; i < max_height; i++){for (int j = 0; j < highest; j++){map_pic[j][i] = "▅";}}for (int i = 0; i < max_height; i++){for (int j = 0; j < highest-save_map_data[i]; j++){map_pic[j][i] = "  ";}}printf("\n");printf("——以下是依据爬行密度得出的二维正太分布图的切面图——");printf("\n");printf("\n");for (int i = 0; i < highest; i++){for (int j = 0; j < max_height; j++){printf("%6s", map_pic[i][j]);}printf("\n");}return highest;
}int main(int argc, char* argv[])
{int max_height ;int max_length ;int loop_times ;do{//输入数据printf("1.请输入砖块矩阵的行数（请输入小于等于20的整数）：");scanf("%d", &max_height);printf("2.请输入砖块矩阵的列数（请输入小于等于20的整数）：");scanf("%d", &max_length);printf("3.请输入蟑螂的前行次数：");scanf("%d", &loop_times);printf("\n");printf("\n");Walk_data_list pic;for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){pic.count[k][j] = 0;}}//执行函数Send_data_list back_data;Send_data_list continues_data;int zhengtai_map;back_data = Crawl_all(pic, max_height, max_length, loop_times);int times = back_data.times_count;int mark = back_data.mark;int m = back_data.m;int n = back_data.n;int get_order;for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){pic.count[k][j] = back_data.end[k][j];}}if (times <= loop_times && mark == 0){printf("—————以下是蟑螂第一次爬完所有砖块的数据—————\n");printf("\n");for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){printf("%3d", back_data.first[k][j]);}printf("\n");}printf("\n");printf("\n");printf("—————以下是蟑螂爬行输入要求次数后的数据—————\n");printf("\n");for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){printf("%3d", back_data.end[k][j]);}printf("\n");}printf("\n");printf("蟑螂完成所有砖块的爬行一共进行了%d次\n", times);printf("\n");printf("\n");printf("4.输入4则继续获取完成要求次数后的大致正太分布图\n");printf("5.输入5则重新开始执行此程序\n");printf("6.输入6则退出程序\n");printf("\n");scanf("%d", &get_order);if (get_order == 4){zhengtai_map = Draw_zhengtai(pic, max_height, max_length);//下面是对图的输出printf("\n");printf("正态切面列的最大值为：%d\n", zhengtai_map);printf("\n");}if (get_order == 5){continue;}if (get_order == 6){return;}}else{printf("—————以下是蟑螂爬行输入要求次数后的数据—————\n");printf("\n");for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){printf("%3d", back_data.end[k][j]);}printf("\n");}printf("\n");printf("共进行了%d次爬行，但没有完成全部砖块的遍历\n", loop_times);printf("\n");printf("\n");printf("4.输入4则继续爬行直到完成一次遍历\n");printf("5.输入5则继续获取完成要求次数后的大致正态分布图\n");printf("6.输入6则重新开始执行此程序\n");printf("7.输入7则退出程序\n");printf("\n");scanf("%d", &get_order);if (get_order == 4){continues_data = Crawl_rest(pic, max_height, max_length, m, n, loop_times);int continues_times = 0;continues_times = continues_data.times_count;printf("\n");printf("—————以下是蟑螂第一次爬完所有砖块的数据—————\n");printf("\n");for (int k = 0; k < max_height; k++){for (int j = 0; j < max_length; j++){printf("%3d", continues_data.end[k][j]);}printf("\n");}printf("\n");printf("蟑螂继续进行%d次爬行完成所有砖块，则一共进行了%d次\n", continues_times - loop_times, continues_times);printf("\n");}if (get_order == 5){zhengtai_map = Draw_zhengtai(pic, max_height, max_length);//下面是对图的输出printf("\n");printf("正态切面列的最大值为：%d\n", zhengtai_map);printf("\n");}if (get_order == 6){continue;}if (get_order == 7){return;}}}while (1);system("pause");
}