一、题目要求
1、返回一个二维整数数组中最大连通子数组的和。
二、设计思路
刚开始看到这个题目时,想了应该对其降维,然后再一维数组的基础上解决问题更方便,但是一直想不到办法,然后在老师的指导下,想到了离散和数据结构曾经学到的有关图的联通的解决办法,将二维数组看成一个图来遍历来寻找最大子数组的和。
本次实验,老师要求从文件中读入行和列还有数组元素,我们利用fstream实现从文件的读入,一次读入行列和数组元素。
本次实验我们没有能实现有符号的32位整数的大数的运算,实验完成度没有达到要求。
三、程序代码
1 //结对开发成员;张晓菲 张哲 2 //本次实验题目为:求二维数组中的最大连通子数组的和 3 #include4 #include 5 #include 6 using namespace std; 7 #define N 100 8 9 typedef struct 10 { 11 int array[N]; 12 int col[N][N]; 13 int countnum; 14 }Struct;//定义结构体变量 15 16 void input(Struct &num, int x, int y) 17 { //input用于实现从文件中读取行和列并输出到屏幕上 18 num.countnum = x*y; 19 int i = 1; 20 int a, b; 21 ifstream in = ifstream("input.txt"); 22 in >> a; 23 in >> b; 24 num.countnum = a*b; 25 while (in >> num.array[i]) 26 { //将in文件中的数字读取到数组中 27 ++i; 28 } 29 in.close();//读取完毕关闭文件in 30 for (int i = 1; i <= num.countnum; i++) 31 { 32 cout << num.array[i] << " "; 33 if (i%b == 0) 34 { 35 cout << endl; 36 } 37 }//输出文件导入的数组到屏幕 38 for (int i = 1; i <= num.countnum; i += y) 39 { 40 for (int j = i; j <= i + y - 2; j++) 41 { 42 num.col[j][j + 1] = 1; 43 num.col[j + 1][j] = 1; 44 } 45 } 46 for (int i = 1 + y; i = b) 62 { 63 b = max; 64 } 65 for (int w = 1; w <= num.countnum; w++) 66 { 67 for (int c = 1; c <= num.countnum; c++) 68 { 69 if ((visit[w] == 0) && (num.col[c][w] == 1) && (visit[c] == 1)) 70 { 71 a = w; 72 var = 1; 73 break; 74 } 75 } 76 if (var == 1) 77 break; 78 } 79 for (int w = 1; w <= num.countnum; w++) 80 { 81 for (int c = 1; c <= num.countnum; c++) 82 { 83 if ((visit[w] == 0) && (num.col[c][w] == 1) && (visit[c] == 1)) 84 { 85 if (num.array[a] > x;104 fs >> y;105 cout << x << " " << y << endl;106 Struct num;107 input(num, x, y);108 int v = 1, b[N] = { 0 }, h = 0;109 for (int i = 1; i <= num.countnum; i++)110 {111 if (num.array[i]<0)112 {113 b[i] = num.array[i];114 }115 else116 {117 int visit[N] = { 0 };118 int max = 0;119 traverse(num, i, visit, b[i], max, x);120 }121 }122 123 int max = b[1];124 for (int i = 2; i <= num.countnum; i++)125 {126 if (b[i]>max)127 max = b[i];128 }129 cout << "该数组中最大连通子数组的和为:" << max << endl;130 }
四、实验运行结果
(1)、input文件内
屏幕显示
五、时间记录日志
日期 | 开始时间 | 结束时间 | 中断时间(min) | 净时间(min) | 活动 | 备注 |
3月28号 星期一 | 14:00 | 15:50 | 10(课间) | 100 | 听课 | 软件工程 |
3月29号 星期二 | 20:00 | 22:00 | 0 | 120 | 编程 | 四则运算网页版 |
3月30号 星期三 | 15:00 | 17:00 | 10(休息) | 110 | 编程 | 四则运算网页版 |
20:00 | 22:10 | 10(休息) | 120 | 编程 | 四则运算网页版 | |
3月31号 星期四 | 14:00 | 15:50 | 10(课间) | 100 | 听课 | 软件工程 |
20:30 | 22:00 | 10(休息) | 80 | 编程 | 二维数组3 最大连通子数组和 | |
4月2号 星期六 | 14:00 | 17:00 | 20 | 160 | 编程 | 四则运算网页版 |
4月3号 星期日 | 14:30 | 18:00 | 30 | 180 | 编程 | 四则运算网页版 |
4月4号 星期一 | 19:30 | 22:30 | 0 | 180 | 编程 | 四则运算网页版 |
4月5号 星期二 | 8:00 | 10:00 | 0 | 120 | 编程 | 二维数组3 最大连通子数组的和 |
19:30 | 23:00 | 0 | 210 | 编程 | 四则运算网页版 | |
4月6号 星期三 | 14:20 | 17:10 | 0 | 150 | 编程 | 四则运算网页版 二维数组3 写博客 |
六、实验总结
通过本次实验,我学到了很多东西,在实验的开始,我们对数组的思考,将其转换为图的方法来解决问题,对之前学过的知识来说是一个很好的利用,实验过程中开始我们对结构的使用比较陌生,之前编程用到的少,再查阅相应资料后得以实现,总之通过这次结对开发的实验设计,收获很多,学到了很多。