当前位置:首页 >> 数学 >>

【名师一号】(新课标)2015-2016学年高中数学 第一章 算法初步本章回顾课件 新人教A版必修3_图文

第一章

算法初步

本章回顾

知识结构

重点知识回顾 一、算法与程序框图 1.解决问题的步骤就是算法. 任何一个能够利用计算机解决问题的算法必须具备以下 5 个 特性: (1)可执行性. (2)确定性. (3)有穷性.

(4)有输入信息的说明. (5)有输出结果的步骤. 在书写算法时,为了得到易读、易懂、易修改扩充的算法,应 做到以下几点: (1)利用自上而下的方法设计算法. (2)利用顺序结构、条件结构、循环结构这 3 种基本逻辑结构 来设计算法. (3)要有优美的算法表达风格.

2.程序框图是用一些图形符号表示各种操作,它直观形象, 易于理解,便于人们之间的交流与合作.学习这部分内容时,我们 要掌握基本的图形符号,在书写算法或画流程图时,要熟练地运用 顺序结构、条件结构、循环结构这 3 种基本逻辑结构来表达算法.

二、基本算法语句 本章介绍了输入语句、输出语句、赋值语句、条件语句、循环 语句,通过这些语句,我们可以编写出计算机能够读懂的程序.

三、算法案例 1.用辗转相除法与更相减损术求两个数的最大公约数时,一 定要弄清每一次除法和减法中的被除数、除数和被减数、减数,同 时要掌握两种方法中除法和减法分别应在何种情况下停止运算, 得 出结果.

2.要注意不同进制的数之间的转换方法.k 进制数化为十进 制数的方法是把 k 进制数写成各位上数字与 k 的幂的乘积之和的形 式,再按十进制数的运算规则计算出结果;十进制数化为 k 进制的 方法是用 k 连续去除十进制数求所得的商,直到商是零为止,然后 把各步得到的余数倒写就是相应的 k 进制数.

专 题 探 究



算法设计

算法设计与一般意义上的解决问题不同,它是对一类问题 的一般解法的抽象与概括,它要借助一般问题的解决方法,又 要包含这类问题的所有可能情形.它往往是把问题的解法划分 为若干个可执行的步骤,有些甚至是重复多次,但最终都必须 在有限个步骤之内完成.

【例1】 已知平面直角坐标系中的两点A(-1,0), B(3,2),写出求线段AB的垂直平分线方程的一个算法. 【分析】 线段AB的垂直平分线是指经过线段AB的中点

且与直线AB垂直的直线,故可先由中点坐标公式求出线段AB 2-0 1 的中点N(1,1),然后计算直线AB的斜率k1= = .由垂直 3-?-1? 2 关系,可知AB垂直平分线的斜率k=-2,最后由点斜式写出 直线方程.

【解】

-1+3 0+2 第一步,计算x0= 2 =1,y0= 2 =1,得

AB的中点N(1,1). 2-0 1 第二步,计算k1= = ,得AB的斜率. 3-?-1? 2 1 第三步,计算k=- =-2,得AB垂直平分线的斜率. k1 第四步,得直线AB垂直平分线的方程,输出.

点评

该算法步骤的设计依据了解析几何中求线段垂直平

分线的一般方法.同学们还可以思考:如果把已知的两点坐标改 为 A?x1,y1?,B?x2,y2?.算法设计将会发生怎样的变化呢?

【例 2】 一个大油瓶装了 8 kg 油,还有两个空油瓶,一 个能装 5 kg 油,另一个能装 3 kg 油.请设计一种算法,将这 8 kg 油平均分成两份. 【分析】 这是一个非数值计算性问题的算法设计,应考

虑首先建立过程模型.此问题中要充分利用好两个空油瓶,用 它们起到称量的作用.

【解】

算法步骤如下:

第一步,用 8 kg 油瓶中的油将 3 kg 油瓶倒满,再将 3 kg 油倒入到 5 kg 油瓶中. 第二步,用 8 kg 油瓶中剩余的油装满 3 kg 油瓶,再用这 3 kg 油瓶中的油装满 5 kg 油瓶,这时 3 kg 油瓶中剩 1 kg 油. 第三步,将 5 kg 油瓶中的油(5 kg)倒入 8 kg 油瓶中,然后 将 3 kg 油瓶中的 1 kg 油倒入 5 kg 油瓶中.

第四步,用8 kg油瓶中的油装满3 kg油瓶,然后将该3 kg 油倒入5 kg油瓶中,这时5 kg油瓶中有4 kg油,8 kg油瓶中也有 4 kg油. 上述各步可用下图表示.

点评 以上给出了该问题的一种算法,当然其算法不是唯 一的,同学们可思考其他的算法,并比较它们的优劣.



程序框图及其画法

程序框图是用规定的图形和指向线来准确、直观、形象地 表示算法的图形.画程序框图之前应先对问题设计出合理有效 的算法,然后分析算法的逻辑结构,根据逻辑结构画出相应的 程序框图.

【例3】 已知函数y=

? ?x ?x<0?, ? 2 ? ?x≥0?, ??x+1?

输入任意一个

实数x,求相应的函数值,画出程序框图,写出程序. 【分析】 根据输入的x确定x的范围,从而确定代入哪一

个表达式.故采用条件语句,可先画出程序框图,再写程序.

【解】 程序框图如图所示.

【例4】 如图,在边长为4的正方形ABCD的边上有一点 P,沿着折线BCDA由点B(起点)向点A(终点)运动.设点P运动 的路程为x,△APB的面积为y,求y与x之间的函数关系式,画 出程序框图,写出程序.

【分析】 按照题意,根据x的变化,写出分段函数的解 析式.

【解】

?2x ?0≤x≤4?, ? 函数关系式为y=?8 ?4<x≤8?, ?2?12-x? ?8<x≤12?. ?

程序:

程序框图如图所示.



循环结构及其应用

算法中的逻辑结构是根据指定条件决定是否重复执行一条 或多条指令的控制结构.由于计算机的运算速度快,最适宜做 重复性的工作,因此循环是计算机解题的一个重要特征,正因 为如此,在算法的三种逻辑结构中,循环结构是很重要的一 种,也是学者在应用中感到最为困惑的一种.本文进一步探析 循环结构及其应用.

一、循环结构的两种基本类型

二、用循环结构的关键点 (1)确定循环变量和初始值; (2)确定算法中反复执行的部分,即循环体; (3)确定循环的终止条件.循环结构有两种——直到型(UNTIL) 和当型(WHILE).

三、循环结构的应用 1.用于迭加运算. 【例5】 计算S=1+(1+2)+(1+2+3)+(1+2+3+4)+? +(1+2+3+4+?+n)的值,画出程序框图并编写程序.

【解】 n=1 时,S1=1; n=2 时,S2=1+(1+2)=S1+(1+2); n=3 时,S3=S2+(1+2+3); ? Sn=Sn-1+(1+2+3+4+?+n) 故先考虑 Tn=1+2+3+4+?+n 的程序框图的画法,求出 Tn 后,将 Sn-1+Tn 赋给 Sn.

程序框图如下.

程序如下. INPUT “n=”;n i=0 S=0 T=0 DO i=i+1 T=T+i S=S+T LOOP UNTIL i>=n PRINT “S=”;S END

2.用于递推运算. 【例 6】 用砖砌一堵墙, 第一层用了全部砖的一半还多一块, 第二层用了剩下的砖的一半还多一块, 以后每一层都用了剩余砖的 一半还多一块,到第 20 层时恰好剩下 1 块砖,问这堵墙一共用了 多少块砖?试编写程序,解决这个问题.

【分析】 依题意知,砌第 20 层时剩余砖为 a20=1 块,砌第 19 层时剩余砖为 a19=(1+1)×2=4 块,砌第 18 层时剩余砖为 a18 =(4+1)×2=10 块,?,砌第 n 层时剩余砖为 an=(an+1+1)×2 块,所以递推公式为 a20=1,an=2(an+1+1),n=1,2,?,19.故本 题可用循环结构实现算法.

【解】 程序: