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

第一章 算法初步知识梳理一、算法的概念算法通常是指按照一定规则解决某一类问题的明确和有限的步骤算法具有确定性、有效性、有限性的特征二、程序框图1构成程序框图的图形符号、名称及其功能如下表：图形符号名称功能终端框(起止框)表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框(执行框)赋值、计算判断框判断某一条件是否成立，成立时在出口处标明“是”或“y”；不成立时标明“否”或“n”流程线连接程序框连接点连接程序框图的两部分说明：一个完整的程序框图一定会包含终端框（用于表示一个算法的开始和结束），处理框（赋值、计算，算法中处理数据需要的算式、公式等）和流程线3程序框图的画法在用自然语言表述一个算法后，可以画出程序框图，用顺序结构、条件结构和循环结构来表示这个算法这样表示的算法清楚、简练，便于阅读和交流设计一个算法的程序框图通常要经过以下步骤：第一步，用自然语言表述算法步骤第二步，确定每一个算法步骤所包含的逻辑结构，并用相应的程序框图表示，得到该步骤的程序框图第三步，将所有步骤的程序框图用流程线连接起来，并加上终端框，得到表示整个算法的程序框图注意：流程线不要忘记画箭头，因为它是反映流程执行先后次序的，若不画出箭头，则难以判断各框的执行顺序三、基本算法语句1if-then语句2if-then-else语句3直到型(until)语句的一般格式4当型(while)语句的一般格式四、算法案例1辗转相除法与更相减损术辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别两者的区别是：（1）辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程（2）辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数注意：用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数2秦九韶算法秦九韶算法的实质是：求多项式的值时，转化为求n个一次多项式的值，共进行n次乘法运算和n次加法运算这种算法的运算次数较少，是多项式求值比较先进的算法3进位制把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数 专题讲解专题一 算法设计算法设计与一般意义上的解决问题不同，它是对一类问题的一般解法的抽象与概括，主要借助一般的问题解决方法，又要包括此类问题的所有情形它往往是把问题的解决划分为若干个可执行的步骤，有时甚至是重复多次，但最终都必须在有限个步骤之内完成（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=”；xif x1 then y=x2-1else if x-1 then y= x2+1 else y=2*x+1 end ifend ifprint “函数值为y=”；yend【点评】（1）在本程序中，ifthenelse 语句嵌入了另一个ifthenelse语句，在每一个语句结束时都要写end if；（2）上述两个语句的先后层次关系，我们用缩进若干空格的办法来体现，从而使程序层次分明，便于检阅；（3）若程序中有幂，其底数和指数之间要用专用符号“”连接例2一个球从100 m的高度落下，每次落地后又反跳回原高度的一半，再落下，在第10次落地时，小球共经过多少路程？画出程序框图，并根据程序框图写出程序【解】程序框图：根据程序框图，可设计程序如下：s=0h=100i=1while i=10s=s+2*h h=h/2i=i+1wends=s-100print send【点评】由于球每次下落的高度都是前一次下落后高度的一半，故可引进一个变量，对其累乘即可求得每次下落的高度专题四 根据程序画程序框图根据程序画程序框图要做到：（1）明确程序是由哪些关键语句构成的（条件语句、循环语句）；（2）明确各类语句定义符号的含义；（3）明确各类语句对应的程序框图可简记为“抓关键，补符号，按照规则画出来”例1请根据给出的算法程序画出程序框图a=1b=1i=2while i=12c=a+b a=b b=c i=i+1wendprint cend【解】给出的算法程序对应的程序框图：例2根