《第三章节计算机软件3.4算法和计算机软件理论基础课件幻灯片》由会员分享，可在线阅读，更多相关《第三章节计算机软件3.4算法和计算机软件理论基础课件幻灯片（51页珍藏版）》请在金锄头文库上搜索。
1、第三章 计算机软件,3.4 算法和数据结构,算法与程序,软件的主体是程序，程序的核心是算法 要使计算机解决某个问题，首先针对问题设计一个解题步骤，然后在根据解题步骤编写程序并交给计算机执行。 这个“解题步骤”就是算法。,算法与程序,算法（Algorithm）：问题求解规则的一种过程描述。 在算法中要精确定义一系列规则，这些规则指定了相应的操作顺序，目标是在有限的步骤内得到所求问题的解答。 算法设计方法：由粗到细，由抽象到具体的逐步求精方法 程序：对解题对象和解题步骤用程序语言进行的一种描述。 程序中用具有一定结构的变量来表示问题的对象 用函数和语句来实现解题的操作 “算法”和“数据结构”是编写
2、程序所要首先考虑的两个重要方面。,3.4.1 算法,算法就是解决问题的方法与步骤,计算机求解问题的步骤,(1) 确定并理解问题； (2) 寻找解决问题的方法与步骤，并将其表示成算法(Algorithm) ； (3) 使用某种程序设计语言描述该算法(编程), 并进行调试； (4) 运行程序，获得问题的解答； (5) 进行评估，改进算法和程序,算法是解决问题的方法与步骤,例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？ 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能),关于算法的三方面问题,如何确定算法（算法设计
3、）？ 如何表示算法（算法表示）？ 如何使算法更有效（算法分析）？,2.算法设计举例,例如，要对包含n个整数元素的数组A按元素值由小到大排序。 第1遍，给出粗略的思路： 从所有整数中选一个最小的，作为已排好序的第一个数； 在剩下的未排序整数中选出最小的，放在已排好序列的最后一个数后面； 反复执行，直到所有整数都放到已排好的序列中。 第2遍，细化，考虑“序列存放在何处” ，如何“反复执行”等。用“伪代码” 描述为： for i=1 to n 选出Ai到An中最小的元素，设为Aj； 交换Ai和j; ,筛选法排序,第一轮比较,第二轮比较,第三轮比较,第四轮比较,筛选法排序,例：筛选法排序。（设从大到小
4、排序） 分析：将N个无序数据存放在 数组中，对数组进行N-1轮扫视。 第一轮扫视：将A（1）与A（2）比较，若A（1）A（2），则交换A（1）和A（2）的值；再将A（1）与A（3）、A（4） A（N）依次按以上规则比较和交换，第一轮扫视完毕，N个数中最大数存放到A（1）中。 第二轮扫视：将A（2）与A（3）、A（4）A（N）依次按以上规则比较； 第三轮扫视：将A（3）与A（4）、A（5）A（N）依次按以上规则比较；这样N-1轮扫视下来排序完成。 ,筛选法排序,假定待排序的N个数已存放在数组 A 中,1.确定排序需要几轮的比较,For I = 1 To N 1 Next I,1.确定排序需要几轮
5、的比较 2.进行每一轮的比较,For J = To Next J,1.确定排序需要几轮的比较 2.进行每一轮的比较 3.在每一轮比较中，比较两 个数的大小，根据比较结 果决定是否交换两个数,If A(I) A(J) then T = A( I ) A( I ) = A( J ) A( J ) = T End If,I + 1,N,Text1 = Text1 & Str(A(I),Text1 = Text1 & Str(A(N),筛选法排序,假定数据已放入A数组中，I，J，T变量均为整型变量 Option Explicit Option Base 1 Dim A(10) As Integer P
6、rivate Sub Cmd数据准备_Click() Dim I As Integer Randomize For I = 1 To 10 A(I) = Int(100 - 9) * Rnd) + 1 Text1 = Text1 & Str(A(I) Next I End Sub,返回,算法设计举例,第3遍，具体给出如何选最小的元素，交换元素等，整合算法。 第4遍，选择程序语言编程，如用C语言编写的函数模块sort如下：,void sort ( int A , int n) int i, min, t ; for( i=0 ; in-1; i+) min=i; for (k=i+1; kn ;
7、k+) if (AkAmin) min=k; t=Ai; Ai=Amin; Amin=t; ,算法,什么是算法,在计算机学科中 , 算法指的是 用于完成某个信 息处理任务的一组有序而明确的、可以由计算机执行的操作 ( 或指令 ), 它能在有限时间内执行结束并产生结果。这里所说的操作 ( 指令 )，必须是计算机可以执行的而且是十分明确的( 什么样的输入一定得到什么样的输出）。 计算机算法是一个有终结的过程 , 它必须在有限步瑕内得到所 求问题的解答。,算法体现了解决问题所需的智能。是一种将智能与他人共享的途径,算法的基本性质,确定性：算法中的每一步运算必须有确切的定义，无二义性。 有穷性: (可
8、终结性)一个算法总是在执行了有穷步运算后终止 能行性：算法中有待实现的运算都是基本的、能精确进行的， 且能在有限的时间内完成。 输入：具有0个或多个输入量。 输出：至少产生一个输出（包括参量状态的变化）,算法的一个显著的特点：它是解决的是一类问题而不是解决一个特定的问题。,算法与程序的区别,终止性区别： 一个程序不一定满足有穷性。例如一个操作系统程序。 能行性区别： 程序中的指令必须是具体机器可执行的，所有细节必须精确描述； 对算法中的运算语句无此限制。可略过可实现的细节，采用“伪代码”、流程图等方式来描述算法。,虽然算法与计算机程序密切相关，但二者也存在区别： 计算机程序是算法的一个实例，是
9、将算法通过某种计算机语言表达出来的具体形式；同一个算法可以用任何一种计算机语言来表达。,3. 算法的表示,算法的表示方法,文字说明 流程图表示 用N-S盒图表示算法 用PAD图描述算法 伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具）,自然语言描述,“比较与的重量，若，则是伪造的；否则再比较与的重量，若，则是伪造的；否则是伪造的。” 缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程,算法的流程图表示,流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件 流程图符号 ：,比文字描述简明，但当算法比较复杂时，理解困难，容易产生
10、错误,求最大公约数的伪代码表示,算法3：辗转相除法求最大公约数 BEGIN input m,n; /*输入正整数m和n*/ do rm mod n; m n; n r; while r0; print m； /*输出最大公约数*/ END,4. 算法的分析,算法分析的基本内容,正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试 简单的算法效率不一定高，要在保证一定效率的前提下力求算法简 两个度量特性 执行算法所要占用的计算机资源的多少，主要有时间复杂度和空间复杂度两个方面。 时间复杂性(Time Complexity
11、) ： 当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 T(n) 空间复杂性(Space Complexity) ： 除原始数据之外，额外占用的存储空间的大小g(n),算法分析,对一个正确的算法，分析其好坏时，应考虑以下因素： 算法是否易理解，是否易调试和易测试等 执行算法所要占用的计算机资源的多少，主要有时间复杂度和空间复杂度两个方面。 两个度量特性 当问题的规模以某种单位由1增至n时 时间代价：解决该问题的算法运行所耗费的时间，以某种单位由T(1)增至T(n)，则称该算法的时间代价为T(n)。 T(n)表示的是，当问题的规模n充分大时，运行该算法程序所需时间的数量级表示 空间代
12、价：解决该问题的算法实现时所占用存储空间也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。,选择排序算法的时间复杂性,假设参加排序的整数有n个 （1）比较操作的次数： 在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2 = (n2 -n)/2 （2）移动操作的次数： 最好情况(原始数据已经排序)时，移动次数为0 最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1) 所以，直接选择排序的时间复杂性 为 O(n2),设置i的初值为1，循环执行下列操作，直到I = n ： 确定Ai 到A
13、n中最小的整数元素的位置，设为j ； 交换Ai和j ； i = i +1 ,算法分析,时间复杂度只是对执行算法所需占用的计算机时间资源的预测，类似地，空间复杂度是对算法所需空间资源的预测。 算法分析时，通常把整个程序中重复执行基本运算的次数之和作为该程序的运行时间特性，记为T(n)实际时间代价是依据算法编制为程序后在计算机中运行时所耗费的时间大小来确定的。,算法分析,算法分析结果的上界比具体的表达式更有意义。因此，常用“O函数”来近似地表示算法分析的（数量级）结果。 称某算法的时间代价（或时间复杂性）T(n)=O(f(n)，则意味着存在常数C和N，当问题规模nN时，有T(n) Cf(n)。 空
14、间复杂度：若存在常数C和N，当问题规模nN时，有S(n) Cg(n)，则称该算法的空间代价（空间复杂度）为O(g(n)。,算法分析,从数学上看，若按数量级递增对算法分析中常见的时间代价排列，则它们依次为常数阶O（1），对数阶O（log2n），线性阶O(n)，线性对数阶O（nlog2n），平方阶O(n2)，立方阶（n3）K次方阶O(nK)， 指数阶O(2n)等。时间代价为指数阶O(2n)的算法，其效率极低，当n值稍大时，这样的算法就无法应用了。 算法的选择 使用次数较少的程序，应力求算法简明易读 反复运行多次的程序，应尽可能选用快速的算法 待解决问题的数据量较大，算法设计时应主要考虑如何节省存储
15、空间,算法设计方法,设计算法是有方法可循的。 常用的算法设计方法：迭代法、穷举搜索法、递推法、递归技术、分治法、回溯法、贪婪法和动态规划法等。 递归：算法实施过程中直接或间接地使用了算法本身。 例如，阶乘函数f的递归定义为： f(int n) if(n=1) return 1;else return n*f(n-1); 定义阶乘f的迭代算法为： f = 1; i = 1; while( i n ) f = f * i; i = i + 1; return f; 递归本质上是一种循环结构，它把“较复杂”的计算逐次归结为“较简单”的计算，一直归结到“最简单”的计算，并得到计算结果为止。,算法设计方
16、法,Private Sub Form_Click() Dim Fact As Long, I As Integer, N As Integer N = InputBox(“输入N“) Fact = 1 For I = 1 To N Fact = Fact * I Next I Print N; “! = “; Fact End Sub,算法设计方法,Private Sub Command1_Click() Dim N As Integer N = InputBox(“输入N“) Print Fact(N) End Sub Private Function Fact(N As Integer) As Long Dim I As Integer If N = 1 Then Fact = 1 Else Fact = N * Fact(N -
