2018高中数学专题01算法初步期中期末备考精讲新人教A版必修3

1、 第一章算法初步 定义 肓穷性 特征 确宦性 可行性 算法与程序框图 程序框图 W 三种基本谡鎖结构 顺序结构 条件结构 循环结构 算法初步 输出语句 基本算法语句 赋值语句 算法案例 釧牛语句 循环銅 知识梳理 2 、算法的概念 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤. 算法具有确定性、有效性、有限性的特征. 、程序框图 1 构成程序框图的图形符号、名称及其功能如下表： 图形符号 名称 功能 终端框（起止框） 表示一个算法的起始和结束 f / 输入、输出框 表示 个算法输入和输出的信息 处理框（执行框） 赋值、计算 判断框 判断某一条件是否成立，成立时在出口处标明 “是”或

2、“ Y”；不成立时标明“否”或“ N 1 -1 流程线 连接程序框 连接点 连接程序框图的两部分 说明：一个完整的程序框图一定会包含终端框（用于表示一个算法的开始和结束），处理框（赋值、计 算，算法中处理数据需要的算式、公式等）和流程线. 2 -算法的三种基本逻辑结构 通常一个算法只能由三种基本逻辑结构构甌这三种基本逻辑结构分别是：顺序结构、条件结构和循环 结构. 3 程序框图的画法 在用自然语言表述一个算法后， 可以画出程序框图，用顺序结构、条件结构和循环结构来表示这个算法. 这 样表示的算法清楚、简练，便于阅读和交流. 设计一个算法的程序框图通常要经过以下步骤： 第一步，用自然语言表述算法

3、步骤. 第二步，确定每一个算法步骤所包含的逻辑结构，并用相应的程序框图表示，得到该步骤的程序框图. 第三步，将所有步骤的程序框图用流程线连接起来，并加上终端框，得到表示整个算法的程序框图. 注意：流程线不要忘记画箭头，因为它是反映流程执行先后次序的，若不画出箭头，则难以判断各框的 3 执行顺序.4 四、算法案例 三、基本算法语句 1. IF-THEN 语句 2. IF-THEN-ELSE 语句 1F条件 THEN 语句3.直到型(UNTIL)语句的一般格式 JX) 循环体 LOOP UNTIL 条件 4.当型(WHILE)语句的一般格式 WHILE条件 陆环体 WHlLEiS 5 1 .辗转相

4、除法与更相减损术 辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别.两者的区别是: (1 )辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其 实质都是一个不断的递推过程. (2)辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可.而更相减损术下一次相 减前必须有一个判断大小的过程，以区别谁做被减数. 注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去 2，这时莫忘记求得的相等 两数乘以约简的数才是所求的最大公约数. 2 .秦九韶算法 秦九韶算法的实质是： 求多项式f(x)二anX“ n疋亠的值时，转化为求n个一次多

5、项式的 值，共进行n次乘法运算和n次加法运算.这种算法的运算次数较少，是多项式求值比较先进的算法. 3 .进位制 把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除 k取余 法，把十进制数转化为 k进制数.6 算法设计与一般意义上的解决问题不同，它是对一类问题的一般解法的抽象与概括，主要借助一般的 问题解决方法，又要包括此类问题的所有情形它往往是把问题的解决划分为若干个可执行的步骤，有时 甚至是重复多次，但最终都必须在有限个步骤之内完成. (1) 用数学语言描述算法解决问题的过程大体可分为三步： 第一步，明确问题的性质，分析题意. 我们将问题简单地分为数值问题

6、和非数值问题，不同类型的问题可以有针对性地采用不同的方法进行 处理. 第二步，建立问题的描述模型. 对于数值型问题，可以建立数学模型，通过数学语言来描述问题对于非数值型问题，我们可以建立 过程模型，通过过程模型来描述问题. 第三步，设计、确立算法. 对于数值型问题，我们可以采用数值分析的方法进行处理，数值分析中有许多现成的固定算法，我们 可以直接使用当然我们也可以根据问题的实际情况设计算法对于非数值型问题，根据过程模型分析算 法并进行处理，也可以选择一些成熟的办法进行处理，如排序、递推等. (2) 算法设计应注意： 与解决问题的一般方法有联系，从中提炼出算法； 将解决问题的过程分为若干个可执行

7、步骤； 引入有关的参数或变量对算法步骤加以表达； 用最简练的语言将各个步骤表达出来； 算法的执行要在有限步内完成. 7 例1已知平面直角坐标系中两点 A（_1,0） , B（3,2），写出求线段 AB的垂直平分线方程的一个算法. 【思路分析】本题考查了数值型问题的算法设计，首先明确线段 AB的垂直平分线的定义，可先由中点坐标 公式求出线段 AB的中点，然后计算直线 AB的斜率，由垂直关系求出 AB的垂直平分线的斜率，最后由点 斜式写出直线方程. 【解】算法步骤： 第一步，计算召二畫= = 得肿的中点 第二步计軒得朋的斜率. 第三步，计算k = - = -2,得宓的垂直平分线的斜率. 第四步、由

8、点斜式写出直线的垂直平分线的方程：$ $ - -1 1 = = - -2 2（工- -1 1）, ,输出 【点评】（1）数值性问题首先建立数学模型，然后将数学问题的求解过程细化过渡成算法步骤，这是通法. （2 ）注意数学问题的解法不是算法步骤. 例2设计一个算法求ai , a2, a3 , a4,氏五个不同实数中最小的数. 【思路分析】本题考查非数值型问题的算法，按照递推关系，先比较 Q与a2，令m为a1和a2中的较小者， 然后比较m与a3，令较小者为m，依次类推，得到最小数. 【解】算法步骤： 第一步，比较ai, a2的大小，若ai : a?，则令m =印；若a：印，则令m = a?. 第二

9、步，比较 m , a3的大小，若a3：m,则令m=a3;否则m值不变. 第三步，比较 m , a4的大小，若a4 : m，则令m =玄4 ;否则m值不变. 第四步，比较 m , as的大小，若a5 : m,则令m=as;否则m值不变. 第五步，输出m. 【点评】任给有限个数，求有限个数中的最大数（最小数） ，在所给数不是很多的情况下，可设第一个数为 最大数（最小数），然后和第二个数比较，取出这两个数中的较大者（较小者）再与第三个数比较，一直进 行下去，直到与最后一个数比较完毕.这样就可以得到答案. 8 1程序框图是用规定的图形和流程线来准确、直观、形象地表示算法的图形. 2算法的设计是画程序框

10、图的基础，我们通过对问题的分析，写出相应的算法步骤，画程序框图之前 应先对算法问题设计的合法性和合理性进行探讨，然后分析算法的逻辑结构和各步骤的功能（输入、输出、 判断、赋值和计算），画出相应的程序框图，如果设计的程序框图较为复杂就采取“逐步求精”的思想设计 框图，先将问题中的简单部分明确出来，再逐步对复杂部分进行细化，然后一步一步逐步向前推进，设计 出程序框图. 例1某商场进行优惠促销：若购物金额 x在500元以上，打8折；若购物金额x在300元以上，打9折; 否则，不打折，设计算法和程序框图，要求输入购物金额为 x，即能输出实际交款额. 【思路分析】 本题考查了条件结构的程序框图， 关键是

11、由题意列出实际交款额 y与购物金额x之间的函数关 x x, 300, 系式 y = 0.9x 300 : x, 500, I 0.8x x 500, 它需要对x进行三次判断， 算法含有两个条件结构. 【解】算法步骤：第一步，输入购物金额 x 第二步，判断x, 300是否成立，若成立，则 y二x ;否则，执行第三步. 第三步，判断x, 500是否成立，若成立，则 y=0.9x ;否则，y = 0.8x 第四步，输出y，结束算法. 程序框图： 9 /输岀y/ 【点评】画程序框图的关键是分析算法的步骤，因为程序框图是算法步骤的图形表示，所以算法步骤越明 确画图就越容易；另外，在分段函数这种需要对条件

12、进行判断的算法设计中，宜使用条件结构. 例2看下面的问题：1+2+3+（ ） 10000 .这个问题的答案不唯一，我们只要确定出满足条件 的最小正整数n0，括号内填写的数字只要大于或等于 n0即可试写出寻找满足条件的最小正整数 n0的算法 并画出相应的程序框图. 【思路分析】本题考查的是循环结构的程序框图的设计、关键设计循环体，本题为累加型循环结构，故累 加变量p的初始值为0，计数变量i的初始值i =0，循环体：i =：i 1 , p = p i . 本题也可以利用公式法 s= 创，变量S每一次的取值，都是n变化后的赋值. 2 【解】方法一：算法步寢： 第步p p = = 第二步， 第三步，n

13、 n 第四步 第五步/若1010000,000,则输出口否则，执行第三步. 该算法的程序框團如團所示.10 方法：算法步骚； 第一步，取打的值等于-第二步，计算用=笛巴. 第三步，如果S的值大于10000,那么输出心否则，让刃的值増加1后转到第二步重复操作. 根抿次上的操作步靈可以画出如图所示的程序框图. 【点评】(1)方法二的初始值n从1开始，若从一个较大的 n的初始值开始，可以减少计算机执行的时间. (2)在循环结构中，要注意根据条件设计合理的计数变量、累加变量及其个数，特别要注意条件的表述要 恰当、精确. (3) 累加变量的初始值一般取 0. 根据程序框图设计程序关键在于： (1) 明确

14、程序框的结构(顺序结构、条件结构、循环结构) 根据程序框图设计程序 11 (2) 明确各程序框的含义. (3) 明确各结构及程序框对应的程序语言. 可简记为“一看结构，二看框，程序语言用恰当”. 例1请写出如图所示的程序框图描述的算法程序. 【思路分析】本题考查了条件语句的设计，通过观察我们发现这个程序框图描述的算法含有两个条件结 2 x -1 x1, 构.通过进一步分析我们还会发现这是一个求分段函数 y=2x+1 -1剟x 1,的函数值的算法.输入、输出 I 2 彳 x 1 X :： -1 框分别对应输入、输出语句、判断框对应条件语句. 【解】所求算法程序为： INPUT “ Please

15、in put x= ”； x IF x1 THEN y=x?2-1 ELSE IF x-1 THEN y= x?2+1 ELSE y=2 *x+1 END IF 12 END IF PRINT “函数值为y=”； y ENDs=0 13 【点评】（1）在本程序中，IF THEN ELSE语句嵌入了另一个 IF THEN ELSE语句，在每一个语句结束 时都要写END IF ； （2） 上述两个语句的先后层次关系， 我们用缩进若干空格的办法来体现， 从而使程序层次分明， 便于检阅; （3） 若程序中有幕，其底数和指数之间要用专用符号“ ？”连接. 例2.个球从100 m的高度落下，每次落地后又反

16、跳回原高度的一半，再落下，在第 10次落地时，小球 共经过多少路程？画出程序框图，并根据程序框图写出程序. 【思路分析】 本題考查的是彳It环语句的程序i殳计， 关键分清循环体结构的设计， 本题是实际应用題. 第1次下落的高度妬LOOm; 第2次下藩的高度親=贏=50m; 霜孑次下落的咼度 = 1 =25叫 第10次下落的咼度论=舟虬. 二递推关系式是=100m,也 弓屯（L.2,刃 到第10次落地时，共经过的路程为坷十地十纯卄+M厂縮+応珂十 訥，故可将生 作为累加变量，（作为计数娈重. 【解】程序框图： 开始 _ _ / h=100 1=1 ss*2h T A s=j100 /输出 i=M

17、 T T 结束 根据程序框图，可设计程序如下: h=100 i=1 14 WHILE i=10 s=s+2* h h=h/2 i=i+1 WEND s=s-100 PRINT s END 【点评】由于球每次下落的高度都是前一次下落后高度的一半，故可引进一个变量，对其累乘即可求得每 根据程序画程序框图要做到： （1） 明确程序是由哪些关键语句构成的（条件语句、循环语句） （2） 明确各类语句定义符号的含义； （3） 明确各类语句对应的程序框图. 可简记为“抓关键，补符号，按照规则画出来”. 例1请根据给出的算法程序画出程序框图. a=1 b=1 i=2 WHILE i v =12 c=a+b a=b 15 b=c i=i+1 WEND PRINT c END 【思路分析】本程序是一个当型循环结构，本程序的关键语句是一个当型循环语句，盘=1, b=? 22都 是赋倩语句（茸中混计数变量人PRINT c是输出语句，WHI