高中算法初步

1、109004 算法初步【考纲要求】1了解算法的含义，了解算法的思想2理解算法框图的三种基本结构：顺序结构、选择结构、循环结构【把脉考情】 从近两年的高考试题来看，循环结构与条件结构是考查的热点，题型以选择、填空题为主，属容易题 本节内容常考的类型有：功能判断型、结果输出型、判断条件型，同时注意算法思想的应用，预测2012年仍为考查的热点【要点梳理】一、算法的概念1算法的定义：是指按照一定规则解决某一类问题的明确和有限的步骤2算法的特征:(1)概括性：写出的算法必须能解决某一类问题，并且能够重复使用(2)逻辑性：算法从初始步骤开始，分为若干明确的步骤，前一步是后一步的前提，只有执行完前一步才能进

2、行下一步，而且每一步都是正确无误的，从而组成了一个有着很强逻辑性的步骤序列(3)有穷性：算法有一个清晰的起始步，终止步是表示问题得到解答或指出问题没有解答，所有序列必须在有限个步骤之内完成，不能无停止地执行下去(4)不唯一性：求解某一个问题的算法不一定只有唯一的一个，可以有不同的算法，当然这些算法有简繁之分、优劣之别(5)普遍性：很多具体的问题，都可以设计合理的算法去解决二、程序框图1程序框图基本概念：（一）程序构图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。一个程序框图包括以下几部分：表示相应操作的程序框；带箭头的流程线；程序框外必要文字说明

3、。（二）构成程序框的图形符号及其作用程序框名称功能终端框（起止框）表示一个算法的起始和结束，是任何流程图不可少的。输入、输出框表示一个算法输入和输出的信息，可用在算法中任何需要输入、输出的位置。处理框（执行框）赋值、计算，算法中处理数据需要的算式、公式等分别写在不同的用以处理数据的处理框内。判断框判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”。流程线连接程序框，连接点连接程序框图的两部分学习这部分知识的时候，要掌握各个图形的形状、作用及使用规则，画程序框图的规则如下：（1）使用标准的图形符号。（2）框图一般按从上到下、从左到右的方向画。（3）除判断框外，大多

4、数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果。（5）在图形符号内描述的语言要非常简练清楚。（三）算法的三种基本逻辑结构：顺序结构、条件结构、循环结构。AB（1）顺序结构：顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的，它是由若干个依次执行的处理步骤组成的，它是任何一个算法都离不开的一种基本算法结构。顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤。如在示意图中，A框和B框是依次执

5、行的，只有在执行完A框指定的操作后，才能接着执行B框所指定的操作。（2）条件结构：条件结构是指在算法中通过对条件的判断根据条件是否成立而选择不同流向的算法结构。条件P是否成立而选择执行A框或B框。无论P条件是否成立，只能执行A框或B框之一，不可能同时执行A框和B框，也不可能A框、B框都不执行。一个判断结构可以有多个判断框。 条件结构的典型问题就是分段函数的求值问题及有关分类的其他问题 在程序框图设计中，程序的流向要多次根据判断做出选择时，一般要用到条件结构的“嵌套”所谓条件结构的“嵌套”，就是在条件结构的一支(或两支)内的步骤中又要用到条件结构这类问题一般比较复杂，设计时要注意每一个处理框执行

6、时对应的条件（3）循环结构：在一些算法中，经常会出现从某处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构，反复执行的处理步骤为循环体，显然，循环结构中一定包含条件结构。循环结构又称重复结构，循环结构可细分为两类：一类是当型循环结构，如下左图所示，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，再判断条件P是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次条件P不成立为止，此时不再执行A框，离开循环结构。不成立P成立A另一类是直到型循环结构，如下右图所示，它的功能是先执行，然后判断给定的条件P是否成立，如果P仍然不成立，则继续执行A框，直到某一次给定的条件

7、P成立为止，此时不再执行A框，离开循环结构。A成立不成立P当型循环结构 直到型循环结构注意：1循环结构要在某个条件下终止循环，这就需要条件结构来判断。因此，循环结构中一定包含条件结构，但不允许“死循环”。2在循环结构中都有一个计数变量和累加变量。计数变量用于记录循环次数，累加变量用于输出结果。计数变量和累加变量一般是同步执行的，累加一次，计数一次。顺序结构条件结构循环结构定义由若干个依次执行的步骤组成的，这是任何一个算法都离不开的基本结构算法的流程根据条件是否成立有不同的流向，条件结构就是处理这种过程的结构从某处开始，按照一定的条件反复执行某些步骤的情况，反复执行的步骤称为循环体程序框图 直到

8、型 当型究疑点三种基本逻辑结构的共同点是什么？提示：三种逻辑结构的共同点即只有一个入口和一个出口，每一个基本逻辑结构的每一部分都有机会被执行到，而且结构内不存在死循环三、程序语言1输入语句（1）输入语句的一般格式：.（2）输入语句与程序框图中的输入框对应，作用是实现算法的输入信息功能；（3）“提示内容”提示用户输入什么样的信息，变量是指程序在运行时其值是可以变化的量；（4）输入语句要求输入的值只能是具体的常数，不能是函数、变量或表达式；（5）提示内容与变量之间用分号“；”隔开，若输入多个变量，变量与变量之间用逗号“，”隔开。2输出语句（1）输出语句的一般格式：.（2）输出语句的作用是实现算法的

9、输出结果功能；（3）“提示内容”提示用户输入什么样的信息，表达式是指程序要输出的数据；（4）输出语句可以输出常量、变量或表达式的值以及字符。3赋值语句（1）赋值语句的一般格式：（2）赋值语句的作用是将表达式所代表的值赋给变量；（3）赋值语句中的“”称作赋值号，与数学中的等号的意义是不同的。赋值号的左右两边不能对换，它将赋值号右边的表达式的值赋给赋值号左边的变量；（4）赋值语句左边只能是变量名字，而不是表达式，右边表达式可以是一个数据、常量或算式；（5）对于一个变量可以多次赋值。注意：赋值号左边只能是变量名字，而不能是表达式。如：2=X是错误的。赋值号左右不能对换。如“A=B”“B=A”的含义运

10、行结果是不同的。不能利用赋值语句进行代数式的演算。（如化简、因式分解、解方程等）赋值号“=”与数学中的等号意义不同。4条件语句（1）条件语句的一般格式有两种：IFTHENELSE语句；IFTHEN语句。（2）IFTHENELSE语句IFTHENELSE语句的一般格式为图1，对应的程序框图为图2。否是满足条件？语句1语句2IF 条件 THEN语句1ELSE语句2END IF 图1 图2分析：在IFTHENELSE语句中，“条件”表示判断的条件，“语句1”表示满足条件时执行的操作内容；“语句2”表示不满足条件时执行的操作内容；END IF表示条件语句的结束。计算机在执行时，首先对IF后的条件进行判

11、断，如果条件符合，则执行THEN后面的语句1；若条件不符合，则执行ELSE后面的语句2。（3）IFTHEN语句满足条件？语句是否（图4）IFTHEN语句的一般格式为图3，对应的程序框图为图4。IF 条件 THEN语句END IF（图3） 补充：条件语句嵌套的形式在有些复杂的算法中，有时需要按条件执行的某一语句继续按照另一个要求进行判断，这时可以再利用一个条件语句进行判断，这就形成了条件语句的嵌套(1)一般形式：(2)在编写条件语句的嵌套中的“条件”时，要注意“If”与“End If”的配对，有时可以利用文字的缩进来表示嵌套的层次，以帮助对程序的阅读和理解(3)对于条件语句的嵌套，一定要分清内层

12、条件语句和外层条件语句，内层的条件结构是外层的条件结构的一个分支(4)当条件结构的嵌套中的“条件”是并列的，则为条件语句的叠加5循环语句循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（WHILE型）和直到型（UNTIL型）两种语句结构。即WHILE语句和UNTIL语句。（1）WHILE语句满足条件？循环体否是WHILE语句的一般格式是 对应的程序框图是WHILE 条件循环体WEND当计算机遇到WHILE语句时，先判断条件的真假，如果条件符合，就执行WHILE与WEND之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直

13、到某一次条件不符合为止。这时，计算机将不执行循环体，直接跳到WEND语句后，接着执行WEND之后的语句。因此，当型循环有时也称为“前测试型”循环。（2）UNTIL语句满足条件？循环体是否UNTIL语句的一般格式是 对应的程序框图是DO循环体LOOP UNTIL 条件直到型循环又称为“后测试型”循环，从UNTIL型循环结构分析，计算机执行该语句时，先执行一次循环体，然后进行条件的判断，如果条件不满足，继续返回执行循环体，然后再进行条件的判断，这个过程反复进行，直到某一次条件满足时，不再执行循环体，跳到LOOP UNTIL语句后执行其他语句，是先执行循环体后进行条件判断的循环语句。 分析：当型循环

14、与直到型循环的区别与联系：(1)联系：两种语句都可以实现计算机反复执行循环体的目的，只是表达形式不同；一般来讲，While语句与Until语句可以相互转化(2)区别：计算机执行的顺序不同：While先条件，Until先循环条件的内容不同：While满足就循环，Until满足就停止对循环体的执行次数不同：在While语句中，循环体可以一次不执行就退出循环结构；而在任何Until语句中，循环体至少要执行一次应用循环语句编写程序应注意的几个问题：(1)循环语句中的变量，一般需要进行一定的初始化操作(2)循环语句在循环的过程中需要有“结束”的语句，程序中最忌“死循环”，所谓“死循环”就是指该循环条件永

15、远成立，没有跳出循环体的机会(3)在循环中要改变循环体条件的成立因素程序每执行一次循环体，循环条件中涉及的变量就会发生改变，正在步步逼近满足跳出循环体的条件 循环结构中几个常用变量： (1)计数变量：用来记录某个事件发生的次数，如ii1； (2)累加变量：用来计算数据之和，如ssi； (3)累乘变量：用来计算数据之积，如ppi. 处理循环结构的框图问题，关键是理解认清终止循环结构的条件及循环次数.补充：常用的程序符号与数学符号对照表：注：“/”表示取商运算，“Mod”表示求余运算四、算法案例1辗转相除法与更相减损术（1）辗转相除法。辗转相除法(欧几里得算法)：对于给定的两个数，用较大的数除以较

16、小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，此时的除数就是所求两数的最大公约数（2）更相减损术 更相减损术(等值算法)：对于给定的两个数，先判断它们是否都是偶数，若是，用2约简；若不是，执行后面步骤再以其中较大的数减去较小的数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行以上步骤，直到被减数与较小的数相等为止，此时相等的这个数与约简数的乘积即为所求的最大公约数 辗转相除法与更相减损术的区别：名称辗转相除法更相减损术区别以除法为主两个整数差值较大时，运算次数较少相除余数为零时得结果以减法为主两个整数差值较大时，运算次数较多相减，两数相

17、等得结果联系都是求最大公约数的方法二者的实质都是递归的过程二者都要用循环结构来实现程序求正整数a,b(ab)的最大公约数2秦九韶算法与排序（1）秦九韶算法概念：把一个多项式f(x)anxnan1xn1a1xa0改写成如下形式：f(x)anxnan1xn1a1xa0(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0.这样，求n次多项式f(x)的值就转化为求n个一次多项式的值，这就是秦九韶算法秦九韶算法的特点在于把求一个n次多项式的值转化为求n个

18、一次多项式的值，即把求f(x)anxnan1xn1a1xa0的值转化为求递推公式：(k1,2，n)这样可以最多计算n次乘法和n次加法即可得多项式的值，和直接代入多项式相比减少了乘法的运算次数(通常求多项式f(x)anxnan1xn1a1xa0的值时，计算anxn，需n次乘法；计算an1xn1，需n1次乘法共需n(n1)1次乘法，还需n次加法，总共进行n次运算)，提高了运算效率（2）两种排序方法： 直接插入排序基本思想：插入排序的思想就是读一个，排一个。将第个数放入数组的第个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置将该位置以及以后的元素向后推移一个位置，将

19、读入的新数填入空出的位置中（由于算法简单，可以举例说明） 冒泡排序基本思想：依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数.直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数. 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序. 五、进位制1概念：为了计数或运算方便而约定的记数系统，“满足k进一”就是k进制，k是基数(其中k是大于1的整数)k进制的数可以表示为一串数字连写在一起的形式为：anan1a1a0(k)(0ank,0an1，a1，a0115，k

20、4.结束循环k4.(2)若输出k2，则2x1115且2(2x1)1115，即28x57.x的取值范围是(28,57考点5补图1如果下边程序执行后输出的结果是132，那么在程序while后面的“条件”应为()BAi11 Bi11 Ci11 Di11【解析】因为输出的结果是132，即s11211，需执行2次，则在程序while后面的“条件”应为i11.2现欲求1的和(其中n的值由键盘输入)，已给出了其程序框图，请将其补序完整并设计出程序【解析】这是一个利用循环结构来解决的求和问题，故ii1，SS.程序： Ninput(“n”)；S0；i0；while inii1；SS1/(2*i-1);endPr

21、int(%io(2);S); 3某篮球队6名主力队员在最近三场比赛中投进的三分球个数如下表所示：队员i123456三分球个数a1a2a3a4a5a6下图是统计该6名队员在最近三场比赛中投进的三分球总数的程序框图，则图中判断框应填_，输出的s_.【答案】i6a1a2a6【解析】图中判断框应填i6，输出的sa1a2a6.4如图所示的程序框图运行的结果为s132，那么判断框中应填入的关于k的判断条件是_【答案】k10？(k11？)【解析】s11211132，循环执行了两次，验证后可确定k10(或k10 Bi20 Di20【答案】A7根据条件把程序框图补充完整，求1到1 000内(包括1 000)的所

22、有奇数的和，(1)处填_，(2)处填_【答案】ssiii2【解析】根据题意，此程序框图为当型结构，先判断再计算，(1)处应填ssi，(2)处应填ii2.考点8画图、编程1画出求一个数的绝对值的程序框图，只需用()DA顺序结构 B条件结构 C循环结构 D顺序结构和条件结构 解：求一个数的绝对值，需要对数的正负进行判断，所以程序框图中需用条件结构，又顺序结构是任何一个算法都离不开的基本结构故选D.2直到型循环结构的框图为()B 解：在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环故选B.4画出计算S12222332410211的值的程序框图解：如图所示

23、：3编写程序，对于输入的x值，输出相应的y值.解：4某商场实行优惠措施，若购物金额x在800元以上(含800元)打8折；若购物金额在500元以上(含500元)打9折，否则不打折请设计一个算法程序框图，要求输入购物金额x，能输出实际交款额，并写出程序 解：程序框图程序：考点9辗转相除法1.设计程序框图，用秦九韶算法求多项式的值，主要用哪种结构实现（）C A.顺序结构 B.条件结构 C.循环结构 D.条件、顺序结构2.用辗转相除法求某两个正整数的最大公约数时，已知某步为，则下一步应为（）C A. B. C. D.没有下一步即结束3.用辗转相除法求1 457与188的最大公约数为 .47考点10更相

24、减损术1.用更相减损术求576与246的最大公约数为 。6评：若两个数不全是偶数，则直接按规则作差即可，若两个数全是偶数，先用2约简，但求出约简后的两个数的最大公约数，一定要乘以约简的倍数2.用更相减损术求某两个正整数的最大公约数时，已知某步为，则下一步的运算应为（）D A. B. C. D.3.用更相减损术求294和84的最大公约数时，需要做减法的次数是（）C A.2 B.3 C.4 D.5考点11秦九韶算法1.当x2时，求多项式f(x)3x58x43x35x212x6的值解：方法1：f(x)(3x8)x3)x5)x12)x6.按照从内到外的顺序，依次计算一次多项式的值v03，v1v02832814，v2v123142325，v3v225252555，v4v321