中科院自动化所博士2006 算法设计与分析

算法设计与分析1、(1) 证明：O(f)+O(g)=O(f+g)（7分）(2) 求下列函数的渐近表达式：（6分）① 3n 2+10n;② 21+1/n;2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。

（15分）(1);5log )(;log )(2+==n n g n n f (2);)(;log )(2n n g n n f == (3);log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。

（13分）4、试用动态规划算法实现最长公共子序列问题。

（15分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。

试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。

（12分）6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。

我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括：(1)删除一个字符。

(2)插入一个字符。

(3)将一个字符改为另一个字符。

将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。

试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。

（16分）⎣⎦2/)(;3)(i i g i i f ==。

对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。

（16分）1、⑴证明：令F(n)=O(f),则存在自然数n 1、c 1，使得对任意的自然数n ≥n 1，有：F(n)≤c 1f(n)……………………………..（2分）同理可令G(n)=O(g),则存在自然数n 2、c 2，使得对任意的自然数n ≥n 2，有：G(n)≤c 2g(n)……………………………..（3分）令c 3=max{c 1,c 2},n 3=max{n 1,n 2},则对所有的n ≥n 3，有： F(n)≤c 1f(n)≤c 3f(n)G(n)≤c 2g(n)≤c 3g(n)……………………………..（5分） 故有：O(f)+O(g)=F(n)+G(n)≤c 3f(n)+c 3g(n)=c 3(f(n)+g(n)) 因此有：O(f)+O(g)=O(f+g)……………………………..（7分） ⑵ 解：① 因为;01033)103(lim 222=+-+∞→n n n n n n 由渐近表达式的定义易知： 3n 2是3n 2+10n 的渐近表达式。

分治法1、二分搜索算法是利用（?分治策略）实现的算法。

9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略?）实现的算法。

34．实现合并排序利用的算法是（分治策略）。

实现大整数的乘法是利用的算法（?分治策略）。

17．实现棋盘覆盖算法利用的算法是（分治法）。

29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。

不可以使用分治法求解的是（0/1背包问题）。

动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。

下列算法中通常以自底向上的方式求解最优解的是（动态规划法?）备忘录方法是那种算法的变形。

（动态规划法）最长公共子序列算法利用的算法是（?动态规划法）。

矩阵连乘问题的算法可由（动态规划算法B）设计实现。

实现最大子段和利用的算法是（??动态规划法?? ）。

贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。

回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。

剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（?分支界限法）的一搜索方式。

分支限界法解最大团问题时，活结点表的组织形式是（?最大堆）。

分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

习题2-1 求下列函数的渐进表达式：3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、3^n、4n^2 、20n、n^2/3、logn、2习题2-4(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。

在某台计算机上实现并完成该算法的时间为t秒。

现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。

对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'<n+log100=n+6.64习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

【关键字】分析《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。

2.程序：程序是算法用某种程序设计语言的具体实现。

2、简答题：1.算法需要满足哪些性质？简述之。

算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。

2）输出：算法产生至少一个量作为输出。

3）确定性：组成算法的每条指令清晰、无歧义。

4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。

该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

2）用递推来实现递归函数。

3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

三、算法编写及算法应用分析题：1.冒泡排序算法的基本运算如下：for i ←1 to n-1 dofor j ←1 to n-i doif a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。

解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。

1）设比较一次花时间1；2）内循环次数为：n-i次,（i=1,…n），花时间为：3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。

第29卷第4期铁 道 学 报Vol.29　No.42007年8月J OURNAL OF T H E CHINA RA IL WA Y SOCIET Y August 2007文章编号:100128360(2007)0420096205非赫兹接触下轮轨接触蠕滑力的计算王小松1,2,　葛耀君2,　吴定俊2(1.重庆交通大学桥梁系,重庆　400074;2.同济大学土木工程防灾国家重点实验室,上海　200092)摘　要:以弹性半空间非赫兹接触理论计算轮轨法向接触问题,得到比较真实的法向压力分布。

在此基础上,根据修正的FastSim 算法计算了轮轨在单点接触、轮缘接触和单接触斑内两点接触情况下的蠕滑力。

与CON 2TACT 的对比表明,修正的FastSim 算法在计算轮缘接触时具有比较精确的结果,在计算单接触斑内两点接触时的精度相对于Shen 2Hedrick 2Elkins 理论和FastSim 算法均有较大的提高。

基于修正的FastSim 算法编制了便于风2列车2桥梁耦合分析应用的蠕滑力插值数表MFT TL M 。

关键词:非赫兹接触;轮轨接触;蠕滑力中图分类号:U211.5 文献标志码:AC alculation of Creep Forces of Wheel 2rail Contact under Non 2H ertzian ConditionsWAN G Xiao 2song 1,2,　GE Yao 2jun 2,　WU Ding 2jun 2(1.Depart ment of Bridge Engineering ,Chongqing Jiaotong University ,Chongqing 400074,China ;2.State Key Laboratory for Disaster Reduction in Civil Engineering ,Tongji University ,Shanghai 200092,China )Abstract :Based on t he real normal p ressure dist ribution of wheel 2rail contact ,which is obtained by t he elastic half 2space non 2Hertzian co ntact t heory ,t he Fast Sim algorit hm is modified and t hen applied to calculate t he creep forces under t he circumstances of single contact ,flange contact and double contact in t he single contact parison wit h CON TACT indicates t hat t he modified Fast Sim algorit hm gives relatively accurate re 2sult s when flange co ntact occurs ,and compariso n wit h t he Fast Sim algorit hm and Shen 2Hedrick 2Elkins t heory shows t hat t he modified Fast Sim algorit hm gives better solution when double contact occurs in t he single con 2tact zone.The modified Fast Sim Traction Table used for wind 2vehicle 2bridge coupling analysis is also compiled.K ey w ords :non 2Hertzian contact ;rail 2wheel contact ;creep force 轮轨接触蠕滑力的计算是风2列车2桥梁耦合振动分析中的核心问题之一。