计算机系统计算机系统 (5).ppt

《计算机系统计算机系统 (5).ppt》由会员分享，可在线阅读，更多相关《计算机系统计算机系统 (5).ppt（73页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第第第5 5章章章章 算法基算法基算法基算法基础础Contents25.1 算法的概念算法的概念15.2 算法的表示算法的表示25.3 常用的基本算法常用的基本算法35.4 算法效率算法效率45.5 算法可视化工具算法可视化工具Raptor55.1 算法的概念算法的概念引言引言算法和程序设计先驱者DonaldErvinKnuth，经典巨著TheArtofComputerProgramming多卷本，以算法研究为主线，认为：算法是算法是计算机科学的基算机科学的基础1968年第一卷基本算法 1969年第二卷半数字化算法1973年第三卷排序与搜索2011年第四卷组合算法1974年，36岁荣获图灵奖

2、迄今最年轻图灵奖获得者“算法不算法不仅是是计算机科学的一个分支，它更是算机科学的一个分支，它更是计算机科学的核心算机科学的核心”计算机科学家DavidHarel算法学：计算精髓3DonaldErvinKnuthDonaldErvinKnuth唐纳德v算法在算法在计算机科学算机科学中的地位中的地位5.1 算法的概念算法的概念什么是算法v通俗说，算法就是解决问题的方法和步骤算法就是解决问题的方法和步骤 算法解决“做什么”和“怎么做”的问题如烹饪菜肴需要有菜谱。菜谱上一般应包括：配料(数据)操作步骤(算法)4DonaldErvinKnuthDonaldErvinKnuth算法的概念算法的概念算法定义

3、及特性5有穷性有穷性明确性明确性可行性可行性零个或多个输入零个或多个输入一个或多个输出一个或多个输出算法算法具备具备五个五个特性特性v算法算法（Algorithm）是解题方案准确而完整的描述，是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法的概念算法的概念算法要素1.基本操作基本操作算术运算：加、减、乘、除等运算关系运算：大于、小于、等于、不等等运算逻辑运算：与、或、非等运算数据传输：输入、输出、赋值等操作 2.控制控制结构构顺序结构，算法按照自上而下的先后顺序依次执行选择结构，也叫分支结构，算法根据不

4、同条件选择性执行循环结构，根据条件对部分操作重复执行多次65.2 算法的表示算法的表示v任何算法都需要将其明确地描述出来，这个描述过程就是算法的表示。常用的常用的表示方法表示方法：自然自然语言言 流程流程图 伪代代码 程序程序设计语言言：算法的最终表示和实现方法7算法的表示算法的表示自然语言自然语言v 自然自然语言言：指人们日常生活使用的语言，可以是汉语、英语或者其它。优点：简单、通俗易懂不足：比较冗长；易产生歧义性【例1】输入三个数，求这三个数中的最大数。利用自然语言描述算法：第1步：输入x、y、z的值；第2步：比较前两个数x和y。如果xy，则将x存入max，否则将y存入max；第3步：再将

5、z和max比较，如果zmax，则将z存入max；第4步：输出max，即为三个数中的最大数。8算法的表示算法的表示自然语言自然语言【例2】写出欧几里德算法的自然语言描述欧几里德算法又称作辗转相除法，人类历史上最早记载的算法。由古希腊数学家欧几里德在TheElements中描述，用于求正整数最大公约数的算法。求解算法自然语言描述：第1步：输入a和b；第2步：如果ab，则交换a和b的值；第3步：求出a、b两数相除的余数r；第4步：如果余数r为0，则执行第7步，否则执行第5步；第5步：将b替换a，r替换b；第6步：重复执行第3步；第7步：输出最大公约数b。9算法的表示算法的表示伪代码伪代码v伪代代码：

6、用介于自然语言和计算机语言之间的文字和符号来描述算法优点：书写简洁、结构清晰，便于向程序过渡不足：不够直观，不易排错v描述形式不必非常严格，主要操作：算术运算符：、mod、关系运算符：、逻辑运算符：and、or、not输入/输出：input、output赋值：或者v表示三种控制结构：10算法的表示算法的表示伪代码伪代码【例3】根据给定的成绩，写出判定成绩等级的算法。成绩60分及以上为及格，否则为不及格。分析：输入：成绩，用变量score表示处理：利用选择结构，用变量grade表示等级输出：等级grade算法伪代码表示：11算法的表示算法的表示伪代码伪代码分析：系列数相加利用循环实现。从1开始，

7、逐项依次累加。输入：系列要加数变量i表示，i从1n，n输入给定处理：利用循环依次累加。累加和sum变量表示，初始值为0输出：最终累加结果sum算法伪代码表示：12【例4】用伪代码描述，求1+2+3+n累加和的算法算法的表示算法的表示流程图流程图v流程流程图：使用图形框和流程线表示各种操作和执行走向优点：形象直观，易于理解不足：复杂问题不便绘制和修改13算法的表示算法的表示流程图流程图【例5】根据给定成绩，使用流程图表示判定成绩等级的算法。条件：成绩85分及以上优秀，60分及以上及格，否则不及格。14算法的表示算法的表示流程图流程图【例6】使用流程图表示例2欧几里德算法求最大公约数155.3 常

8、用的基本算法常用的基本算法v 基本算法基本算法设计：迭代法递归法蛮力法v 经典算法典算法：排序（选择排序、冒泡排序）查找（顺序查找、二分查找）16迭代法迭代法（Iteration）v迭代算法迭代算法：也称辗转法，是不断用变量的旧值递推新值的过程。3方面的设计：确定迭代变量建立迭代关系式对迭代过程进行控制17【例7】求P=n！(n！=1*2*3*n）分析：迭代变量p,初始值1,累乘变量i初始值2；迭代关系式p=p*i；迭代过程in时结束。算法伪代码表示：迭代法迭代法（Iteration）【例8】求斐波那契数列(Fibonaccisequence)的第n项值。说明：斐波那契数列第1项和第2项为1，

9、从第3项开始，每一项均等于它前两项之和。算法伪代码表示：18递归法（法（Recursion）v递归算法算法：直接或间接地调用自身算法的过程 递归定义两个要素：递归出口 递归公式例如：计算阶乘（n！）可以通过递归方式定义函数实现。因为当n=0，0!=1；当n0，n!=n*(n-1)*(n-2)*(n-3)3*2*1=n*(n-1)!如：5！=5*4*3*2*1=5*4！所以计算阶乘，以递归算法定义关系式如下：19Fac(n)=1（n=0）（递归出口）Fac(n)=n*Fac(n-1)（n0）（递归公式）递归法（法（Recursion）v例9使用递归算法，计算斐波那契(Fibonacci)数列的第

10、n项函数值Fib(n)分析：计算fib(n)，须先计算fib(n-1)和fib(n-2)而计算fib(n-1)和fib(n-2)，又须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(2)和fib(1)。假设n=6，递归过程可以用右图表示 20Fib(n)=1 （n=1,n=2）（递归出口）Fib(n)=Fib(n-1)+Fib(n-2)（n2）（递推公式）递归法（法（Recursion）求斐波那契数列，递归算法定义关系式以及伪代码如下：21Fib(n)=1 （n=1、2）（递归出口）Fib(n)=Fib(n-1)+Fib(n-2)（n2）（递归公式）蛮力法（蛮力法（Brut

11、e force）v 蛮力蛮力算算法法：一种简单而直接地解决问题方法。直接基于问题的描述，从有限集合中列举集合中所有元素，对每个元素逐一判断和处理，从中找出问题的解。枚举法是蛮力策略的一种表现形式。依据给定的条件，遍历所有可能的情况，从中找出满足条件的正确答案。考虑2个要素：找出枚举范围 找出约束条件22蛮力法（蛮力法（Brute force）【例10】百鸡问题。公鸡5元1只，母鸡3元1只，小鸡3只1元，100元买100只鸡。那么可买公鸡、母鸡和小鸡各多少只？分析：假设每种鸡至少买1只，公鸡、母鸡、小鸡分别可买x、y、z只，公鸡需5*x元，母鸡3*y元，小鸡z/3元。列出代数方程：x+y+z=1

12、00只5x+3y+(1/3)z=100元23蛮力法（蛮力法（Brute force）【例11】猜比赛结果。某大学ICPC队的A,B,C,D四支候选队参加预选赛。赛完4名队长问带队教练谁赢了，教练让他们猜。最后只有1个队长猜对了。请问，哪个队赢得了比赛？A队长说：“不是我们队，也不会是C队”；B队长说：“是我们队或者是D队”；C队长说：“应该是A队，不会是B队”；D队长说：“B队长肯定猜错了”。分析：将A,B,C,D候选队分别编号为1、2、3、4，变量x存放Winner编号24排序算法排序算法v排序排序（Sorting）是对一组数据按照一定顺序递增或递减地排列。经典排序算法：选择排序、冒泡排序、

13、插入排序、快速排序、堆排序、归并排序等等介绍其中两种排序算法：选择排序排序 冒泡排序冒泡排序25选择排序（排序（Selection Sort）v基本思想基本思想：（以升序为例）所有元素进行比较，从中选出最小元素与第1个元素交换位置；再从余下n-1个未排元素中选出最小元素与第2个元素交换位置。以此类推，直至完成第n-1个位置元素选择（第n个位置就只剩唯一的最大元素），排序完成。26冒泡排序（冒泡排序（Bubble Sort）v基本思想基本思想：(以升序为例)将相邻的第1、第2个元素进行比较，如果逆序就交换位置。再将第2、第3个元素作同样比较，直至完成第n-1、第n个元素的比较，在最后的元素就是最

14、大数。依次类推，再对前面n-1个元素重复以上步骤，直至整个序列有序为止。27查找算法找算法v查找找（Searching）：在大量数据中寻找一个特定的数据元素查找算法有多种：顺序查找、折半查找、分块查找、哈希表查找、插值查找等介绍其中两种：顺序序查找找折半折半查找找28顺序序查找（找（Sequential Search）v顺序序查找找，又称线性查找，属于无序查找基本思路基本思路：从数列第1个元素开始逐个与需要查找元素进行比较，直到找到目标元素，或直到最后都没有出现目标元素。例如：假设一数组a，各元素存放数组a1，a2，a3，an中，要从中查找关键字为key的元素。算法伪代码：29二分二分查找（找

15、（Binary Search）v二分查找，又称为折半查找，属于有序查找基基本本思思路路：在有序(升序)列表中，从中间元素开始比较，若正是要找元素，则查找成功；若待查元素小于中间元素，则在中间元素的左半区继续查找，反之在中间元素的右半区继续查找。重复上述过程，直到查找成功，或查找区域不存在，查找失败止。例如：数列6,15,18,22,39,58,63,85,89,93，查找关键字8930二分二分查找（找（Binary Search）算法描述算法描述（数列An，查找关键字K）第1步：赋值L1，Rn；/设置初始查找区间第2步：测试查找区间L，R是否存在（LAmid，则Lmid+1，查找在右半区进行，

16、重复第2步；如果K0整数)表示，如scores1，scores2，scores340Raptor使用基使用基础v基本运算包括以下几大基本运算包括以下几大类数学运算：、或、mod字符运算：（字符串连接）关系运算：、=、0)or(year mod 400=0)C(year mod 4=0 xor year mod 1000)or(year mod 400=0)D提交单选题1分589.蛮力法的适用范围()。一切问题A仅查找问题B解的个数极多问题C解的个数有限且可一 一列举问题D提交单选题1分5910.顺序查找的时间复杂度为()。O(n)AO(n2)BO(2*n)CO(2/n)D提交单选题1分6011

17、.算法的时间复杂度是指()。算法的执行时间A算法所处理的数据量B算法程序中的语句或指令条数C算法在执行过程中所需要的基本运算次数D提交单选题1分6112.算法的空间复杂度是指()。算法在执行过程中所需要的计算机存储空间A算法所处理的数据量B算法程序中的语句或指令条数C算法在执行过程中所需要的临时工作单元数D提交单选题1分6213.算法必须满足有穷性,而程序不一定满足有穷性,如操作系统等()。正确A错误B提交单选题1分6314.有序数据序列也可以使用顺序查找算法()。正确A错误B提交单选题1分6415.Raptor中,表达式floor(random*100)可以生成0,100之间的随机整数()。

18、正确A错误B提交单选题1分6516.一个算法有一个或多个输入,同样有一个或多个输出()。正确A错误B提交单选题1分6617.Raptor基本编程符号除了输入输出符号还包括()。迭代A赋值符号B指针C选择和循环D调用E提交多选题1分6718.度量算法的执行效率可以用()。算法正确性A算法在计算机上易于调试B算法指令的执行次数C算法所消耗存储空间D算法易于理解E提交多选题1分6819.表达式 5/0 不符合算法特性中的填空1。作答正常使用填空题需3.0以上版本雨课堂填空题1分6920.递归是指函数直接或者填空1通过一些语句调用自身的过程。作答正常使用填空题需3.0以上版本雨课堂填空题1分7021.使用二分查找算法在n个有序列表中搜索一个特定元素,在最好情况和最坏情况下搜索的时间复杂性分别为(O(填空1)和(O(填空2)。作答正常使用填空题需3.0以上版本雨课堂填空题2分7122.如何理解算法的有穷性?为什么算法一定要有输出?作答正常使用主观题需2.0以上版本雨课堂主观题10分7223.用流程图表示算法有什么优缺点?作答正常使用主观题需2.0以上版本雨课堂主观题10分7324.简述选择排序和冒泡排序算法的不同。作答正常使用主观题需2.0以上版本雨课堂主观题10分