算法第三章上机实践报告

一、上机题目解析

实践题目：

7-1 数字三角形

 1 #include<iostream>
 2 using namespace std;
 3
 4
 5 int main(){
 6     int n;//n为三角形的行数
 7     cin >> n;
 8     int a[n][n],b[n][n];
 9     for(int i=0;i<n;i++){
10         for(int j=0;j<=i;j++){
11             cin >> a[i][j];
12         }
13     }
14     //先将b数组全部置为0 
15     for(int i=0;i<n;i++){
16         for(int j=0;j<=i;j++){
17             b[i][j] = 0;
18         }
19     }
20     //再将a数组的最后一行复制到b数组中 
21     for(int l=0;l<=n-1;l++){
22         b[n-1][l] = a[n-1][l];
23     }
24     //给b数组填表，将max加到a数组的对应层 
25     for(int p=n-1;p>0;p--){
26         for(int q=0;q<p;q++){
27             if((a[p-1][q]+b[p][q]) > (a[p-1][q] + b[p][q+1]))
28                     b[p-1][q] = a[p-1][q] + b[p][q];
29             else b[p-1][q] = a[p-1][q] + b[p][q+1];
30         }
31     }
32
33     cout << b[0][0];
34     return 0;
35 }

数字三角形（填表法）

 1 #include<iostream>
 2 using namespace std;
 3
 4 int main(){
 5     int n;
 6     cin >> n;//三角形有n行 
 7     int a[n][n];
 8     for(int i=0;i<n;i++){
 9         for(int j=0;j<=i;j++){
10             cin >> a[i][j];
11             }
12     }
13
14     for(int p = n-1;p > 0;p--){
15         for(int q = 0;q < p;q++){
16             if((a[p][q] + a[p-1][q]) > (a[p][q+1]+a[p-1][q]))
17                     a[p-1][q] = a[p][q] + a[p-1][q] ;
18             else a[p-1][q] = a[p][q+1]+a[p-1][q];
19         }
20     }
21     cout << a[0][0];
22     return 0;
23 }

数字三角形（递归非填表法）

算法描述：

①对于给出的数字三角形，我们是根据自底向上顺序来计算的

②递推公式

b[i-1][j] = max(a[i][j]，a[i][j+1])+a[i-1][j]

时间复杂度：

T（n）= 3O(n²）+O（n）=

7-2 最大子段和

参考：

算法设计与分析_中国大学MOOC(慕课) https://www.icourse163.org/learn/PKU-1002525003?tid=1002695005#/learn/content?type=detail&id=1003858255

 1 /*给出一个长度为n的序列A1、A2、A3、...、An，
 2 求最大连续和。即找到1<=i<=j<=n,使得Ai+Ai+1+...+Aj最大*/
 3 #include<iostream>
 4 using namespace std;
 5
 6 /*穷举法（暴力）*/
 7 int maxsum(int* a,int l,int r){
 8     int pi =0,pj=0;
 9     int max = a[l];
10     for(int i=l;i <=r;i++){
11         for(int j=i;j<=r;j++){
12             int sum =0;
13             for(int k=i;k<=j;k++){
14                 sum+=a[k];
15             }
16             if(sum>max){
17                 max = sum;
18                 pi = i;
19                 pj = j;
20             }
21         }
22     }
23     return max;
24 }
25
26 int main(){
27     int n;
28     cin >>n;
29     int a[n];
30     for(int i=0;i<n;i++){
31         cin >> a[i];
32     }
33     cout  << maxsum(a,0,n-1);
34     return 0;
35 }

最大子段和（暴力穷举法）

暴力穷举法：时间复杂度O（n³）

 1 #include<iostream>
 2 using namespace std;
 3
 4 int getMaxNum(int a,int b,int c){
 5     if (a > b&&a > c){
 6         return a;
 7     }
 8     if (b > a&&b > c){
 9         return b;
10     }
11     return c;
12 }
13 int maxSumRec(int data[], int left, int right){
14     if (right - left == 1){
15         //如果当前序列只有一个元素
16         return data[left];
17     }
18     int center = (left + right) / 2;//计算当前序列的分裂点
19     int maxLeftSum = maxSumRec(data,left,center);
20     int maxRightSum = maxSumRec(data,center,right);
21     //计算左边界最大子序列和
22     int leftBonderSum = 0;
23     int maxLeftBonderSum = data[center-1];
24     for (int i = center - 1; i >= left; i--){
25         leftBonderSum += data[i];
26         if (maxLeftBonderSum < leftBonderSum){
27             maxLeftBonderSum = leftBonderSum;
28         }
29     }
30     //计算右边界最大子序列和
31     int rightBonderSum = 0;
32     int maxRightBonderSum = data[center];
33     for (int i = center; i < right; i++){
34         rightBonderSum += data[i];
35         if (maxRightBonderSum < rightBonderSum){
36             maxRightBonderSum = rightBonderSum;
37         }
38     }
39     //返回当前序列最大子序列和
40     return getMaxNum(maxLeftBonderSum + maxRightBonderSum, maxLeftSum, maxRightSum);
41 }
42
43 int main(){
44     int n;
45     cin >> n;
46     int a[100];
47     for(int i=0;i<n;i++){
48         cin >> a[i];
49     }
50     cout << maxSumRec(a,0,n-1);
51     return 0;
52 }

最大子段和（分治法）

时间复杂度

T(n)=2T(n/2)+O(n)=2T(n/4)+O(n)+O(n)=2T(n/8)+O(n)+O(n)+O(n)=O（nlogn）

 1 #include<iostream>
 2 using namespace std;
 3
 4 int MAX(int a[],int b[],int n,int max){
 5     //数组b存放每个子段和 
 6     int sum=0;
 7     //边界条件 令b[0]=a[0]  
 8     for(int i=0;i<n;i++){
 9         if(i==0){
10             b[i] = a[i];
11             max =b[i];
12         }
13     //如果前一个数b[i-1]<0 则数组b中的下一个数就不需要加上前一个数 反之则需要加上      
14         else{
15             if(b[i-1]<0)
16                 b[i] = a[i];
17             else
18                 b[i] = b[i-1] + a[i];
19             if(b[i]>max)
20                 max = b[i];
21         }
22         //计算负数的个数 
23         if(a[i] < 0) sum++;
24     }
25     if(sum == n) return 0;//如果全为负数 则返回0 
26     else return max;
27 }
28
29 int main(){
30     int n;
31     cin >> n;
32     int a[1000];
33     for(int i=0;i<n;i++){
34         cin >> a[i];
35     }
36     int b[1000];
37     int max=0;
38     max = MAX(a,b,n,max);
39     cout << max;
40     return 0;
41 }

最大字段和（动态规划）

用动态规划的方法

由于只有一个For循环因此时间复杂度为O（n）

7-3 编辑距离问题

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4
 5 string A,B;
 6 int Distance[4001][4001];
 7
 8 int main(){
 9
10     cin >> A >> B;
11     //假设一个字符串为空字符串，则他们两个之间的编辑距离就是另一个字符串的长度 
12     for(int i=1;i<=A.size();i++){
13         Distance[i][0] = i;
14     }
15     for(int i=1;i<= B.size();i++){
16         Distance[0][i] = i;
17     }
18     for(int i=1;i<=A.size();i++){
19         for(int j=1;j<= B.size();j++){
20             //因为数组没有经过初始化 所以默认所有元素都是0，也就是说如果两个字符串的对应字符相等，则他们之间的编辑距离为默认值0，不用改变 
21         if(A[i-1] == B[j-1]) Distance[i][j] = Distance[i-1][j-1];
22         else{//如果字符串中对应的字符不相等则，比较 上面和左边的数的大小 取小 然后再跟斜对角线的比较 
23             Distance[i][j] = Distance[i-1][j] < Distance[i][j-1] ? Distance[i-1][j] : Distance[i][j-1];
24             Distance[i][j] = Distance[i][j] < Distance[i-1][j-1] ? Distance[i][j] : Distance[i-1][j-1];
25             Distance[i][j]++;
26             }
27         }
28     }
29     cout << Distance[A.size()][B.size()];
30     return 0;
31 }

编辑距离问题

时间复杂度：T（n）=O(n²)+2O（n）

二、心得体会

这次上机我和我的搭档没有上次那么顺利，上次我们还没下课就已经写完三道题，这次我们一直卡在第二道题那

1.在课上我们成功做出第一道题，但我们并没有用到填表的方法，

 1 #include<iostream>
 2 using namespace std;
 3
 4 int main(){
 5     int n;
 6     cin >> n;//三角形有n行 
 7     int a[n][n];
 8     for(int i=0;i<n;i++){
 9         for(int j=0;j<=i;j++){
10             cin >> a[i][j];
11             }
12     }
13
14     for(int p = n-1;p > 0;p--){
15         for(int q = 0;q < p;q++){
16             if((a[p][q] + a[p-1][q]) > (a[p][q+1]+a[p-1][q]))
17                     a[p-1][q] = a[p][q] + a[p-1][q] ;
18             else a[p-1][q] = a[p][q+1]+a[p-1][q];
19         }
20     }
21     cout << a[0][0];
22     return 0;
23 }

数字三角形（非填表法）

但是我们其实是用来填表的思想的

后来下课后我改进了一下改成了用填表的方法

 1 #include<iostream>
 2 using namespace std;
 3
 4
 5 int main(){
 6     int n;//n为三角形的行数
 7     cin >> n;
 8     int a[n][n],b[n][n];
 9     for(int i=0;i<n;i++){
10         for(int j=0;j<=i;j++){
11             cin >> a[i][j];
12         }
13     }
14     //先将b数组全部置为0 
15     for(int i=0;i<n;i++){
16         for(int j=0;j<=i;j++){
17             b[i][j] = 0;
18         }
19     }
20     //再将a数组的最后一行复制到b数组中 
21     for(int l=0;l<=n-1;l++){
22         b[n-1][l] = a[n-1][l];
23     }
24     //给b数组填表，将max加到a数组的对应层 
25     for(int p=n-1;p>0;p--){
26         for(int q=0;q<p;q++){
27             if((a[p-1][q]+b[p][q]) > (a[p-1][q] + b[p][q+1]))
28                     b[p-1][q] = a[p-1][q] + b[p][q];
29             else b[p-1][q] = a[p-1][q] + b[p][q+1];
30         }
31     }
32
33     cout << b[0][0];
34     return 0;
35 }

数字三角形（填表法）

2.对于第二道题，我们刚开始一直在思考如何使得算出的两个正数之间的序列和

后来我回来上网查了一下并在慕课看到类似的题，我发现了这个也是用填表法，其实老师在将第二章分治法的时候也用了分治法做了一遍，这次用填表法，是将每个子段和存到另外一个数组，这样可以，递归调用，如果该原数组的数为负数则不加进子段和这样一层层的求出

3.第三题的确让我很懵逼，虽然也是用填表法做，但我有些不理解，为什么要在上左斜对角这三个元素中去最小值呢？希望老师上课可以详细的讲一下

上机体会：

我发现算法越来越难，这次上机我和我的搭档一起解题的时候，总是希望用老师将的算法知识方法解，但是总有重重困难，而且动态规划也蛮复杂的，的确要认真的体会领悟，多看几遍题，多想，然后把不会的题一定要理解。