算法第三章上机实践报告
一、数字三角形
1.实践题目
2.问题描述
该问题要求在只能向左斜下方或者右斜下方走得条件下，从第一行开始找寻一个最佳路径，使得到达最后一行的路径和最大
3.算法描述
定义一个二维数组dis[i][j]存储数字三角形的数据，据题意，比较dis[i][j]右下方和左下方的两个数，将dis[i递][j]和那个较大的相加，就是所求从第i行到第j行路径最大值，其递归方程式为
dis[i][j] = max{dis[i+1][j], dis[i+1][j+1]} + dis[i][j] (i < n-2)
填表的方式为从第n-2行开始，从下往上填，从左往右填。代码如下：
1 #include <iostream> 2 using namespace std; 3 #define MAX 100 4 5 int maxDis(int dis[][MAX], int n) { 6 for (int i = n - 2; i >= 0; i--) { 7 for (int j = 0; j <= i; j++) { 8 if (dis[i + 1][j] > dis[i + 1][j + 1]) 9 dis[i][j] += dis[i + 1][j]; 10 else dis[i][j] += dis[i + 1][j + 1]; 11 } 12 } 13 return dis[0][0]; 14 } 15 16 int main() { 17 int dis[MAX][MAX]; 18 int n; 19 cin >> n; 20 for (int i = 0; i < n; i++) { 21 for (int j = 0; j <= i; j++) { 22 cin >> dis[i][j]; 23 } 24 } 25 cout << maxDis(dis, n); 26 return 0; 27 }
4.算法时间及空间复杂度分析
整个算法主要是用两个for循环来初始化数组，用两个for循环来填表，因此时间复杂度T(n) = O(n2)。
数组dis[][]不受输入的n值得影响，所以空间复杂度为O(1).
二、最大子段和
1.实践题目
2.问题描述
求一个整数序列的最大子段和（既是子段边便不要求连续，只要是原序列的子序列就可）
3.算法描述
定义一个一维数组sum[i], 表示从第1个数到第i+1个数组成的序列的子段和。sum的初始定义为每个数的值，再定义一个max，初始值为0，用来记录最大子段和的值，可以满足当序列全为负数时，子段和为0。其递归方程如下：
sum[i] = sum[i-1] + sum[i] (sum[i-1) > 0）
其余情况sum[i]的值不变，算法代码如下：
1 #include <iostream> 2 using namespace std; 3 #define MAX 10000 4 5 int maxSum(int *sum, int n) { 6 int max = 0; 7 for (int i = 1; i < n; i++) { 8 if (sum[i - 1] > 0) 9 sum[i] += sum[i - 1]; 10 if (max < sum[i]) 11 max = sum[i]; 12 } 13 return max; 14 } 15 16 int main() { 17 int sum[MAX], n; 18 cin >> n; 19 for (int i = 0; i < n; i++) 20 cin >> sum[i]; 21 cout << maxSum(sum, n); 22 }
4.算法时间及空间复杂度分析
初始化数组sum的时间复杂度为O(n)，填表的时间复杂度也为O(n)，所以整个算法的时间复杂度为O(n)。
整个算法只用到了一个一维数组，且数组大小不受所输入N的影响，因此空间复杂度为O(1)。
三、编辑距离问题
1.实践题目
2.问题描述
与求最长子序列有点类似，该问题求取得是将序列A更换为B序列，要进行多少次变换。
3.算法描述
除数组a、b之外，另定义一个二维数组c，来记录子问题的解。c[i][j]表示数组a的前i+1个字符转换成数组b的前j+1个字符需要的字符操作数，定义一个整型变量flag，若a[i]=b[j]，则flag=0，否则flag=0。递归方程为：
代码如下：
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 #define MAX 2000 6 int c[MAX][MAX]; 7 8 int length(char *a, char *b, int ma, int mb) { 9 int min; 10 for (int i = 1; i <= ma; i++) 11 c[i][0] = i; 12 for (int j = 1; j <= mb; j++) 13 c[0][j] = j; 14 for (int i = 1; i <= ma; i++) { 15 for (int j = 1; j <= mb; j++) { 16 int flag = 1; 17 //所填表的规格是c[ma+1][mb+1],当第一行和第一列都填好后，从第二行第二列下标为1开始填，但是字符数组的起始下标是从0开始的 18 if (a[i - 1] == b[j - 1]) 19 flag = 0; 20 if (c[i][j - 1] < c[i - 1][j]) 21 min = c[i][j - 1] + 1; 22 else 23 min = c[i - 1][j] + 1; 24 if (c[i - 1][j - 1] + flag < min) 25 min = c[i - 1][j - 1] + flag; 26 c[i][j] = min; 27 } 28 } 29 return c[ma][mb]; 30 } 31 32 int main() { 33 char a[MAX], b[MAX]; 34 cin >> a; 35 cin >> b; 36 int ma = strlen(a); 37 int mb = strlen(b); 38 cout << length(a, b, ma, mb) << endl; 39 return 0; 40 }
4.算法时间及空间复杂度分析
时间复杂度T(n) = O(n)+O(n) + O(n^2)，即时间复杂度为O(n^2)。
由于三个数组的大小都是固定值，因此空间复杂度为O(1)。
四、心得体会
在求解数字三角形和最大子段和这两题时我们小组没有遇到太大的困难，主要编辑距离问题，我们开始是想的先求出两个字符串的最大公共子序列，再用较长的字符串长度减去最大公共子序列的长度，但是提交上去的答案却有个测试点是错误的，主要是我们忽略了字符顺序问题，如果两个字符串分别是fx和xg，那么根据我们之前的想法，求出来的最小字符操作数为1，但是实际上是2，要进行删除操作和插入操作。另外，我们的算法开始还出现了段错误，经过查找，我们知道了段错误是访问的内存超过了系统所给的内存，后我们将C数组的改为全局变量就可以了。
程序满足题目所给的测试数据并不代表程序正确了，就像每个实验都要进行无数次实验，才能得出正确的结果，在测试时，应该多准备几组具有代表性的数据，来进行检测，而不能仅仅相信偶然。