沈鑫剡编著《计算机基础与计算思维》第5章配套课件.ppt

《沈鑫剡编著《计算机基础与计算思维》第5章配套课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机基础与计算思维第五章第5章算法必须给出解决问题步骤步骤是机械的、计算机可执行的算法是描述问题解决过程的机械的、计算机可执行的步骤算法设计是计算机解决问题的基础第5章难点和重点学习思路本章主要内容算法的作用和定义排序算法折半查找算法汉诺塔问题算法时间复杂度分析第5章算法5.1算法的作用和定义本讲主要内容算法的作用算法的定义算法分层和抽象算法设计算法分析算法的重要性一、算法的作用一是计算机已经到了无所不能的程度；每一条机器指令的功能相对简单；任何计算机语言编写的程序最终需要转换成机器语言程序；算法的作用是提供一种通过组合机

2、器语言中的数据传送指令、运算指令和控制指令构建能够完成计算机魔术般功能的机器语言程序的方法。算法定义算法（algorithm）是特定问题求解步骤的一种描述，是指令的有限序列，每一条指令表示一个或多个操作。二、算法的定义算法具有如下特性：有穷性。算法必须在执行有穷步骤后完成，且每一步骤都在有穷时间内完成。确定性。算法中的每一条指令无歧义，对于任何给定条件，算法只有唯一执行路径，相同输入只能得出相同的输出。可行性。算法描述的操作步骤都是可以实现的。输入。算法允许有零个或多个输入。输出。算法有一个或多个输出，输出与输入之间存在某种

3、关系。二、算法的定义一旦给定两个正整数m和n，经过有限步骤一定可以求出它们的最大公约数，每一步骤可以在有限的时间内完成；对于特定的两个正整数m和n，求解它们的最大公约数的执行路径是确定的；算法中的每一个步骤都可以用计算机语言的一条或几条语句实现；两个正整数m和n作为输入；两个正整数m和n的最大公约数作为输出。二、算法的定义三、算法分层和抽象算法具有层次结构；第一层算法将解决问题的步骤细化到能够用高级语言中一条或几条语句实现的程度；第二层算法由编译器实现，将用高级语言中一条或几条语句描述的步骤转换成用一系列机器指令描述的步骤；

4、算法抽象过程使得解决应用问题的算法设计者在不需要了解计算机硬件结构和机器语言细节的情况下，就能完成算法设计过程。四、算法设计计算机解决问题过程分析问题计算机能不能做？数学模型数据抽象算法设计得出求解问题的步骤算法的每一步骤可以通过高级语言的一条或几条语句实现四、算法设计计算机解决问题过程程序设计计算机语言描述解决特定问题的算法测试程序验证算法和程序在各种应用环境与可能的输入对象组合下是否都能得到正确的输出综合运用已有算法解决某个特定问题的算法往往是一种，或几种经典算法的组合分而治之将一个大型复杂问题分解为若干个能够解决的小型

5、简单问题四、算法设计第一层算法给出查找素数i和j，且m=i+j的思路；第一层算法中，判断某个正整数是否是素数的过程作为一个步骤；第二层算法给出判别某个正整数i是否是素数的过程。四、算法设计第一层算法第二层算法主程序中通过调用函数fac完成判断正整数i和j是否是素数的过程。四、算法设计intfac（inti）{intn，k=2；while（k＜i）{If（i%k＝＝0）{n=0；return（n）；}k=k+1；}n=1；return（n）；}inti=2，j，m=100，t=0；while（t＝＝0）{if（fac（i）＝＝

6、1）{j=m－i；if（fac（j）＝＝1）{t=1；}else{i=i+1；}}else{i=i+1；}}五、算法分析用算法执行时间与输入运算对象数量之间的关系来表示算法的时间效率；空间效率是特定输入条件下，执行算法所需的存储器空间；一个简单的算法是一个容易理解和容易编程的算法；普遍性主要指算法解决的问题的普遍性和算法自身的通用性。六、算法的重要性算法是了解计算机如何做的关键；算法具有普遍性；算法设计是拓展计算机应用的关键；经典算法有重大学习价值。5.2排序算法本讲主要内容问题说明冒泡排序算法快速排序算法排序算法分析排序算

7、法的启迪一、问题说明排序过程就是将无序存放的数据变成有序存放。完成排序后，存放在数组元素a[0]中的是7个整数中最小的整数13，存放在数组元素a[6]中的是7个整数中最大的整数97。二、冒泡排序算法第一次比较和交换过程从数组元素a[0]开始，相邻数组元素两两比较和交换，每一次比较和交换过程都是将大的数据交换到下标较大的数组元素中；最大整数97成为数组元素a[6]的值。二、冒泡排序算法第二次比较和交换过程从数组元素a[0]开始，相邻数组元素两两比较和交换，每一次比较和交换过程都是将大的数据交换到下标较大的数组元素中；次大整数7

8、6成为数组元素a[5]的值；数组元素a[6]不参与比较交换操作。这种比较和交换过程一直进行，每一次比较和交换过程比前一次比较和交换过程减少一个参与比较和交换操作的数组元素，最后一次比较和交换过程只有a[0]和a[1]两个数组元素参与比较和交换操作。二、冒泡排序算法变量i控制交换和比较过程，