高级数据结构与算法期末考试速成记录

0.分治中的一些知识点

Master公式（又称主定理，Master Theorem）是一种用于快速求解分治递归算法时间复杂度 的数学工具，适用于递归式形如以下形式的算法：
$$\begin{gathered} T(n)=aT(\frac{n}{b})+O(n^c) \\ 其中a:子问题被递归调用的次数 \\ b:将原问题分为了几个子问题 \\ O(n^c):分治之后合并所需要的时间复杂度 \end{gathered}$$
之后根据具体情况有着一下的结论:

1. 如果$lo{g}_b^a<c$,时间复杂度为$O(n^c)$
2. 如果$lo{g}_b^a>c$时间复杂度为$O(n^{lo{g}_b^a})$
3. 如果相等的话时间复杂度为$O(n^c\times logn)$

快速排序中经常会用到的一个划分方法(就是根据给定的基准值,划分为小于,大于的两部分,返回基准的坐标值)的代码:

int part(int arr[],int l,int r)//其中r指向的是最后一个元素,不是n而是n-1
{int i=l,j=r+1;int shu=arr[l];//也可以使用随机划分,就是让随机选择的那个数和第一个数交换一下while(1){while(arr[++i]<shu && i<r) ;while(arr[--j]>shu);if(i>=j)break;swap(arr[i],arr[j]);}arr[l]=arr[j];arr[j]=shu;return j;
}

记住吧,因为错一点就会陷入死递归,或者划分错误!!!

1.分治算法之最近点对问题

问题描述:

给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。

输入格式
:

第一行一个整数 n,表示点的个数。
接下来行,每行两个整数x,y,表示一个点的行坐标和列坐标。

输出格式:

仅一行,一个实数,表示最短距离,四舍五入保留4位小数。

测试链接

思路解析(作者自己的理解):

首先是利用分治,将点集不断的根据这个集合的横坐标的中位数划分==(分治),直到一个集合的点的数量为2或者3的时候,就是问题的basecase就可以直接得到这个分得的点集中最小的距离,之后也可以得到另一个小的点集中的最小的距离相比较,就可以得到两边各自的最短距离,之后取出最短的,把落在[mid-d,mid+d]的点开始遍历,根据这个鸽舍定理==不知道的可以去搜一下(简单来说在一定的条件下,一个点和跨越[mid-d,mid+d]的点只可能是6个).遍历[mid-d,mid+d]中的点,算距离他比较近的6个点即可(合并)(按照y排一个序),之后就可以得到答案.
代码示例:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
//定义点对
struct Point
{int x, y;
};
//获取两个点之间的距离
double getDis(Point& a, Point& b)
{return sqrt((a.x - b.x)*(a.x-b.x) + (a.y - b.y)*(a.y-b.y));
}
bool mcmp1(Point& a, Point& b)
{return a.x < b.x;
}
bool mcmp2(Point& a, Point& b)
{return a.y < b.y;
}
double f(Point arr[], int l, int r)
{if (r - l == 1)//两个点return getDis(arr[l], arr[r]);else if (r - l == 2)//三个点{double d1 = getDis(arr[l], arr[l + 1]);double d2 = getDis(arr[l + 1], arr[r]);double d3 = getDis(arr[l], arr[r]);if (d1 < d2){if (d1 < d3)return d1;else{return d3;}}else{if (d2 < d3)return d2;elsereturn d3;}}else{double ans = 0;int mid = (l + r) / 2;double d1=f(arr, l, mid);//左边最短距离double d2 = f(arr, mid + 1, r);//右边最短距离if (d1 < d2)ans = d1;elseans = d2;//下面求解跨越中间的答案//存放位于[mid-d,mid+d]的点,进行查找跨越中间的点的答案Point* brr = new Point[r - l + 4];int b = 0;for (int i = l; i <= r; i++)if (abs(arr[i].x - arr[mid].x) < ans)brr[b++] = arr[i];//按照y坐标排一个序sort(brr, brr + b, mcmp2);for (int i = 0; i < b; i++){//只需要找距离这个点最近的7个点即可.for (int j = i + 1; j <= i + 7 && j < b; j++){//如果y坐标就已经比找到的最小的d大了,就不需要往后找了,因为y越来越大if (brr[j].y - brr[i].y > ans)break;double tmp = getDis(brr[j], brr[i]);if (tmp < ans)ans = tmp;}}delete[]brr;return ans;}
}
int main()
{int n;cin >> n;Point arr[10005];for (int i = 0; i < n; i++){cin >> arr[i].x >> arr[i].y;}sort(arr, arr + n, mcmp1);//按照x从小到大排序,便于分治double res = f(arr, 0, n - 1);printf("%.4lf", res);
}

2.1动态规划之数字三角形

问题描述:

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

输入格式
第一个行一个正整数r,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。

题目链接

从后面往前面进行推答案即可,因为只考虑只有两行的时候可以非常容易的得到结果.定义转态:

dp[i][j]从第i行j列的数可以得到的最大的数字,

转态转移方程为:

$dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+arr[i][j].$

进一步可以使用空间压缩,使用一个一维数组不断更新答案,根据状态转移方程可知,这个位置的答案,只是依赖于上一个的相同列和列+1的最大值.故

转态转移方程变化为:

$dp[i]=max(dp[i],dp[i+1])+arr[i][j]$.

那么结果就是$dp[0]$

代码示例:

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;int arr[n+1][n+1]={0};for(int i=0;i<n;i++){for(int j=0;j<i+1;j++)cin>>arr[i][j];}int dp[n+2];//存放上一行的答案数组,不断的滚动更新for(int i=0;i<n;i++){dp[i]=arr[n-1][i];}for(int i=n-2;i>=0;i--){for(int j=0;j<=i;j++){dp[j]=max(dp[j],dp[j+1])+arr[i][j];}} cout<<dp[0]<<endl;}

2.2动态规划之矩阵连乘问题

题目描述
矩阵连乘问题:
给定n个矩阵{A,A2…,An} 其中$A_i$与$A_{i+1}$是可乘的($i=1,\mathrm{2..},n-1$),确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
输入
每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。因为相乘需满足列数和下一个矩阵的列数相等所以会输入一个数组
输出
矩阵连乘最优计算次数。
样例输入
7
30 35 15 5 10 20 25
样例输出
15125

没找到测试链接,找到的小伙伴可以在评论下面发一下,感谢💐💐💐💐

思路分析:

首先明确矩阵$A(大小为i\ast j)$和矩阵$B(j\ast k)$需要相乘的次数为$i\times j\times k$次

为方便起见,将连乘积$A_{i-1}Ai..A_j$;简记为$A[i:j]$,其中$A_i$的维度记为$p_{i-1}\times p_i$。
若有一个计算$A[1:k]$的次序所需的计算量更少,则会取代之。类似,计算$A[k+1:n]$的次序也一定是最优的。
因此,矩阵连乘计算次序问题的最优解,包含了其子问题的最优解。

那么计算目的是求解$A[1:n]$的最优解,而一个最优策略的子策略也应是最优的
所以问题可分解为求$A[i:j]$的最优计算次序。

考察计算$A[i:j]$的最优计算次序:
设这个计算次序在矩阵$A_k和A_{k+1}$之间将矩阵链断开,$i\le k<j$,则其相应加括号的方式为:KaTeX parse error: Unexpected character: '
' at position 35: …A_{k+1}...A_j;)
̲那么$A[i:j]$的计算量为$A[i:k]$的计算量加上$A[k+1:j]$的计算量,再加上$A[i:k]$和$A[k+1:j]$
相乘的计算量$p_{i-1}\ast p_k\ast p_j$。

设计算$A[i:j],1\le i\le j\le n$,所需要的最少数乘次数$dp[i][j]$,则原问题的最优值为KaTeX parse error: Unexpected character: '
' at position 9: dp[1][n]
̲,当$i=j$时,一个矩阵无法自己乘所以$dp[i][i]=0,i=1,\mathrm{2..}$
当$i<j$时这里$A_i$, 的维数为 $p_{i-1}pi$
可以得到动态转移方程:
d p [ i ] [ j ] = min ⁡ i ≤ k < j { d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + p i − 1 ∗ p k ∗ p j } 其中 i < j dp[i][j]=\min_{i \le k < j} \{dp[i][k]+dp[k+1][j]+p_{i-1}*p_{k}*p_j\}其中i< j dp[i][j]=i≤k<jmin​{dp[i][k]+dp[k+1][j]+pi−1​∗pk​∗pj​}其中i<j
代码示例:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int p[maxn], dp[maxn][maxn];
int main()
{int n;while (~scanf("%d", &n)){for (int i = 1; i <= n; ++i)scanf("%d", &p[i]);memset(dp, 0, sizeof(dp));for (int r = 2; r < n; ++r)//r个矩阵相乘{for (int i = 1; i < n - r + 1; ++i){int j = i + r - 1;//r个dp[i][j] = dp[i + 1][j] + p[i] * p[i + 1] * p[j + 1];for (int k = i + 1; k < j; ++k)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]);}}printf("%d\n", dp[1][n - 1]);}return 0;
}