算法与程序设计(高中选修)复习资料word格式word格式[精品].doc

主题一 利用计算机解决问题的基本过程 点击考点 了解利用计算机解决问题的基本过程 了解问题分析与算法设计之间的关系 了解算法的基本特征 能用自然语言、流程图或伪代码描述算法 了解程序设计语言产生与发展过程 考点注解 了解利用计算机解决问题的基本过程 一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整直道到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 了解问题分析与算法设计之间的关系 任何一个问题必须弄清楚其内容、性质、规模，才能找到解决问题的方法，所以分析问题就是要确定用计算机做什么，接下来，就解决怎么做的问题，也就是算法。 算法就是解决问题的方法与步骤。有了算法才能转化成指令代码，计算机才能按照指令代码一步一步去执行，直到得到问题的解。 算法是程序设计的灵魂，算法独立于任何一种程序设计语言，一个算法可以用多种程序设计语言来实现。 一个问题，可能有多种算法 ，应该通过分析、比较、挑选一种最优的算法。一个好算法必须用到科学的方法 ，应该好好学习各学科处理问题的科学方法。 了解算法的基本特征 一个算法应该具有以下特征： 1）有穷性：一个算法必须保证它的执行步骤是有限的，即它是能终止的。 2）确定性：算法中的每一个步骤必须有确切的含义，而不应当是模糊的，模棱两可的。 3）可行性：算法的每一步原则上都能精确运行 4）有零个或多个输入：所谓输入是指算法在执行时需要从外界获得数据，其目的是为算法建立某些初始状态。如果建立初始状态所需的数据已经包含在算法中了，那就不再需要输入了。 5）有一个或多个输出：算法的目的是用来求解问题的，问题求解的结果应以一定的形式输出。 能用自然语言、流程图或伪代码描述算法 一个算法可以用多种不同的方法来描述。一般用自然语言、流程图、伪代码描述。 1）自然语言 自然语言是人们日常所用的语言，如汉语、英语、德语等。用自然语言描述算法符合我们的表达习惯，并且容易理解。缺点：书写较烦、不确定性、对复杂的问题难以表达准确、不能被计算机识别和执行。 用自然语言描述一下解决以下问题的算法：借助一个空杯将一杯橙汁和一杯可乐互换所盛放的杯子。 (1) 橙汁倒入空杯； (2) 可乐倒入刚空出的杯子； (3) 橙汁倒入刚倒出可乐的杯子 2）流程图 流程图是由一些图框和流程线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序。也称为程序框图，它是算法的一种图形化表示方法。优点：形象、直观、容易理解。 由键盘输入一个任意值作为 n，求1到 n 的累加值。 用流程图的方法描述一下求一元二次方程 ax2+bx+c=0 （其中 a≠0 ）的实数解的算法。 Input 三个实数值（其中 a≠0 ） To a,b,c d=b^2-4*a*c If d 大于等于 0 Then X1= （ -b-d ） /2*a X2= （ -b+d ） /2*a 输出 X1和 X2的值 Else 输出方程无实数解 3）伪代码 伪代码是介于自然语言和计算机程序语言之间的一种算法描述。 优点：简洁、易懂、修改容易 缺点：不直观、错误不容易排查 比如： 　　IF 九点以前 THEN 　　do 私人事务； 　　ELSE 9点到18点 THEN 　　工作； 　 　ELSE 　　 下班; 　　 END IF 这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更加直观. 了解程序设计语言产生与发展过程 程序设计语言泛指一切用于书写计算机程序的语言。 计算机语言的发展经历了从机器语言、汇编语言到高级语言的历程，如图1-1所示。 1） 机器语言（Machine Language）计算机使用的是由“0”和“1”组成的二进制数，二进制编码方式是计算机语言的基础。计算机发明之初，科学家只能用二进制数编制的指令控制计算机运行。每一条计算机指令均由一组“0”、“1”数字，按一定的规则排列组成，若要计算机执行一项简单的任务，需要编写大量的这种指令。这种有规则的二进制数组成的指令集，就是机器语言（也称为指令系统）。不同系列的CPU，具有不同的机器语言，如目前个人计算机中常用AMD公司的系列CPU和Intel公司的系列CPU，具有不同的机器语言。机器语言是计算机唯一能识别并直接执行的语言，与汇编语言或高级语言