- 1、本文档共5页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
(考研复试)计算机算法与分析笔记
1:递归算法,分治法,贪心算法,动态规划,基本检索和周游方法,回溯法,并行算法。 递归2:0/1背包问题:背包最大承受重量m,现在有n个物品为质量m1,m2,m3…mn,要从n个物品中挑选若干件,使放入背包的质量之和为m。(0/1的意思就是,一个物品,要么取,要么不取)一开始是mn放进容量为m的包中,如果没满,就把m1到m(n-1)放入容量为m-mn的包中,如果满了,就放弃mn,查看m(n-1).knap(m,n),如果mn能放得进去,就进一步考虑knap(m-mn,n-1),如果mn放不进去,就考虑knap(m,n-1)2:汉诺塔问题:Hanoi(n-1,one,three,two)先把n-1个盘子从1柱借助3柱移动到2柱子,Move(one,three)然后把1住上还身下的第n个盘子移到3柱Hanoi(n-1,two,one,three)最后把2住上的n-1块盘子借助1柱移动到3柱。3:自然数拆分:任何一个大于1的自然数都可以划分成若干个小于n的自然数之和。有n/2种拆分Split(7)=1+split(6)=2+split(5)=3+split(4)分治法4:求解一个输入规模很大的问题,直接求解很麻烦,将输入规模分成k个不同的子集合,得到k个不同可独立求解的子问题,求出这些解之后,可以找到适当的方法合并成整个问题的解。5:二分查找,二路归并,快速分类,快速排序,6:找最大和最小元素:就是把数组一分为2,选出左半边的最大值和最小值,选出右半边的最大值和最小值,然后两个最大值相比,选出最大值,然后两个最小值相比,选出最小值。Maxmin(i,j,max,min)//i到j中的最大值和最小值。如果i==j,则说明max=min如果i=j-1,说明就两个数字,直接判断就是了。否则,就运行 maxmin(i,mid,max,min)和maxmin(mid=1,j,max,min)7:找出第k小的元素(并把该元素放在位置k上,并且左边的小于k,右边的大于k):用快速分类partition(m,j),返回值是x,x是首元素被划分以后再数组中的位置,也就第x小的元素。那么再判断,如果x=k,就正确,如果x大于k,就partition(m,x),如果x小于k,就partiotion(x+1,j)8:二次取中法:一位数组划分成多个等长的一位数组,然后分别求中间值,然后诸多中间值再求中间值。9:用二次取中法求第k小元素。先用二次取中法求得中间值,然后判断中间值是不是第k小的元素,如果不是,再对两边分别二次取中,递归。10:斯特拉森矩阵:把16*16的矩阵分块,每个矩阵里面有4个小矩阵,每个小矩阵是8*8,然后用分块矩阵相乘。 贪心算法11:现实世界中,有的问题有很多可以满足约束条件的解,这些解就叫做可行解。为了衡量这些解,我们给出目标函数,那些使目标函数取极值的可行解称之为最优解。这些问题可以用线性规划,非线性规划,动态规划等问题来解决,12:但是有些问题可以选出一种度量值,然后按照这种度量值对输入排序,然后从排序中选出最优解,这种分级处理方法就是贪心方法。13:背包问题:价值/重量 来衡量。14:带有限期的作业排序:也是先看效益值,效益值从高到低依次加入,然后判断是不是可行解。15:最优归并模式(哈夫曼树):30 20 10 三个记录,如果先归并30和20就要移动50次,然后归并10和50移动60,一共110次。但是如果换种方法,先归并20和10,移动30次,然后归并30和30,移动60次,一共移动90次。于是就要用哈弗曼树的方法。16:最小生成树:prim方法和kruskal(克鲁斯卡尔)方法单源最短路径。 动态规划17:一个问题,活动过程可以分为若干个阶段,而且在任一阶段后的行为都仅依赖于此阶段的过程状态,与此阶段之前的过程如何达到这种状态无关,这就是多段决策过程。多段决策过程的每个阶段都可能有多重可供选择的决策,必须从中选取一种决策,一旦各个阶段的决策选定之后,就构成了解决这种问题的一个决策序列。决策序列不同导致问题结果也不同,动态规划就是要选取最优决策序列。18:最优性原理:无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列,这是一个递推。19:动态规划有向前处理(从最后的阶段开始,逐步向前地推的方式列出求前一阶段决策值的递推关系式)和向后处理20:多段图问题:Vi中的节点j到汇点的成本=诸多L中的最小值(j到L的成本+V(i+1)中的L到汇点的成本)也就是我从重庆到江西的成本等于重庆到湖南某个市的成本加上这个市到江西的成本。比如有源点s V2 V3 V4 汇点t,
您可能关注的文档
- (刘艾鸿)艾滋病的病理及预防.doc
- (可借鉴需节选滨水区规划)美国城市滨水区规划建设经验借鉴及启示.docx
- (北京大学)2012秋操作系统原理课件作业.docx
- (整理完)动物病理生理学网上作业题20121102.doc
- (万科技术标准)玻璃雨蓬技术要求.doc
- (小论文)焊缝探伤中伪缺陷波的识别.doc
- (投资)上证50ETF与上证50指数的波动性分析.docx
- (液氨储罐风险评估报告)1.doc
- (病理生理学)病生名词解释【重庆医科大学】五年临床全科专业儿科专业救援专业老年专业.doc
- (9-30)合理开发蓟县栾树资源,加快发展养蜂业的调查研究.doc
- 2024年江西省寻乌县九上数学开学复习检测模拟试题【含答案】.doc
- 2024年江西省省宜春市袁州区数学九上开学学业水平测试模拟试题【含答案】.doc
- 《GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语》.pdf
- 中国国家标准 GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语.pdf
- GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- 《GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构》.pdf
- 中国国家标准 GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 中国国家标准 GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 《GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南》.pdf
文档评论(0)