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

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

0.分治中的一些知识点

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

如果 $log_b^a<c$ ,时间复杂度为 $O(n^c)$
如果 $log_b^a>c$ 时间复杂度为 $O(n^{log_b^a})$
如果相等的话时间复杂度为 $O(n^c\times log\ n)$

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

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;
			else
				return 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;
		else
			ans = 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列的数可以得到的最大的数字,

转态转移方程为:

$d p [i] [j] = ma x (d p [i - 1] [j], d p [i - 1] [j + 1]) + a rr [i] [j] .$

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

转态转移方程变化为:

$d p [i] = ma x (d p [i], d p [i + 1]) + a rr [i] [j]$ .

那么结果就是 $d p [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, 2.., n - 1$ ),确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
输入
每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。因为相乘需满足列数和下一个矩阵的列数相等所以会输入一个数组
输出
矩阵连乘最优计算次数。
样例输入
7
30 35 15 5 10 20 25
样例输出
15125

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

思路分析:

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

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

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

考察计算 $A [i : j]$ 的最优计算次序:
设这个计算次序在矩阵 $A_k和A_{k+1}$ 之间将矩阵链断开, $i \leq 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}*p_k*p_j$ 。

设计算 $A [i : j], 1 \leq i \leq j \leq n$ ,所需要的最少数乘次数 $d p [i] [j]$ ,则原问题的最优值为 $KaTeX parse error: Unexpected character: ' ' at position 9: dp[1][n] ̲$ ,当 $i = j$ 时,一个矩阵无法自己乘所以 $d p [i] [i] = 0, i = 1, 2..$  当 $i < j$ 时这里 $A_i$ , 的维数为 $p_{i-1}pi$  可以得到动态转移方程:
$dp[i][j]=\min_{i \le k < j} \{dp[i][k]+dp[k+1][j]+p_{i-1}*p_{k}*p_j\}其中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;
}

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