算法设计第一章

第一章习题（1-1,1-2,1-3,1-6）1-1 求下列函数的渐进表达式3n2+10n = O(n2)n2/10+2n = O(2n)21+1/n = O(1)logn3 = O(logn)10log3n = O(n)知识点：如果存在正的常数C和自然数N0，使得：当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).这时，可以说f(N)的阶不高于g(N)的阶。

1-2 论O(1)和O(2)的区别O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。

1-3 从低到高排列以下表达式（按渐进阶排列以下表达式）结果：2 logn n2/320n 4n23n n! 分析：当n>=1时，有logn< n2/3当n>=7时，有3n < n!补充：当n>=4时，有logn> n1/31-6 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=Θ(g(n))。

知识点：f(n)的阶不高于g(n)的阶：f(n)=O(g(n))；f(n)的阶不低于g(n)的阶：f(n)=Ω(g(n))；f(n)与g(n) 同阶：f(n)=Θ(g(n)) (1)f(n)= logn2 ; g(n)= logn+5f(n)与g(n)同阶，故f(n)=Θ(g(n)) (2) f(n)= logn2 ; g(n)= n1/2当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。

如依次用n=1, 21, 22, 23, 26, 28, 210 (3) f(n)= n ; g(n)= log2nf(n)=Ω(g(n))(4) f(n)= nlogn+n; g(n)= lognf(n)=Ω(g(n))(5) f(n)= 10 ; g(n)= log10f(n)=Θ(g(n))(6) f(n)= log2n ; g(n)= lognf(n)=Ω(g(n))(7) f(n)= 2n ; g(n)= 100 n2f(n)=Ω(g(n))(8) f(n)= 2n ; g(n)= 3nf(n)=O(g(n))。

第一章算法概述1、算法的五个性质：有穷性、确定性、能行性、输入、输出。

2、算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A)，C=F(N,I,A。

3、算法的时间复杂度的上界，下界，同阶，低阶的表示。

4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。

5、常用的几种数据结构：线性表、树、图。

第二章递归与分治1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。

递归的时间复杂性可归结为递归方程：1 11= 1T(n) <aT(n—b) + D(n) n> 1其中，a是子问题的个数，b是递减的步长，~表示递减方式，D(n)是合成子问题的开销。

递归元的递减方式~有两种：1、减法，即n -b，的形式。

2、除法，即n / b，的形式。

2、D(n)为常数c：这时，T(n) = 0(n P)。

D(n)为线形函数cn：r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x：r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI：中，p= log b ao考虑下列递归方程：T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解：方程中均为a = 4，b = 2，其齐次解为n2。

对⑴，T a > b (D(n) = n) /• T(n) = 0(n);对⑵，•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶，•/ a < b3(D(n) = n3) - T(n) = 0(n3)；证明一个算法的正确性需要证明两点：1、算法的部分正确性。

算法程序设计知识点汇总算法与程序设计知识点汇总第一章计算机解决咨询题的基本过程一、开始分析咨询题设计算法编写程序调试、运行程序咨询题解决二、算法-----程序设计的“灵魂”1、定义：算是解决咨询题的办法和步骤 21、确定性：每一步都有确切的含义2、有穷性：执行的步骤和每一步执行的时刻基本上有限的3、输入：有零个或多个输入4、输出：至少产生一具输出5、可行性：原则上可精确运行3、算法的描述：1、自然语言 2、流程图(P11) 3、伪代码（p12）4、计算机语言三：程序设计语言的进展：须通过转换处理。

高级语言：更接近于自然语言（英语）和数学语言的编程语言，容易掌握和使用，也别能直截了当识不，必须通过转换才干被计算机执行。

第二章一、visiual basic 可视化程序开辟工具，要紧是让程序设计人员利用软件本身所提供的各种控件，像搭积木一样构造应用程序的各种界面，然后再编写少量的代码就能够构建应用程序，提供了程序设计，编辑，调试，运行于一体的集成开辟环境。

二、VB6.0的集成开辟环境三个工作栏：标题栏菜单栏工具栏六个基本窗口：主窗口(main) 窗体窗口(form) 工具箱窗口(toolbox)工程窗口(project) 属性窗口(properties) 窗体布局窗口(formlayout)三、属性---用来描述对象的外部特征四、常用控件熟悉常用控件(标签、文本框、命令按钮)的作用，图标及其属性五、数据的表示与处理 1、Vb 数据类型2、常量与变量的讲明：常量讲明：Const a=3.14 const a as single=3.14变量讲明： Dim a As integerDim b As integerDim a,b As integer3、运算符(1) 算术运算符(2)字符串运算符＆、+字符串连接" 123 " + " 456 "结果 " 123456 "" 123 " & " 456 " 结果 " 123456 "区不: + 两边必须是字符串, & 别一定例如:"abcdef" & 12345 ' 结果为 "abcdef12345 ""abcdef " + 12345 ' 出错"123" & 456 ' 结果为" 123456 "“123” + 456 ' 结果为 579注意："123 " + True'结果为 122True转换为数值-1，False转换为数值0(3)关系运算符a、将两个操作数举行大小比较,结果为逻辑量。

算法分析与设计习题第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。

2、多项式10()m m A n a n a n a =+++的上界为O(n m )。

3、算法的基本特征：输入、输出、确定性、有限性。

4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。

5、计算下面算法的时间复杂度记为： O(n 3) 。

for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]= c[i][j]+a[i][k]*b[k][j];}6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。

7、算法设计的基本要求：正确性 和 可读性。

8、计算下面算法的时间复杂度记为： O(n 2) 。

for （i ＝1；i<n; i++）{ y=y+1;for （j ＝0；j <=2n ；j++ ）x ＋＋；}9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。

10、算法是指解决问题的 方法或过程 。

二、简答题：1、按照时间复杂度从低到高排列：O( 4n 2)、O( logn)、O( 3n )、O( 20n)、O( 2)、O( n 2/3),O( n!)应该排在哪一位？答：O( 2)，O( logn)，O( n 2/3)，O( 20n)，O( 4n 2)，O( 3n )，O( n!)2、什么是算法？算法的特征有哪些？答：1）算法：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

通俗讲，算法：就是解决问题的方法或过程。

2）特征：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性 ； ４)有穷性3、给出算法的定义？何谓算法的复杂性？计算下例在最坏情况下的时间复杂性？for(j=1;j<=n;j++) (1)for(i=1;i<=n;i++) (2) {c[i][j]=0; (3)for(k=1;k<=n;k++) (4)c[i][j]= c[i][j]+a[i][k]*b[k][j]; } (5)答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

第一章多选答案：1．ACD 2．ABC 3．ABCD 4．BCD 5．ABC 6 ．ABCD 7． ACD 8．ABD 9．ABC 10．ABCD 11.ACD单选题答案：第一章单选题1．流程图中表示“处理”的图形是( )。

∙A) 矩形∙B) 菱形∙C) 圆形∙D) 平行四边形2．以下不是程序设计语言的是( )。

∙A) BASIC∙B) C语言∙C) Word∙D) Pascal3．在调试程序过程中，下列哪一种错误是计算机检查不出来的？( ) ∙A) 编译错误∙C) 逻辑错误∙D) 任何错都能查出来4．Visual Basic 是一种面向( )程序设计语言。

∙A) 事件∙B) 过程∙C) 对象∙D) 属性5．计算机能够直接识别的语言是( )。

∙A) 伪代码∙B) 高级语言∙C) 机器语言∙D) 汇编语言6．程序设计语言的发展大致经历了几个阶段，以下说法正确的是( )。

∙A) 机器语言、高级语言、汇编语言∙B) 高级语言、汇编语言、机器语言∙C) 机器语言、汇编语言、高级语言∙D) 汇编语言、机器语言、高级语言7．以下说法正确的是( )。

∙A) 算法+数据结构=程序∙B) 算法就是程序∙C) 数据结构就是程序∙D) 算法包括数据结构8．求s=1+2+3+……+100的和。

编程时最适合使用的结构为( )。

∙A) 顺序结构∙B) 分支结构∙C) 循环结构∙D) 层次结构9．机场托运行李，每人免费20千克，超过20千克不到40千克，则超出部分按每千克10元收费，如果超过40千克，则超过部分按每千克20元收费。

这种计费程序最适合用到的程序结构是( )。

∙A) 循环结构∙B) 赋值结构∙D) 顺序结构10．结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构( )。

∙A) 顺序结构∙B) 输入、输出结构∙C) 选择结构∙D) 循环结构11．任何算法都可以由三种基本结构完成，下列不属于基本结构的是( )。