算法设计与分析 复习讲义

《算法设计与分析 复习讲义》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、课程介绍干晓聪sliant13@sina.com15626013626南海楼308sina微博资料下载通知1~16周教学17～18周复习答疑19～20考试周考试卷面60%考平时所讲知识点不考编程考前有复习题库平时成绩40%作业=上机实验自选题目交十次，或大作业（需同意）上机：南海楼209每周四下午14:00~16:00Java16:00~18:00数据结构交作业，可在宿舍做上课出勤课程定位：计算机基础=>编程语言=>数据结构=>算法=>复杂性理论，专题方向横向扩充，纵向深入教材参考书做题学习方法：编程基础是前提，自学最重要收集：面试题，算法题，编程题，智力题引论一些数学公式估计调和

2、级数前n项1/x积分得对数1/x和1/(x+1)所夹估计误差前若干项精确计算，后面误差小P10题1.7P10题1.8P10题1.9Fibonacci数的通项：母函数，z变换计算机中的数进制转换：DecBinHexOct整数转换：DecInt=>Bin模二任意进制带权相加：BinInt/Float=>Dec任意进制浮点数除法：4/3转二进制任意进制二进制的乘除法x*3整数编码：补码浮点数编码：IEEE754，二进制科学计数法，能表示的浮点数个数是有限的，能表示的浮点数的精度是有限的，浮点数在数轴上的分布是不均匀的。HEX16进制编码有效数字指数实际表示名称说明符号+指数纯小数0000

3、0000000000000线性区00000000000012-1022*2-52subnormalminFFFFFFFFFFFFF2-1022*(1-2-52)subnormalmax00100000000000001+0-10222-1022realmin3CB00000000000001+0-522-52eps精度，HEX0.00000000000013FF00000000000001+0013FFFFFFFFFFFFFFF2-eps02-eps屏幕显示2.0000...40000000000000001+012屏幕显示240080000000000001+1/2137FEFF

4、FFFFFFFFFFF2-eps1023(2-eps)*21023realmax7FF0000000000000infx/07FFxxxxxxxxxxxxxNaN0/0;一般FFF8000000000000考虑-0，-infMatlab演示formatlongformathexformatshortformat1/0=inf0/0=NaN运算时阶码调整/对齐1/24+11+eps=HEX3FF00000000000012+eps=HEX4000000000000000浮点数的误差：x=1+eps,x-1x=2+eps,x-2x=4/3-1,y=3*x,z=1-y程序中的数据数组：下

5、标指针：地址；内存看作巨大的字节数组，下标结构；首地址+偏移=实际地址本质上都是地址/指针内存，磁盘：巨大数组段页式/扇区、簇、文件分配碎片算法分析时间复杂度1for(inti=0;i

6、长子序列和：求积分最大子序列和，不定长：n^3,n^2求积分，转为求最大增长式落差。注意最大子序列，起点一定是终点前的最小值，终点一定是起点后的最大值。从前往后扫描积分序列，求以当前点为终点的最大增长落差：记录迄今为止最小值，与当前值之差就是。再参见P21算法4，里面的ThisSum就是以当前点为终点的最大子序列，其清零对应在积分序列里，每次碰到迄今最小值后就清零，所以就是从迄今最小值到当前点。直接证明此算法：以ThisSum清零点分段，每段和都<=0。段内，积分曲线始终>=0，反向积分就一定<=0。所以，以当前点为终点的最大子序列，必以最后一个ThisSum清零点位起点；起点再往

7、前延伸是不会使和增大的。P28题2.12最小子序列和：考虑负数最小正子序列和：不会是要求子序列内全正数，求子序列和最小，如此取最小正数即可。应该是要求所有子序列中，和为正，最小。扫描积分序列，对每个当前元素，求前面最接近又小于当前元素。可以有。最大子序列积：考虑对数。扫描积分序列，对每个当前元素，前面按符号分两组，按当前元素的符号求正组的最大（可能不存在），负组的最大。最大公约数GCD欧几里德辗转相除法a/b=q...rb/rP23最小公倍数a/x*b/x*x=a*b