【数学】2019届一轮复习人教A版算法初步学案 15页

知识梳理 一、算法的概念 算法通常是指按照一定规则解决某一类问题的明确和有限的步骤．‎ 算法具有确定性、有效性、有限性的特征． ‎ 二、程序框图 ‎1．构成程序框图的图形符号、名称及其功能如下表：‎ 图形符号 名称 功能 终端框(起止框)‎ 表示一个算法的起始和结束 输入、输出框 表示一个算法输入和输出的信息 处理框(执行框)‎ 赋值、计算 判断框 判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”‎ 流程线 连接程序框 连接点 连接程序框图的两部分 说明：一个完整的程序框图一定会包含终端框（用于表示一个算法的开始和结束），处理框（赋值、计算，算法中处理数据需要的算式、公式等）和流程线．‎ ‎3．程序框图的画法 在用自然语言表述一个算法后，可以画出程序框图，用顺序结构、条件结构和循环结构来表示这个算法．这样表示的算法清楚、简练，便于阅读和交流．‎ 设计一个算法的程序框图通常要经过以下步骤：‎ 第一步，用自然语言表述算法步骤．‎ 第二步，确定每一个算法步骤所包含的逻辑结构，并用相应的程序框图表示，得到该步骤的程序框图．‎ 第三步，将所有步骤的程序框图用流程线连接起来，并加上终端框，得到表示整个算法的程序框图．‎ 注意：流程线不要忘记画箭头，因为它是反映流程执行先后次序的，若不画出箭头，则难以判断各框的执行顺序．‎ 三、基本算法语句 ‎1．IF-THEN语句 ‎2．IF-THEN-ELSE语句 ‎3．直到型(UNTIL)语句的一般格式 ‎4．当型(WHILE)语句的一般格式 四、算法案例 ‎1．辗转相除法与更相减损术 辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别．两者的区别是：‎ ‎（1）辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程．学 ‎ ‎（2）辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可．而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数．‎ 注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数．‎ ‎2．秦九韶算法 秦九韶算法的实质是：求多项式的值时，转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算．这种算法的运算次数较少，是多项式求值比较先进的算法．‎ ‎3．进位制 把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除 取余法，把十进制数转化为 进制数．‎ 专题讲解 专题一 算法设计 算法设计与一般意义上的解决问题不同，它是对一类问题的一般解法的抽象与概括，主要借助一般的问题解决方法，又要包括此类问题的所有情形．它往往是把问题的解决划分为若干个可执行的步骤，有时甚至是重复多次，但最终都必须在有限个步骤之内完成．‎ ‎（1）用数学语言描述算法解决问题的过程大体可分为三步：‎ 第一步，明确问题的性质，分析题意．‎ 我们将问题简单地分为数值问题和非数值问题，不同类型的问题可以有针对性地采用不同的方法进行处理．‎ 第二步，建立问题的描述模型．‎ 对于数值型问题，可以建立数学模型，通过数学语言来描述问题．对于非数值型问题，我们可以建立过程模型，通过过程模型来描述问题．‎ 第三步，设计、确立算法．‎ 对于数值型问题，我们可以采用数值分析的方法进行处理，数值分析中有许多现成的固定算法，我们可以直接使用．当然我们也可以根据问题的实际情况设计算法．对于非数值型问题，根据过程模型分析算法并进行处理，也可以选择一些成熟的办法进行处理，如排序、递推等．‎ ‎（2）算法设计应注意：‎ ‎①与解决问题的一般方法有联系，从中提炼出算法；‎ ‎②将解决问题的过程分为若干个可执行步骤；‎ ‎③引入有关的参数或变量对算法步骤加以表达；‎ ‎④用最简练的语言将各个步骤表达出来；‎ ‎⑤算法的执行要在有限步内完成．‎ 例1已知平面直角坐标系中两点，，写出求线段的垂直平分线方程的一个算法．‎ ‎【思路分析】本题考查了数值型问题的算法设计，首先明确线段的垂直平分线的定义，可先由中点坐标公式求出线段的中点，然后计算直线的斜率，由垂直关系求出的垂直平分线的斜率，最后由点斜式写出直线方程．学 ‎ ‎【点评】（1）数值性问题首先建立数学模型，然后将数学问题的求解过程细化过渡成算法步骤，这是通法．‎ ‎（2）注意数学问题的解法不是算法步骤．‎ 例2设计一个算法求，，，，五个不同实数中最小的数．‎ ‎【思路分析】本题考查非数值型问题的算法，按照递推关系，先比较与，令为和中的较小者，然后比较与，令较小者为，依次类推，得到最小数．‎ ‎【解】算法步骤：‎ 第一步，比较，的大小，若，则令；若，则令．‎ 第二步，比较，的大小，若，则令；否则值不变．‎ 第三步，比较，的大小，若，则令；否则值不变．‎ 第四步，比较，的大小，若，则令；否则值不变．‎ 第五步，输出．‎ ‎【点评】任给有限个数，求有限个数中的最大数（最小数），在所给数不是很多的情况下，可设第一个数为最大数（最小数），然后和第二个数比较，取出这两个数中的较大者（较小者）再与第三个数比较，一直进行下去，直到与最后一个数比较完毕．这样就可以得到答案．‎ 专题二 程序框图及其设计 ‎1．程序框图是用规定的图形和流程线来准确、直观、形象地表示算法的图形．‎ ‎2．算法的设计是画程序框图的基础，我们通过对问题的分析，写出相应的算法步骤，画程序框图之前应先对算法问题设计的合法性和合理性进行探讨，然后分析算法的逻辑结构和各步骤的功能（输入、输出、判断、赋值和计算），画出相应的程序框图，如果设计的程序框图较为复杂就采取“逐步求精”的思想设计框图，先将问题中的简单部分明确出来，再逐步对复杂部分进行细化，然后一步一步逐步向前推进，设计出程序框图．‎ 例1 某商场进行优惠促销：若购物金额在500元以上，打8折；若购物金额在300元以上，打9折；否则，不打折，设计算法和程序框图，要求输入购物金额为，即能输出实际交款额．‎ ‎【思路分析】本题考查了条件结构的程序框图，关键是由题意列出实际交款额y与购物金额之间的函数关系式 ‎ ‎∵它需要对进行三次判断，‎ ‎∴算法含有两个条件结构．‎ ‎【解】算法步骤：第一步，输入购物金额．‎ 第二步，判断是否成立，若成立，则；否则，执行第三步．‎ 第三步，判断是否成立，若成立，则；否则，．‎ 第四步，输出，结束算法．‎ 程序框图：‎ ‎【点评】画程序框图的关键是分析算法的步骤，因为程序框图是算法步骤的图形表示，所以算法步骤越明确画图就越容易；另外，在分段函数这种需要对条件进行判断的算法设计中，宜使用条件结构．‎ 例2看下面的问题：1+2+3+…+（　　　　）＞10000．这个问题的答案不唯一，我们只要确定出满足条件的最小正整数，括号内填写的数字只要大于或等于即可．试写出寻找满足条件的最小正整数的算法并画出相应的程序框图．学 ‎ ‎【思路分析】本题考查的是循环结构的程序框图的设计、关键设计循环体，本题为累加型循环结构，故累加变量的初始值为，计数变量的初始值，循环体：，．‎ 本题也可以利用公式法，变量每一次的取值，都是变化后的赋值．‎ ‎【点评】（1）方法二的初始值从1开始，若从一个较大的的初始值开始，可以减少计算机执行的时间．‎ ‎（2）在循环结构中，要注意根据条件设计合理的计数变量、累加变量及其个数，特别要注意条件的表述要恰当、精确．‎ ‎（3）累加变量的初始值一般取0．‎ 专题三 根据程序框图设计程序 根据程序框图设计程序关键在于：‎ ‎（1）明确程序框的结构（顺序结构、条件结构、循环结构）．‎ ‎（2）明确各程序框的含义．‎ ‎（3）明确各结构及程序框对应的程序语言．‎ 可简记为“一看结构，二看框，程序语言用恰当”．‎ 例1请写出如图所示的程序框图描述的算法程序．‎ ‎【思路分析】本题考查了条件语句的设计，通过观察我们发现这个程序框图描述的算法含有两个条件结构．通过进一步分析我们还会发现这是一个求分段函数 的函数值的算法．输入、输出框分别对应输入、输出语句、判断框对应条件语句． 学 ‎ ‎【解】所求算法程序为：‎ INPUT “Please input x=”；x IF x>1 THEN ‎ y=xˆ2-1‎ ELSE ‎ IF x<-1 THEN ‎ y= xˆ2+1‎ ‎ ELSE ‎ y=2 x+1‎ ‎ END IF END IF PRINT “函数值为y=”；y END ‎【点评】（1）在本程序中，IF—THEN—ELSE 语句嵌入了另一个IF—THEN—ELSE语句，在每一个语句结束时都要写END IF；学 ‎ ‎（2）上述两个语句的先后层次关系，我们用缩进若干空格的办法来体现，从而使程序层次分明，便于检阅；‎ ‎（3）若程序中有幂，其底数和指数之间要用专用符号“ˆ”连接．‎ 例2．一个球从100 m的高度落下，每次落地后又反跳回原高度的一半，再落下，在第10次落地时，小球共经过多少路程？画出程序框图，并根据程序框图写出程序．‎ ‎【解】程序框图：‎ 根据程序框图，可设计程序如下：‎ s=0‎ h=100‎ i=1‎ 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＜=12‎ c=a+b ‎ a=b ‎ b=c ‎ i=i+1‎ WEND PRINT c END ‎【解】给出的算法程序对应的程序框图：‎ 例2根据下列程序语句画出程序框图．‎ s=1‎ n=1‎ WHILE s＜5000‎ s=s n n=n+1‎ WEND PRINT n-2‎ END ‎【思路分析】从上面的程序可以看出，这是一个用循环语句写出的程序，从，开始，第一次循环为求1×1，第二次循环为求1×2，第三次循环为求1×2×3，…，第次循环为求！，因此，此程序就是输出使！＜5000的最大整数．学 ‎ ‎【解】程序框图：‎ ‎【点评】根据程序语句，可画出程序框图，由程序框图可以很容易地说出其功能．‎