当前位置:首页 >> 其它课程 >> 算法与程序设计(高中选修)复习资料

算法与程序设计(高中选修)复习资料


主题一 利用计算机解决问题的基本过程 点击考点
1、了解利用计算机解决问题的基本过程 2、了解问题分析与算法设计之间的关系 3、了解算法的基本特征 4、能用自然语言、流程图或伪代码描述算法 5、了解程序设计语言产生与发展过程

考点注解
1、了解利用计算机解决问题的基本过程

一般来说,用计算机解决一个具体问题时,大致经

过以下几个步骤:首先要从具体问 题抽象出一个适当的数学模型, 然后设计一个解此数学模型的算法, 最后编出程序进行测试 调整直道到最终解答。寻求数学模型的实质就是分析问题,从中提取操作的对象,并找出这 些操作对象之间含有的关系,然后用数学的语言加以描述。 2、了解问题分析与算法设计之间的关系 任何一个问题必须弄清楚其内容、性质、规模,才能找到解决问题的方法,所以分析问 题就是要确定用计算机做什么,接下来,就解决怎么做的问题,也就是算法。 算法就是解决问题的方法与步骤。有了算法才能转化成指令代码,计算机才能按照指令 代码一步一步去执行,直到得到问题的解。 算法是程序设计的灵魂,算法独立于任何一种程序设计语言,一个算法可以用多种程序 设计语言来实现。 一个问题,可能有多种算法 ,应该通过分析、比较、挑选一种最优的算法。一个好算 法必须用到科学的方法 ,应该好好学习各学科处理问题的科学方法。 3、了解算法的基本特征 一个算法应该具有以下特征: 1)有穷性:一个算法必须保证它的执行步骤是有限的,即它是能终止的。 2)确定性:算法中的每一个步骤必须有确切的含义,而不应当是模糊的,模棱两可的。 3)可行性:算法的每一步原则上都能精确运行 4)有零个或多个输入:所谓输入是指算法在执行时需要从外界获得数据,其目的是为算 法建立某些初始状态。 如果建立初始状态所需的数据已经包含在算法中了, 那就不再需要输 入了。 5)有一个或多个输出:算法的目的是用来求解问题的,问题求解的结果应以一定的形式 输出。 4、能用自然语言、流程图或伪代码描述算法 一个算法可以用多种不同的方法来描述。一般用自然语言、流程图、伪代码描述。 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 这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更 加直观. 5、了解程序设计语言产生与发展过程 程序设计语言泛指一切用于书写计算机程序的语言。 计算机语言的发展经历了从机器语言、汇编语言到高级语言的历程,如图1-1所示。

1) 机器语言(Machine Language)

计算机使用的是由“0”和“1”组成的二进制数, 二进制编码方式是计算机语言的基础。 计 算机发明之初, 科学家只能用二进制数编制的指令控制计算机运行。 每一条计算机指令均由 一组“0”、“1”数字,按一定的规则排列组成,若要计算机执行一项简单的任务,需要编 写大量的这种指令。 这种有规则的二进制数组成的指令集, 就是机器语言 (也称为指令系统) 。 不同系列的 CPU,具有不同的机器语言,如目前个人计算机中常用 AMD 公司的系列 CPU 和 Intel 公司的系列 CPU,具有不同的机器语言。 机器语言是计算机唯一能识别并直接执行的语言, 与汇编语言或高级语言相比, 其执行效率 高。但其可读性差,不易记忆;编写程序既难又繁,容易出错;程序调试和修改难度巨大, 不容易掌握和使用。此外,因为机器语言直接依赖于中央处理器,所以用某种机器语言编写 的程序只能在相应的计算机上执行,无法在其他型号的计算机上执行,也就是说,可移植性 差。 2)汇编语言(Assemble Language) 为了减轻使用机器语言编程的痛苦,20世纪50年代初,出现了汇编语言。汇编语言用比较容 易识别、记忆的助记符替代特定的二进制串。下面是几条 Intel80x86的汇编指令:ADD AX , BX ;表示将寄存器 AX 和 BX 中的内容相加,结果保存在寄存器 AX 中。 SUB AX , NUM ;表示将寄存器 AX 中的内容减去 NUM,结果保存在寄存器 AX 中。 MOV AX , NUM ;表示把数 NUM 保存在寄存器 AX 中。 通过这种助记符,人们就能较容易地读懂程序,调试和维护也更方便了。但这些助记符号计 算机无法识别,需要一个专门的程序将其翻译成机器语言,这种翻译程序被称为汇编程序。 汇编语言的一条汇编指令对应一条机器指令, 与机器语言性质上是一样的, 只是表示方式做 了改进,其可移植性与机器语言一样不好。总之,汇编语言是符号化的机器语言,执行效率 仍接近于机器语言,因此,汇编语言至今仍是一种常用的软件开发工具。 3) 高级语言 尽管汇编语言比机器语言方便, 但汇编语言仍然具有许多不便之处, 程序编写的效率远远不 能满足需要。1954年,第一个高级语言—FORTRAN 问世了。高级语言是一种用能表达各种意 义的“词”和“数学公式”按一定的“语法规则”编写程序的语言, 也称为高级程序设计语 言或算法语言。半个多世纪以来,有几百种高级语言问世,影响较大、使用较普遍的有 FORTRAN、A LGOL、COBOL、BASIC、LISP、SNOBOL、PL/1、Pascal、C、PROLOG、Ada、C++、 Visual C++、Visual Basic 、Delphi、Java 等。高级语言的发展也经历了从早期语言到结 构化程序设计语言、面向对象程序设计语言的过程。 高级语言与自然语言和数学表达式相当接近,不依赖于计算机型号,通用性较好。高级语言 的使用,大大提高了程序编写的效率和程序的可读性。 与汇编语言一样, 计算机无法直接识别和执行高级语言, 必须翻译成等价的机器语言程序 (称 为目标程序)才能执行,如图1-2所示。高级语言源程序翻译成机器语言程序的方法有“解 释”和“编译”两种。解释方法采用边解释边执行的方法,如早期的 BASIC 语言即采用解

释方法,在执行 BASIC 源程序时,解释一条 BASIC 语句,执行一条语句。编译方法采用相 应语言的编译程序, 先把源程序编译成指定机型的机器语言目标程序, 然后再把目标程序和 各种标准库函数连接装配成完整的目标程序,在相应的机型上执行。如 C、C++、Visual C++ 及 Visual Basic 等均采用编译的方法。编译方法比解释方法更具有效率。

同步集训
一、选择题 1、人们利用计算机解决问题的基本过程一般有如下五个步骤(①~⑤) ,请按各步骤的先后 顺序在下列选项(A~D)中选择正确的答案( ) ①调试运行程序 ②分析问题 ③设计算法 ④问题解决 ⑤编写程序 A、①②③④⑤ B、②④③⑤①C、④②③⑤① D、②③⑤①④ 2、在下图中利用计算机解决问题的基本步骤流程图中,对于标注为(1)的流程线,以下说 明正确的是( )

A.该流程线可有可无 B.当程序运行不出结果时,才需要该部分流程线 C.该部分流程线保证了问题解决的正确性 D.该部分流程线有错 3、下列三种算法的描述,缺乏直观性、简洁性,最容易产生歧义的是( ) A、自然语言描述法 B、流程图 C、伪代码 4、流程图中表示判断的是( ) A、矩形框 B、菱形框 C、圆形框 D、椭圆形框 5、 “分支判断”作为解决问题的算法的一个基本步骤,正是体现了计算机的( A、算术运算能力 B、逻辑运算能力 C、分布式运算能力 D、记忆存储能力

)能力。

6、下面关于算法的描述,正确的是( ) A、算法不可以用自然语言描述 B、算法只能用框图来描述 C、一个算法必须保证它的执行步骤是有限的 D、算法的框图表示法有 0 个或多个输入,但只能有一个输出 7、下面关于算法的描述,正确的是( ) A、一个问题只有一个算法 B、一个问题可能有多种算法 C、能解决问题的算法都是好算法,没优劣之分 D、算法不是程序设计所必需的 8、下列关于算法的叙述,正确的是( ) A、解决一个问题的算法只有一种 B、有穷性是算法的基本特征之一 C、可行性不属于算法基本特征 D、算法对程序设计没有任何作用 9、下列关于算法的叙述,正确的是( ) A、解决一个问题的算法只有一种 B、算法必定有一个或一个以上的输出 C、算法中可以存在不确切的步骤 D、描述算法的步骤可以是无穷的 10、从以下计算 S 的算法可以看出,S 的代数式表示是( ①变量 S 的初值是 0; ②变量 I 从 1 起循环到 N; ③循环表达式为 S=S+(-1)*i; ④输出变量 S 的值 A.1-2+3-4+…+(-1)N*(N-1) B.1-2+3-4+…+(-1)N-1*n C.1+2+3+4+…+(n-1)+n D.-1-2-3-4-…-(n-1)-n 11、下列选项都是属于高级语言的是( ) A、汇编语言 机器语言 B、Basic 语言 Pascal 语言 C、汇编语言 Basic 语言 D、机器语言 Pascal 语言 12、下列选项都是属于低级语言的是( ) A、汇编语言 机器语言 B、Basic 语言 Pascal 语言 C、汇编语言 Basic 语言 D、机器语言 Pascal 语言 13、________是计算机能直接识别,理解执行的语言。 A、汇编语言 B、Pascal 语言 C、Basic 语言 D、机器语言 14、下列关于程序设计言中机器语言的说法,正确的是( A、Visual Basic 属于机器语言的一种





B、机器语言就是 Visual Basic C、机器语言比高级语言更早出现 D、高级语言比机器语言更早出现 15、下列选项中,最先出现的程序设计语言是( ) A、汇编语言 B、高级语言 C、Visual Basic D、机器语言 16、不能被计算机直接识别,理解执行的语言需要转换,这种转换是( ) A、人工转换或机器转换 B、计算机语言提供的解释器或编译器负责转换 C、操作系统负责转换 D、人工智能技术中的自然语言理解 二、简答题 1、简述什么是计算机程序、程序设计、程序设计语言、算法 2、简述算法的特征。 3、简述程序设计语言的发展历程 4、高级语言编制的源程序计算机无法直接识别,必须经过转换才能被计算机执行。请问有 哪些转换方式,这些方式有什么区别? 三、阅读流程图,写出其处理的任务问题 1、 该流程图处理的任务是: 开始 输入正整数 n 赋初值 s=0 i=1 s=s+i 开始 i=i+1 否 i>n 吗 是 输入正整数 n 赋初值 s=0 i=1 s=s+i i=i+1 否 i>n 吗 是

备注:x mod y 是 x 除 y 的余数, 如 10 mod 4 余数是 2 2、该流程图处理的任务是:

输出 s 的值 结束

输出 s 的值 四、用 流程图 表示如下问题的算法,由键盘输入两个 结束

整数 a 、 b,输出其中较大的数。 主题一 利用计算机解决问题的基本过程 同步集训答案 一选择题: 1、D 2、C 3、A4、B5、B6、C7、B8、B9、B10、D11、B 12、A13、D14、C15、D16、B 6、简答题 1、计算机程序就是指计算机如何去解决问题或完成任务的一组机器操作的指令或语句 的序列,是算法的一种描述,简称程序。 程序设计就是寻求解决问题的方法, 并将其实现步骤编写成计算机可以执行的程序的过 程。 程序设计语言泛指一切用于书写计算机程序的语言。 算法就是解决问题的方法和步骤。 2、一个算法应该具有以下特征: 1)有穷性:一个算法必须保证它的执行步骤是有限的,即它是能终止的。 2)确定性:算法中的每一个步骤必须有确切的含义,而不应当是模糊的,模棱两可 的。 3)可行性:算法的每一步原则上都能精确运行 4)有零个或多个输入:所谓输入是指算法在执行时需要从外界获得数据,其目的是 为算法建立某些初始状态。 如果建立初始状态所需的数据已经包含在算法中了, 那就不再需 要输入了。 5)有一个或多个输出:算法的目的是用来求解问题的,问题求解的结果应以一定的 形式输出。 3、计算机语言的发展经历了从机器语言、汇编语言到高级语言的历程 4、高级语言源程序翻译成机器语言程序的方法有“解释”和“编译”两种。解释方法采用 边解释边执行的方法,如早期的 BASIC 语言即采用解释方法,在执行 BASIC 源程序时, 解释一条 BASIC 语句,执行一条语句。编译方法采用相应语言的编译程序,先把源程序编 译成指定机型的机器语言目标程序, 然后再把目标程序和各种标准库函数连接装配成完整的 目标程序,在相应的机型上执行。如 C、C++、Visual C++及 Visual Basic 等均采用编译的方 法。编译方法比解释方法更具有效率。 三、阅读流程图,写出其处理的任务问题 1、该流程图处理的任务是:输入两个数 a 和 b,求出它们的最大公约数并输出。 2、该流程图处理的任务是:输入一个数 n,计算并输出 1 到 n 的和 四、用流程图表示如下问题的算法 主题二 程序设计基础 点击考点 1、 能 够 使 用 可 视 化 程序开发工具设计简单的用 户界面。 2、 知 道 常 用 的 数 据 类型、变量、常量的含义; 学会定义常量、变量的数据

类型。 3、 知道程序中运算符、函数、表达式的表示方式,能够转换数学表达式为程序接 受的表达式。 4、 学会使用顺序结构设计程序的基本方法。 5、 学会使用选择结构设计程序的基本方法。 6、 学会使用循环结构设计程序的基本方法。 7、 了解程序的编辑与翻译过程方法,比较编译型语言与解释型语言的优势与不 足。 考点注解 7、能够使用可视化程序开发工具设计简单的用户界面。 Visual Basic 是可视化程序设计语言。可视化程序让程序设计人员利用软件提供的各种 控件,像搭积木式地构造应用程序的各种界面。VB 的集成开发环境如下:

面向对象的程序设计以对象为中心,以事件为过程执行起点。 在可视化程序开发环境中,文本框、标签、命令按钮等控件都叫对象。 对象的特征称为对象的属性。 在对象上发生的事情称为事件,常用的有单击(click),双击(dblclick),加载(load),按键 (keypress)等 对象能够执行的操作叫方法。如 form1.cls 的作用是清除窗体 form1 中的内容。 8、知道常用的数据类型、变量、常量的含义;学会定义常量、变量的数据类型。 数据是程序处理的对象, 不同类型的数据有不同的处理方法。 数据可以依照类型进行分 类。 数据类型用于确定一个变量所具有的值在计算机内的存储方式, 以及对变量可以进行何 种操作。 VB 语言的数据类型比较丰富,此外还可以通过数据类型定义语句在基本数据类 型的基础上定义新的数据类型(自定义数据类型) 。 VB 数据类型

常量 在程序执行过程中,其值不能改变的量称为常量。常量可以直接用一个数来表示,称为 常数(或称为直接常量) ,也可以用一个符号来表示,称为符号常量。 1)直接常量(常数) 各种数据类型都有其常量表示,如表所示。

2)符号常量 常量在程序中也可用符号表示。 符号常量的定义格式如下: [访问权限] Const <常量名> [As 数据类型]=<数值> 如: Const PI As Single =3.1416 表示定义 PI 为符号常量,代表单精度型数值 3.1416。 变量

在程序执行过程中,其值可以改变的量称为变量。 1)变量的命名规则 ( 1)变量名首字符必须是字母; ( 2)变量名只能由字母、数字和下划线组成; ( 3)变量名不能使用 VB 中的关键字(保留字) ; ( 4)变量名在同一个作用域内必须唯一; ( 5)变量名长度不超过 255; ( 6)变量的命名最好还应遵守一定的编程约定。 2)变量的作用域 变量的作用域是指变量的有效范围,根据变量说明方式的不同,变量有三个作用域,见表

3)变量定义语句 ( 1)定义模块或过程局部变量 Dim <变量名> As <类型> [, <变量名> As <类型>]… ( 2)定义全局变量 Public <变量名> As <类型> [, <变量名> As <类型>]… 9、知道程序中运算符、函数、表达式的表示方式,能够转换数学表达式为程序接受的 表达式。 运算符 是在代码中对各种数据进行运算的符号。例如,有进行加、减、乘、除算术运 算的运算符,有进行与、或、非、异或逻辑运算的运算符。 表达式 是由运算符和运算对象及圆括号组成的一个序列,它是由常量、变量、函数等 用运算符连接而成的式子。表达式是构成程序代码的最基本要素。 1)赋值运算符 赋值语句的语法格式为: <变量名> = <表达式> 例如:Count=5。 2)算术运算符与算术表达式 ( 1)算术运算符 VB 中算术运算符有+(加) 、-(减) 、*(乘) 、/(除) 、\(整除) 、mod(模运算,求余 数)和^(幂) 。 ( 2)算术运算符及优先级:^(乘方)→*、/→\(整除)→mod(取余)→+、- ( 3)算术表达式:用算术运算符和括号将运算对象连接起来的式子称为算术表达式。 运算运算对象可以是常量、变量或函数等。例如: Dim a As Integer,x As Single a=5 x = a ^ 2 * a - 1.5 + a \ 2 + a Mod 2 运算结果为 X=5^ 2*5-1.5+5\2+5 mod 2 =125-1.5+2+1=126.5 3)字符串运算符 VB 中的字符串运算符主要用来将两个字符串连接成一个字符串。VB 提供了两个字符串运 算符:“&”和“+