【算法与设计】期末总结

文章目录

  • 第一章 概述
    • 算法与程序
    • 时间复杂性
    • 求上界
  • 第二章 递归与分治
    • 双递归函数——Ackerman函数
    • 分治策略
      • 大整数乘法
        • 两位×两位
        • 四位x四位
      • 三位x三位
        • 两位x六位
  • 第三章 动态规划
    • 矩阵连乘
    • 基本要素
      • 最优子结构
      • 子问题重叠
    • 备忘录
  • 第四章 贪心算法
    • 活动安排问题
    • 基本要素
      • 贪心选择性质
      • 最优子结构性质
      • 与动态规划的区别
    • 背包问题
      • 物体可分
      • 物体不可分
  • 第五章 回溯法
    • **问题的解空间**
    • 0-1背包
    • 迭代回溯
    • 0-1背包问题(树结构)
  • 期末考点

第一章 概述

算法与程序

算法:解决问题的一种方式或者一种过程。算法有若干个指令组成的有穷序列。
程序:算法用某种程序设计语言的具体实现

算法的4种性质:

  • 输入
  • 输出
  • 确定性
  • 有限性

程序可以不满足“有限性”

时间复杂性

算法复杂度的高低体现在运行该算法所需要的计算机资源的多少上。资源的多少依赖于要解决问题的规模(N)、算法的输入(I)和算法本身的函数(A)

关于时间复杂性,分为三种情况:最坏情况、最好情况和平均情况。
可操作性最好且最有实际价值的是最坏情况的时间复杂度

求上界

当N>=N0时有f(N)<=Cg(N),称为函数f(N)的一个上界是Cg(N),记作f(N)=O(g(N))
这个上界的阶越低,则评估越精确,结果越有价值

如何求上界?
1.把f(N)函数中的所有阶放大到最高阶,合并后并记为Cg(N)
2.此时f(N)<=Cg(N),把这两个函数去化简即可得条件,即n值。

例子:f(n)=3n2+10n
最高阶是n2,所有阶放大到最高阶得3n2+10n2=13n2,记为Cg(N)
此时,C=13,g(N)=n2
当3n2+10n <= 3n2+10n2时,即10n <= 10n2时,条件成立。
故n0>=1
综上,当n0=1时,C=13,f(n)=O(n2)

注意:放大方向不变,方式可以改变(即可以增大阶层且缩小系数),如3n2+10n <= 3n2+n2,此时结果的C和n0都不一样,但f(n)始终一样。

第二章 递归与分治

递归:代码效率好,但是空间效率和时间效率差

如何改进??
消除递归,有两种方式:阶乘(循环)和阶加(循环、通项公式)

双递归函数——Ackerman函数

定义:一个函数及它的一个变量由函数自身定义时

分治策略

基本思想:将问题分解为k个小规模的子问题,这些子问题相互独立且原问题相同。递归地解这些子问题,将个子问题的解合并得到原问题的解。

大整数乘法

普通乘法的时间复杂度是O(n2)
通过分支策略可达到O(n1.59)

两位×两位

步骤:
1.两位数分出高低位
2.套用公式求p,q,r

遇到负数,高低位都带符号
如-23:高位-2,低位-2。至此,-23=(-2)*10+(-3)

最简的分治(递归出口):一位x一位

四位x四位

一直递归,直到满足出口

三位x三位

往前补0,公式不变

两位x六位

补零或者把六位拆成3个两位

第三章 动态规划

动态规划分治
分解子问题分解子问题
子问题相互依赖子问题相互独立

基本思想:
分解成子问题求解时,有些子问题被重复计算许多次。用一个记录所有已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量的重复计算。

步骤:
1.找到最优解,刻画其结构性质
2.递归地定义最优值
3.以自底向上的方式计算最优值
4.根据计算最优值时得到的信息,构造最优解

矩阵连乘

题目背景:
若两矩阵相乘,需满足第一矩阵的行=第二矩阵的列
即Amxn X Bpxq的条件为n==p
此时,乘法次数为=m x n x q

连乘次序会影响乘法次数

按照上述步骤:
1.最优解及其结构性质:最小乘法次数 及 最小乘法次数的断开处
记A[i:j]是AiAi+1…Aj
问题:A[1:n],可以在k=1,2,⋯n−1处断开,若A[1:n]最优,则A[1:k]与A[k+1:n]也最优

2.建立递归关系
记A[i:j],其中1≤i≤j≤n,最少乘法次数记m[i][j]
(1)当i=j时→ A[i:i] →指A[i] 本身→乘法次数为0,即 m[i][j]=0
(2)当i<j时, 在k处断开, k可以取值i, i+1, ∙∙∙, j−1,在某k处乘法次数最少

在这里插入图片描述
定义数组p存储矩阵信息
p[0]为第1矩阵的行
p[1]为第1矩阵列(也为第2矩阵行)
p[2]为第2矩阵列(也为第3矩阵行)
p[3]为第3矩阵列(也为第4矩阵行)

p[n]为第n矩阵列

3.计算最优值
对于结果的存储,使用m表存储最小乘法次数(即最优值),用s表存储k值(即最优解)

代码实现:

//构造最优值
void MatrixChain(int *p, int n, int **m, int **s)//P一维数组记下标;n矩阵个数;m表;s记分段
{
	for(int i=1;i<=n;i++)
		m[i][i]=0;//对角线上都填0

	for(int r=2;r<=n;r++)//在m表中,从第2条填到第n条(对角线)
		for(int i=1;i<=n-r+1;i++)//i是行下标,从第1行开始填一个倒三角的表
		{
			int j=i+r-1;//列下标
			m[i][j]=0+m[i+1][j]+p[i-1]*p[i]*p[j];//实现递归计算,先初始化第1项,省略了m[i][i]
			s[i][j]=i;//s记分段点,此为s的初值

			for(int k=i+1;k<j;k++)//递归式从k=i+1到j-1,找最小
			{
				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//递归式计算 
                if(t<m[i][j])
				{
					m[i][j]=t;//记入最小值
					s[i][j]=k;//记入划分位置
				}
			}
		}
}

4.构造最优解
算法MatrixChain只是计算出了最优值,并未给出最优解。但是MatrixChain已记录了构造最优解所需要的全部信息。s[i][j]中的数表明,最佳方式应在矩阵的何处断开。

//构造最优解
void Traceback(int i,int j,int **s)//求A[i:j]的最优解构造,利用s[][],设已知s[i][j]=k
{
	if(i==j)
		return ;//A[i:i]不必构造,递归出口

	Traceback(i,s[i][j],s);//求A[i:k]的构造,记1
    Traceback(s[i][j]+1,j,s);//求A[k+1:j]的构造,记2
	cout<<"Multiply A["<<i<<":"<<s[i][j]
		<<"]and A["<<(s[i][j]+1)<<":"<<j<<"]"<<endl;//输出Ai,k And Ak+1,j,表明在k处断开,记3
}

基本要素

最优子结构

设计动态规划算法的第一步通常是要刻画最优解的结构。
当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。

子问题重叠

在用递归算法自顶向下解此问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。
动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。

备忘录

动态规划的变形——备忘录

动态规划:保存所有子问题的解
变形:动态规划是自底向上;备忘录是自顶向下

第四章 贪心算法

工作量:贪心算法 < 动态规划
但是贪心算法的结果可能不是最优结果,因为贪心算法并不是从整体最优上加以考虑,它所做出的选择只是某种意义上的局部最优选择

所以,贪心算法的关键是贪心策略的选择

活动安排问题

该问题要求高效地安排一系列争用某一个公共资源的活动。有n个活动,开始和结束的时间si≤fi,如何安排最多个活动?

贪心策略:按结束时间递增排序,从前向后能安排则安排

例题:当前有4个活动。

i1234
s[i]1305
f[i]4567

若选择最早结束优先,能使选入活动最多
若最早开始优先,仅能安排这一个活动
若最短占用优先,则能安排这一个活动

推广:
假设要在足够多的的会场里安排一批活动,即每个活动都要被安排,并希望使用尽可能少的会场。
(1)贪心策略思路1:先在第1会场安排最多活动,其次在第2会场安排最多,……,依此类推 。
(2)贪心策略思路2:视为区间重叠问题。时间点:起点和终点。
按时间点排序起点分配1个会场,终点回收,保证此会场可重复利用
在这里插入图片描述
在这里插入图片描述

基本要素

贪心选择性质

贪心选择性质是指所求问题的整体最优解是可以通过局部最优的选择,即贪心选择达到的。
动态规划算法中,每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后,才能做出选择。
而在贪心算法中,仅在当前状态下做出最好选择,即局部最优选择。然后再去解做出这个选择后产生的相应子问题。

最优子结构性质

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

与动态规划的区别

**贪心算法:**先依据贪心策略选择并解一个子问题,再进行下一步。
**动态规划算法:**先解决所有的子问题,比较得出一个最优子问题,再进行下一步。

背包问题

问题描述:容量为c的背包,有n种物品,每种物品重w_i,价值为v_i,其中1≤i≤n,
物品不可(可以)分开。
问:如何装入使价值最大?

cnw1w2w3v1v2v3
50310203060100120

物体可分

c>0,wi>0,vi>0,1≤i≤n。找(x1,x2,⋯,xn),0≤xi≤1,可为分数,即仅取一部分,
使 ∑ i = 1 n w i ∗ x i < = c \sum_{i=1}^{n} wi*xi<= c i=1nwixi<=c 达到最大
∑ i = 1 n v i ∗ x i \sum_{i=1}^{n} vi*xi i=1nvixi

//物品可分:贪心算法 
#include <iostream>
#include <iomanip> 
using namespace std;

void Knapsack(int n, int c, int*v, int *w, double *x);

int main() 
{	
	int n=3;//物品数量 
	int c=50;//背包容量 
	int *v=new int[n+1];//价值 
	int *w=new int[n+1];//重量 
	int i;
	double *x=new double[n+1];	
	for(i=1;i<=n;i++)
		x[i]=0;	
	
	//将数据按贪心策略排序 
	v[1]=60;v[2]=100;v[3]=120;
	w[1]=10;w[2]=20;w[3]=30;
	
	Knapsack(n,c,v,w,x); 
	
	for(i=1;i<=n;i++)
	{		
		if(x[i]>0)
			cout<<"物品"<<i<<"装入"<<setiosflags(ios::fixed)<<setprecision(2)<<x[i]<<endl;
		else
			cout<<"物品"<<i<<"不装入"<<endl;
	}
		
	return 0;
}

void Knapsack(int n, int c, int*v, int *w, double *x)
{
	int i;
	
	for(i=1;i<=n;i++)
	{
		if(w[i]>c)
			break;
		else
		{
			x[i]=1;
			c=c-w[i]; 
		}			
	}	
	if(i<=n)	
		x[i]=(double)c/w[i];		
}

step1:准备
按单位价格递减排序,x[ ]初值为0,先都没选
step2:循环
按递减装入物品至不可装为止,从1检查到n
物品装入置x[i]=1,c=c−w[i]
step3:最后
将当前i物品分开,送入c/w[i]

物体不可分

其中,c>0,wi>0,vi>0,1≤i≤n,
找(x1,x2,⋯,xn),xi∈{0,1},
(物品没装xi=0,装入xi=1)
使 ∑ i = 1 n w i ∗ x i < = c \sum_{i=1}^{n} wi*xi<= c i=1nwixi<=c 达到最大
∑ i = 1 n v i ∗ x i \sum_{i=1}^{n} vi*xi i=1nvixi

根据上述步骤:
1.最优子结构性质
若(y_1,y_2,⋯,y_n)是最优解,则(y_2,⋯,y_n)是子问题的最优解

2.递归关系
m(i,j)记背包容量j,可选物品为i,i+1,⋯,n时,0-1背包问题的最优解
在这里插入图片描述
3.计算最优值

template <class Type>
void Knapsack(Type *v, int *w, int n, Type **m)
{
	int jMax=min(w[n]-1,c);//找<w[n]的临界值,并避免物品n比背包容量还要大的情况 
	
	//最小子问题,填写最后一行m[n][j] 
	for(int j=0;j<=jMax;j++)
		m[n][j]=0;
	for(int j=w[n];j<=c;j++)
		m[n][j]=v[n];
		
	 
	for(int i=n-1;i>1;i--)
	{
		jMax=min(w[i]-1,c);
		for(int j=0;j<=jMax;j++)
			m[i][j]=m[i+1][j];//物品i装不进去
		for(int j=w[i];j<=c;j++)
			m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//能装但不装,装进去,两个值中取较大值 
	}
	
	//填最后一行 
	m[1][c]=m[2][c];//若物品1装不进去 
	if(c>=w[1])//若物品1可以装 
		m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]); 
}
 step1:实现递归出口,填矩阵m的第n行(前3行)
 step2:循环,实现递归式,填矩阵m的第(n−1)行到第2行
 step3:填m[1][c]

4.构造最优解

template <class Type>
void Traceback(Type **m, int *w, int c, int n, int *x)//m表已经填好,已知w、c、n,输出x[],0不装,1装入
{
	for(int i=1;i<n;i++)
	{
		if(m[i][c]==m[i+1][c])
			x[i]=0;//相同则不装
		else
		{
			x[i]=1;
			c-=w[i];
		}
	}

	x[n]=(m[n][c])?1:0;		

}

第五章 回溯法

溯法有“通用的解题法”之称。
用它可以系统地搜索一个问题的所有解或任意解
它在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对以该点为根的子树的搜索,逐层向其祖先结点回溯;否则进入该子树,继续按深度优先策略搜索。

问题的解空间

 用回溯法解问题时,应明确定义问题的解空间。
指包含解的“集合”,结构常为树或者图。
问题的解空间至少应包含问题的一个(最优)解。

0-1背包

迭代回溯

有两种方案:
第一种是保存所有子集
第二种是添加剪枝函数

3个状态:左子树、右子树、回溯
在左、右子树添加约束函数、限界函数

两种剪枝函数:
约束函数:在扩展结点处剪去不满足约束的子树;
限界函数:剪去得不到最优解的子树。

0-1背包问题(树结构)

期末考点

1.熟练求出上界的n0,C,g(N)
2.清楚Ackerman函数的代码实现
3.熟练掌握大整数相乘的p,q,r;掌握其求解过程
4.清楚大整数乘法的代码实现,尤其是递归出口
5.掌握动态规划中0-1背包的代码实现、m表、s表、及其求最优值的解
6.在动态规划中0-1背包的代码中,可能会考察代码填空,变量的各阶段的值
7.掌握备忘录代码的具体实现
8.回溯法中的旅行售货员内容 及 整本书的定义内容不会考察。

掌握的意思是必考清楚代表可能重点考察

期末在头歌上考,有代码填空及代码分析两种题型

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/720834.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

DLS平台:惠誉全球经济展望——今年调增至2.6%,明年调减!

摘要 尽管全球货币政策逐渐转向宽松&#xff0c;惠誉国际评级&#xff08;Fitch Ratings&#xff09;在最新的《全球经济展望》中对2024年全球经济增长进行了上调。然而&#xff0c;由于美国经济增速放缓和其他因素的影响&#xff0c;2025年的全球经济增长预期则被下调。这篇文…

MySQL操作数据库语句

mysql关键字不区分大小写 1. 创建数据库 CREATE DATABASE [IF NOT EXISTS] westos (带[ ]表示该语句可有可无) 2. 删除数据库 DROP DATABASE [IF EXISTS] westos 3.使用数据库 -- tab键的上面&#xff0c;如果你的表名或者字段名是一个特殊的字符&#xff0c;就需要带 …

科普童话投稿

《科普童话》杂志是由国家新闻出版总署批准、黑龙江省教育厅主管、黑龙江省语言文字报刊社主办的正规期刊。《科普童话》以培养科学素养与创新探索精神为办刊宗旨&#xff0c;以科学与艺术统一为编辑方针&#xff0c;以科学教育、教育科学作为自己的出发点&#xff0c;致力于对…

重学java 72.正则表达式

人长大之后就在频繁地离别&#xff0c;相聚反而时日无多 —— 24.6.17 一、正则表达式的概念及演示 1.概述 正则表达式是一个具有特殊规则的字符串 2.作用&#xff1a;校验 3.String中有一个校验正则的方法&#xff1a; boolean matches(String regex) —— 校验字符串是否…

《Nest系列 - 2. Nest 代码生成器,让你告别base代码书写!!!》

紧接上文我们做一些核心梳理 核心梳理&#xff1a; /controllers目录&#xff1a;存放控制器文件&#xff0c;每个控制器对应一组路由和请求处理方法。控制器处理来自客户端的HTTP请求&#xff0c;并返回相应的响应。/modules目录&#xff1a;存放模块文件&#xff0c;每个模块…

Docker(三)-Docker常用命令

1.run run命令执行流程:2.帮助启动类命令 2.1 启动docker systemctl start docker2.2 停止docker systemctl stop docker2.3 重启docker systemctl restart docker2.4查看docker状态 systemctl status docker2.5开机启动 systemctl enable docker2.6查看docker概要信息 …

【python】从python中调用matlab函数

【python】从python中调用matlab函数 【先赞后看养成习惯】求关注点赞收藏 问题描述&#xff1a;用python的时候&#xff0c;有部分计算是也有的matlab写好的代码&#xff0c;要改成python格式又比较麻烦&#xff0c;那么我们可以通过python命令来调用matlab运行并返回指定值 …

【Android面试八股文】谈一谈你对http和https的关系理解

文章目录 HTTPHTTPSSSL/TLS协议HTTPS加密、解密流程HTTP 和 HTTPS 的关系具体的差异实际应用总结扩展阅读HTTP(HyperText Transfer Protocol)和HTTPS(HyperText Transfer Protocol Secure)是用于在网络上进行通信的两种协议。 它们在很多方面是相似的,但关键的区别在于安全…

如何解决跨境传输常见的安全及效率问题?

在当今全球化的商业版图中&#xff0c;企业为了拓展国际市场和增强竞争力&#xff0c;跨境传输数据已成为一项不可或缺的业务活动。合格的数据跨境传输方案&#xff0c;应考虑以下要素&#xff1a; 法律合规性&#xff1a;确保方案符合所有相关国家的数据保护法律和国际法规&am…

JupyterLab使用指南(五):JupyterLab的 扩展

1. 什么是JupyterLab的扩展 JupyterLab 扩展&#xff08;Extension&#xff09;是一种插件机制&#xff0c;用于增强 JupyterLab 的功能。通过安装扩展&#xff0c;用户可以添加新的功能、改进现有功能&#xff0c;甚至自定义界面和工作流。扩展可以覆盖各种用途&#xff0c;从…

轻松掌握使用PuTTY SSH连接cPanel的技巧

作为一名多年的Hostease用户&#xff0c;我深知管理服务器的重要性。在我的工作中&#xff0c;SSH连接是必不可少的工具之一&#xff0c;而PuTTY则是我常用的SSH客户端。今天&#xff0c;我想分享一下如何使用PuTTY SSH连接到cPanel&#xff0c;帮助你更好地管理你的服务器。 第…

Gradle 自动化项目构建-Gradle 核心之 Project

一、前言 从明面上看&#xff0c;Gradle 是一款强大的构建工具&#xff0c;但 Gradle 不仅仅是一款强大的构建工具&#xff0c;它更像是一个编程框架。Gradle 的组成可以细分为如下三个方面&#xff1a; groovy 核心语法&#xff1a;包括 groovy 基本语法、闭包、数据结构、面…

漏洞复现之CVE-2012-1823(PHP-CGI远程代码执行)

关于CGI知识点 CGI模式下的参数&#xff1a; -c 指定php.ini文件的位置 -n 不要加载php.ini文件 -d 指定配置项 -b 启动fastcgi进程 -s 显示文件源码 -T 执行指定次该文件 -h和-&#xff1f; 显示帮助题目如下图&#xff0c;没有什么发现 目录扫描一下 dirsearch -u http://4…

ch552g使用torch-pad测试触摸按键遇到的问题

基本工作原理 通过设置好功能在寄存器和控制寄存器检测引脚输入的值。 实际检测阶段分为3个步骤&#xff1a;第一阶段&#xff1a;选择需要检测的阶段&#xff0c;选择扫描周期1或2ms&#xff0c;开启触摸按键中断&#xff0c;然后在87us内为充电准备阶段&#xff0c;87us内数…

SQL注入-中篇

SQL盲注 一、时间盲注 模拟环境&#xff1a;Less-9 概述 延迟注入&#xff0c;一种盲注的手法&#xff0c;提交对执行时间敏感的sql语句&#xff0c;通过执行时间的长短来判断是否执行成功。 时间注入函数 sleep() if() ascii() substring() length() mid()判断是否存在延…

【跟我学RISC-V】(三)openEuler特别篇

写在前面 这篇文章是跟我学RISC-V指令集的第三期&#xff0c;距离我上一次发文已经过去一个多月了&#xff0c;在这个月里我加入了oerv的实习项目组&#xff0c;并且还要准备期末考试&#xff0c;比较忙。 在这篇文章里我会隆重、详细地介绍一个对RISC-V支持非常友好的Linux发…

Apache Druid-时序数据库

Apache Druid&#xff1a;是是一个集时间序列数据库、数据仓库和全文检索系统特点于一体的分析性数据平台&#xff0c;旨在对大型数据集进行快速的查询分析&#xff08;"OLAP"查询)。Druid最常被当做数据库来用以支持实时摄取、高性能查询和高稳定运行的应用场景&…

Linux top 命令使用教程

转载请标明出处&#xff1a;https://blog.csdn.net/donkor_/article/details/139775547 文章目录 一、top 是什么二、top的基础语法三、top输出信息解读 一、top 是什么 Linux top 是一个在Linux和其他类 Unix 系统上常用的实时系统监控工具。它提供了一个动态的、交互式的实时…

Matlab复数相关

文章目录 MATLAB复数相关知识相关函数 MATLAB复数相关知识 相关函数 假定存在复数zabi 函数说明real(z)返回复数z的实部&#xff08;a&#xff09;imag(z)返回复数z的虚部&#xff08;b&#xff09;abs(z)返回复数的模即|z| &#xff08; ( a 2 ) ( b 2 ) \sqrt{(a^2)(b^2)…

modbus流量计数据解析(4个字节与float的换算)

通过modbus协议从流量计中读取数据后&#xff0c;需要将获得的字节数据合成float类型。以天信流量计为例&#xff1a; 如何将字节数据合并成float类型呢&#xff1f;这里总结了三种方法。 以温度值41 A0 00 00为例 目录 1、使用char*逐字节解析2、使用memcpy转换2、使用联合体…