还剩20页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《算法设计与分析》习题第一章算法引论
1、算法的定义?答算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程通俗讲,算法就是解决问题的方法或过程
2、算法的特征?答1算法有零个或多个输入;2算法有一个或多个输出;3确定性;4有穷性
3、算法的描述方法有几种?答自然语言、图形、伪代码、计算机程序设计语言
4、衡量算法的优劣从哪几个方面?答1算法实现所耗费的时间(时间复杂度);2算法实现所所耗费的存储空间(空间复杂度);3算法应易于理解,易于编码,易于调试等等
5、时间复杂度、空间复杂度定义?答指的是算法在运行过程中所需要的资源(时间、空间)多少
6、时间复杂度计算{i=1;while(i=n)i=i*2;}答语句
①执行次数1次,语句
②③执行次数fn2^fn=n则fn=log2n;算法执行时间Tn=2log2n+1时间复杂度记为Olog2n;
7.递归算法的特点?答
①每个递归函数都必须有非递归定义的初值;否则,递归函数无法计算;(递归终止条件)
②递归中用较小自变量函数值来表达较大自变量函数值;(递归方程式)
8、算法设计中常用的算法设计策略?答
①蛮力法;
②倒推法;
③循环与递归;
④分治法;
⑤动态规划法;
⑥贪心法;
⑦回溯法;
⑧分治限界法
9、设计算法 递归法汉诺塔问题?兔子序列(上楼梯问题)? 整数划分问题? 蛮力法百鸡百钱问题?倒推法穿越沙漠问题?答算法如下
(1)递归法汉诺塔问题voidhanoiintnintaintbintc{ifn0{hanoin-1acb;moveab;hanoin-1cba;}}兔子序列(fibonaci数列)递归实现IntFintn{ifn=2return1;elsereturnFn-1+Fn-2;}上楼梯问题IntFintn{ifn=...。