1、第六编算法初步 1.算法的含义、程序框图 （1）了解算法的含义，了解算法的思想。 （2）理解程序框图的三种基本逻辑结构：顺序程序、条件结构、循环结构。 2.基本算法语句 了解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句的含义。知识能力解读知能解读（一）算法的概念1.算法算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。2.算法的要求（1）写出的算法必须能解决一类问题。（2）要使算法尽量简单、步骤尽量少。（3）要保证算法正确，且计算机能够执行。知能解读（二）程序框图1.定义用一些通用图形个符号构成一张图来表示算法，这种图称为程序框图（简称框图或流程图）。2.常用的表示
2、算法步骤的图形符号图形符号名称功能终端框（起止框）表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框（执行框）赋值、计算判断框判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”流程线连接程序框连接点连接程序框图的两部分3.画程序框图的规则（1）使用标准的框图符号。（2）框图一般按从上到下、从左到右的方向画。（3）除判断框外，大多数框图符号只有一个进入点和一个退出点，判断框是唯一具有超过一个退出点的框图符号。（4）在图形符号内描述的语言要非常精炼、清楚。知能解读（三）算法的三种基本逻辑结构和框图表示1.顺序结构顺序结构是最简单的算法结构，它由若
3、干个依次执行的处理步骤组成，它是任何一个算法都离不开的一种算法结构，可以用如图所示的流程图表示。其中A和B两个框是依次执行的，只有在执行完A框所指定的操作后，才能接着执行B框所指定的操作。说明：顺序结构往往是从上到下的顺序，有时也有从左到右的。顺序结构常用于直接应用公式的题型。2.选择结构（条件结构）在一个算法中，经常会遇到条件的判断。算法的流程根据条件是否成立有不同的流向，这种根据条件作出判断，再决定执行哪一种操作的结构称为选择机构（条件结构）。如图所示，均为选择结构。图（1）为根据给定的条件P是否成立，而选择A框或B框，请注意无论条件P是否成立，只能执行A框或B框之一，不可能执行A框又执行
4、B框，也不可能A，B框都不执行。无论走哪一条路径，在执行完A框或B框之后，脱离本选择结构。图（2）为当条件P成立时执行A框，当条件P不成立时不执行任何操作。 说明：（1）选择结构与顺序结构的不同之处是它在执行下一语句时是有选择性的。（2）在进行条件P的判断后可以不执行操作，而直接退出选择结构。（3）选择结构在书写时要注意加上“是”或“否”，以便进行选择。（4）在条件P的判断中只能存在“是”或“否”两种答案，而不能出现“不一定”这种现象。3.循环结构需要重复执行同一操作的结构称为循环结构，即从某处开始，按照一定的条件反复执行某一处理步骤，反复执行的处理步骤称为循环体。图是一种常见的循环结构，它的
5、功能是先执行A，然后判断给定的条件P是否成立，如果条件P不成立，就继续执行A，然后再对条件P进行判断，如果条件P仍然不成立，则仍然执行A如此反复执行A，直到给定的条件P成立为止，此时不再执行A，脱离本循环结构。另外，图所示的框图也是常见的一种循环结构，它的功能是先判断条件P是否成立，如果条件P成立，则执行A，然后再对条件P进行判断，如果条件P仍然成立，则仍然执行A如此反复执行A，直到条件P不成立为止，此时不再执行A，脱离本循环结构。说明：（1）理解两种常见的循环结构，即直到型（UNTIL型）循环和当型（WHILE型）循环以及它们之间的相互转换。 （2）在理解循环体内部循环的含义及作用时，要知道
6、循环体的循环次数或循环条件以及什么时候循环结束。（3）在加条件P时，一定要注意经有限次循环后能使循环结束，否则，将出现死循环，即一个错误的循环结构。4.三种基本结构的共同特点（1）只有一个入口。（2）只有一个出口。请注意一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形判断框的出口和选择结构的出口混为一谈。（3）结构内的每一部分都有机会被执行到，也就是说对每一个框来说都应当有一条从入口到出口的路径通过它。像图的处理框没有一条从入口到出口的路径通过它，就是不符合要求的流程图。 （4）结构内不存在死循环，即无终止的循环。像图就是一个死循环。在流程图中是不允许有死循环出现的。三种基本结
7、构的这些共同特点，也是检查一个流程图或算法是否正确、合理的方法和试金石。知能解读（四）基本算法语句1.赋值语句赋值语句就是将表达式所代表的值赋给变量的语句，其格式为“变量=表达式”（或“变量表达式”），用符号“=”（或“”）表示，“x=y”（或“xy”）表示将y的值赋给x，其中x是一个变量，y是一个与x同类型的变量或表达式。（注：不同版本的算法语句略有不同）说明：（1）左边只能是变量，而不能是表达式，例如3=m（或3m）是错误的。赋值语句右边表达式可以是一个常量、变量或含变量的运算式。（2）赋值号左右不能兑换，赋值语句是将赋值号右边的表达式的值赋给左边的变量，例如y=x（或yx），表示用x的值
8、替代变量y原先的取值，不能改写为x=y（或xy），因为后者表示用y的值替代变量x原先的取值。（3）不能用赋值语句进行代数式的演算（如化简、分解因式等），如是不能实现的。在一个赋值语句中只能给一个变量赋值，不能出现两个或多个“=”。（4）赋值号与数学计算中的等号的意义不同。赋值号左边的变量如果原来没有值，则在执行赋值语句后，获得一个值；如果原来已有值，则执行该语句后，以赋值号右边表达式的值替代该变量的原值，即将原值“冲掉”。如N=N+1在数学计算中是不成立的，但在赋值语句中，意思是将N的原值加1再赋给N，即N的值加1。2.输入、输出语句输入、输出语句是分别用来实现算法的输入信息、输出结果的功能的
9、语句。输入语句格式“INPUT a，b”（或“Reada，b”）表示输入的数据依次赋给a，b。输出语句格式“PRINT x”（或“Printx”）表示输出运算结果x。“PRINT x，y”（或“Printx，y”）表示依次输出运算结果x，y。（1）输入语句还可以表示为“INPUT“提示内容”；变量”；（2）输入语句中的变量表示的只能是具体的常数，不能是函数、变量或表达式；（3）输出语句PRINT（或Print）可以输出常量、变量或表达式的值。3.条件语句在处理选择结构的算法中，运用条件语句来实现。条件语句的一般格式如下：说明：（1）在执行这种格式的条件语句时，若表达式（即条件）为真，则执行“T
10、HEN分支”，若表达式为假，则执行“ELSE分支”，然后结束这一条件语句。其对应的程序框图如图。 （2）在执行这种格式的条件语句时，只对表达式的结果进行判断，若表达式为真，则执行“THEN分支”，否则跳过“THEN分支”执行下一语句，其对应的程序框图如图。（3）在这种格式的条件语句中，“THEN分支”与“ELSE分支”执行且只执行其中一个分支。（4）“THEN分支”与“ELSE分支”语句一般在前面加空格以便阅读。（5）条件语句主要用来实现算法中的条件结构，如判断一个数的正负、比较两数的大小、对一组数据进行排序等就需要用到条件语句。4.循环语句用来实现循环结构的语句。（1）WHILE语句的一般格
11、式（2）For语句的一般格式（苏教版）（3）UNTIL语句一般格式说明：（1）当程序执行时，遇到WHILE语句，先判断条件是否成立，若成立，则执行WHILE和WEND之间的循环体，然后再判断上述条件，再次执行循环体，这个过程反复执行，直到某一次不符合条件为止，这时不再执行循环体，将跳到WEND语句后，执行WEND后面的语句。（2）当程序执行时，遇到For语句，首先把初值赋给循环变量，记下终值和步长，并比较初值和终值，若初值没有超过终值，就开始执行For后面的语句，执行到End For语句时，计算机让循环变量增加一个步长值，然后用增值后的循环变量值与终值比较，如果超过终值，就执行End For后
12、面的语句，否则执行For后面的语句。（3）循环变量是用于控制算法中循环次数的变量，起计数作用。初值和终值，是循环开始和结束时循环变量的值，步长是指循环变量每次增加的值。步长为1时可以省略不写，但为其他值时，必须写，不能省略。（4）当计算机遇到UNTIL语句时，先执行一次DO和UNTIL之间的循环体，再对UNTIL后的条件进行判断。如果条件不符合，继续执行循环体，然后再检查上述条件，如果条件仍不符合，再次执行循环体，直到条件符合时为止。这时，计算机将不再执行循环体，执行UNTIL语句之后的语句。（5）循环语句主要用来处理算法中的循环结构，在处理一些有规律的计算问题，如果加求和、累乘求积等问题时，
13、常常用循环语句编写程序。（6）用For循环编写程序时要注意设定好循环变量的初值、步长和终值，避免出现多一次循环或少一次循环的情况；用WHILE循环编写程序时，一定要注意表达式的写法，当表达式为真时执行循环体，表达式为假时结束循环；UNTIL语句是先执行循环体，再判断条件，因此在任何一个UNTIL语句中，循环体至少要执行一次。简单地讲，“WHILE”符合就循环，“UNTIL”符合就停止。知能解读（五）辗转相除法与更相减损术辗转相除法与更相减损术都是求两数最大公约数的方法。说明：（1）用辗转相除法求a，b的最大公约数的步骤：用较大的数a除以较小的数b得到一个商和一个余数。若，则b为a，b的最大公约
14、数；若，则用除数b除以余数得到一个商和一个余数。若，则为a，b的最大公约数；，则用除以余数得到一个商和一个余数。如此下去，直至余数，则为a，b的最大公约数。（2）用更相减损术求两个数的最大公约数的步骤：所谓更相减损术就是用两个数中较大的数减去较小的数，用差和较小的数构成新的一对数。对于这一对数，再用大数减去小数。用同样的方法一直做下去，直到得到两个相等的数，这个数就是最大公约数。在九章算术中记载了用更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译为：任意给定两个正数，判断它们是否都是偶数。若是，用2约简；若不是，执行第步。用较
15、大的数减去较小的数，接着把较小的数与所得的差比较，并用大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。（3）辗转相除法与更相减损术之间的关系。辗转相除法与更相减损术都是求最大公约数的方法。在计算上，辗转相除法以除法为主，更相减损术以减法为主；在计算次数上，辗转相除法计算次数相对较少，特别是当两个数字大小差别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除法是以相除余数为0而得到结果的，而更相减损术则是以减数与差相等而得到结果的。辗转相除法的理论依据是：由得a，b与b，r有相同的公约数；更相减损术的理论依据是：由得a，b与b，
16、r有相同的公约数。知能解读（六）秦九韶算法和进位制1.应用秦九韶算法完成一般多项式的求值问题。求多项式的值时，首先计算最内层括号内一次多项式的值，即，然后由内向外逐层计算一次多项式的值，即，这样，把n次多项式的求值问题转化成求n个一次多项式值的问题。2.进位制是一种计数方式，用有限的数字在不同的位置表示不同的数值，可使用数学符号的个数称为基数，基数为n，即可称n进位制，简称n进制，现在最常用的是十进制，通常使用10个阿拉伯数字09进行记数，对于任何一个数，我们可以用不同的进位制来表示，比如：十进制数57，可以用二进制表示为111001，也可以用八进制表示为71，它们所代表的数值都是一样的。一般
17、地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为：。而表示各种进位制数一般在数字右下方加注来表示，如111001（2）表示二进制数，34（5）表示五进制数。R进制转化成十进制的方法：数码乘以相应权之和。如：，。十进制数转化成r进制数的方法：连续除以基，直至商为0，从低到高记录余数。如：把十进制数159转换成八进制数。知能解读（六）秦九韶算法和进位制思想方法（一）转化思想程序框图与程序是描述算法的两种重要语言，熟练地进行二者的互化，是灵活描述某一算法的基础。思想方法（二）递归法递归法是数学中非常重要的方法，比如数列中的累加、累乘、递推公式等都是常见的递归。在算法中，我们可通过赋值语
18、句和循环语句来实现递归。规律技巧（二）画流程图，写伪代码（苏教版）1.利用顺序结构绘制算法流程图，利用赋值、输入、输出语句书写伪代码当所需解决的问题较为简单，只要依次进行多个处理就能完成时，通过顺序结构来绘制算法流程图，用赋值、输入、输出语句来书写伪代码。2.利用选择结构绘制算法流程图，利用条件语句书写伪代码解决问题的过程中，必须先根据条件作出判断，再决定执行哪一种操作，画流程图时必须通过选择结构实现，写伪代码时也必须用条件语句描述。3.利用循环结构绘制算法流程图，利用循环语句书写伪代码当需要解决的问题需要多次重复相同的步骤时，要实现算法必须通过循环结构来实现，伪代码的书写也必须用循环语句来描
19、述。高考命题研究程序框图是高考必考知识点，以选择题、填空题的形式出现，主要考查循环结构程序框图。其中读出程序框图的功能，求出输出结果，根据题目条件补充判断框内的条件是高考热点。有时还会与分段函数求值、数列求和或求积、统计与概率等知识综合考查，难度不大。高考热点（一）基本算法语句计算机程序设计语言包含以下五个基本算法语句：输入语句、输出语句、赋值语句、条件语句、循环语句，它们与算法的三种基本结构式相互对应的。其中条件语句、循环语句是重点考查的内容，常以选择题、填空题的形式考查，重在考查对算法语句的理解和应用。高考热点（二）程序框图程序框图是高考新课程标准的新增内容，主要以客观题出现，考查最多的是循环结构。算法和程序框图常见的题型有两种：一种是阅读程序框图，写出执行结果；另一种是填写程序框图的空白部分。高考热点（三）算法与其他知识结合在知识交汇处命题是高考命题的一个原则，算法作为新增内容，它与其他知识的结合也是高考热点，它常与函数、数列、统计、概率等结合在一起考查。附录常用公式定理常用符号图形符号名称终端框（起止框）输入、输出框处理框（执行框）判断框流程线连接点
