最新高中数学必修3-算法初步精讲

《最新高中数学必修3-算法初步精讲》由会员分享，可在线阅读，更多相关《最新高中数学必修3-算法初步精讲（32页珍藏版）》请在装配图网上搜索。

1、精品文档高中数学必修 3- 算法初步精讲13.1流程图一、 知识导学1. 流程图：是由一些图框和带箭头的流线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，带箭头的流线表示操作的先后次序 .2算法的三种基本的逻辑结构：顺序结构、条件结构、循环结构.3根据对条件的不同处理，循环结构又分为两种：直到型 (until 型 )循环：在执行了一次循环体之后， 对控制循环条件进行判断，当条件不满足时执行循环体.满足则停止 .如图 13-1-3 ，先执行 A 框，再判断给定的条件 p 是否为“假”，若 p 为“假”，则再执行 A ，如此反复，直到 p 为“真”为止 .当型（ while

2、 型）循环：在每次执行循环体前对控制循环条件进行判断，当条件满足时执行循环体， 不满足则停止 .如图 13-1-4 ，当给定的条件 p 成立（“真”）时，反复执行 A 框操作，直到条件p 为“假”时才停止循环 .图 13-1-1图 13-1-2二、疑难知识1.“算法“没有一个精确化的定义，教科书只对它作了描述性说明，算法具有如下特点：精品文档精品文档（ 1）有限性：一个算法的步骤是有限的，必须在有限操作之后停止，不能是无限的 .（ 2）确定性：算法的每一步骤和次序应当是确定的 .（ 3）有效性：算法的每一步骤都必须是有效的 .2. 画流程图时必须注意以下几方面：（1）使用标准的图形符号 .（2

3、）流程图一般按从上到下、从左到右的方向画.（3 ）除判断框外，大多数流程图符号只有一个进入点和一个退出点.判断框具有超过一个退出点的唯一符号.（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果.（5）在图形符号内描述的语言要非常简练清楚.3. 算法三种逻辑结构的几点说明：（1 ）顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的 .在流程图中的体现就是用流程线自上而下地连接起来，按顺序执行算法步骤 .（2 ）一个条件结构可以有多个判断框 .（ 3）循环结构要在某个条件下终止循环，这就需要条件结构来判

4、断 .在循环结构中都有一个计数变量和累加变量 .计数变量用于记录循环次数，累加变量用语输出结果，计数变量和累加变量一般是同步执行的，累加一次，计数一次.三、经典例题 例 1已知三个单元存放了变量x ， y ， z 的值，试给出一个算法，顺次交换x ，y ， z 的值（即 y 取 x 的值， z 取 y 的值， x 取 z 的值），并画出流程精品文档精品文档图.错解：第一步yx第二步zy第三步xz流程图为图 13-1-3错因：未理解赋值的含义，由上面的算法使得y ， z 均取 x 的值 .举一形象的例子： 有蓝和黑两个墨水瓶， 但现在却把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其

5、互换，请你设计算法解决这一问题.对于这种非数值性问题的算法设计问题，应当首先建立过程模型， 根据过程设计步骤完成算法 . 我们不可将两个墨水瓶中的墨水直接交换，因为两个墨水瓶都装有墨水，不可能进行直接交换.正确的解法应为：S1 取一只空的墨水瓶，设其为白色；S2将黑墨水瓶中的蓝墨水装入白瓶中；S3将蓝墨水瓶中的黑墨水装入黑瓶中；S4将白瓶中的蓝墨水装入蓝瓶中；S5交换结束 .正解：第一步pz先将 z 的值赋给变量 p ，这时存放 z 的单元可作它用 精品文档精品文档第二步zy再将 y 的值赋给 z ，这时存放 y 的单元可作它用 第三步yx同样将 x 的值赋给 y ，这时存放 x 的单元可作它

6、用 第四步xp最后将 p 的值赋给 y ，三个变量 x ， y ， z 的值就完成了交换 流程图为图 13-1-4点评：在计算机中，每个变量都分配了一个存储单元，为了达到交换的目的，需要一个单元存放中间变量p . 例 2 已知三个数 a ， b ， c .试给出寻找这三个数中最大的一个算法，画出该算法的流程图 .解：流程图为精品文档精品文档图 13-1-5点评：条件结构可含有多个判断框，判断框内的内容要简明、准确、清晰.此题也可将第一个判断框中的两个条件分别用两个判断框表示，两两比较也很清晰.若改为求 100 个数中的最大数或最小数的问题则选择此法较繁琐，可采用假设第一数最大（最小）将第一个数

7、与后面的数依依比较，若后面的数较大（较小），则进行交换，最终第一个数即为最大（最小）值.点评：求和时根据过程的类同性可用循环结构来实现，而不用顺序结构. 例 3 画出求 1222324 299 21002 的值的算法流程图 .解：这是一个求和问题，可采用循环结构实现设计算法，但要注意奇数项为正号，偶数项为负号 .思路一：采用 -1 的奇偶次方（利用循环变量）来解决正负符号问题；精品文档精品文档图 13-1-6图 13-1-7思路二：采用选择结构分奇偶项求和；图 13-1-8思路三：可先将122232429921002化简成精品文档精品文档3711199 ，转化为一个等差数列求和问题， 易利用循

8、环结构求出结果 .例 4设计一算法， 求使 122232n22006 成立的最小正整数 n 的值 .解： 流程图为图 13-1-9点评：这道题仍然是考察求和的循环结构的运用问题，需要强调的是求和语句的表示方法 .若将题改为求使 122232n 22006 成立的最大正整数n 的值时，则需注意的是输出的值 . 例 5 任意给定一个大于1 的整数 n ，试设计一个程序或步骤对n 是否为质数做出判断 .解：算法为：S1判断 n 是否等于 2，若 n=2 ，则 n 是质数；若 n2 ，则执行 S2S2依次从 2 n-1 检验是不是的因数，即整除 n 的数，若有这样的数，则n 不是质数；若没有这样的数，

9、则n 是质数 .点评：要验证是否为质数首先必须对质数的本质含义作深入分析：（1）质数是只能被1 和自身整除的大于1 的整数 .（2）要判断一个大于1 的整数 n 是否为质数，只要根据定义，用比这个精品文档精品文档整数小的数去除n.如果它只能被1 和本身整除，而不能被其它整数整除，则这个数便是质数 .图 13-1-10 例 6 设计一个求无理数2 的近似值的算法 .分析：无理数2 的近似值可看作是方程x 220 的正的近似根， 因此该算法的实质是设计一个求方程x220 的近似根的算法 .其基本方法即运用二分法求解方程的近似解 .解：设所求近似根与精确解的差的绝对值不超过0.005, 算法 :S1

10、令()x22因为f (1)0, f (2) 0,所以设x1 1, x2 2f x.S2令 m( x1x2 )2 ,判断 f (m) 是否为 0, 若是 ,则 m 为所求 ;若否 ,则继续判断f ( x1 ) f (m) 大于 0还是小于 0.S3若f xfm0, 则 xm否则 令m .( 1 )( )1;, x2S4判断 x1x20.005是否成立，若是，则 x1 , x2 之间的任意值均为满足条件的近似根；若否，则返回第二步 .精品文档精品文档点评：二分法求方程近似解的算法是一个重要的算法案例，将在第三节中详细阐述 .四、典型习题1已知两个单元分别存放了变量A 和 B 的值，则可以实现变量A

11、, B 交换的算法是（）.AS1BABS1CACS1CADS1CAS2ABS2BCS2ABS2D BS3CBS3BC1 下面流程图中的错误是（）图 13-1-11A i 没有赋值B循环结构有错CS 的计算不对D判断条件不成立精品文档精品文档3. 将“打电话”的过程描述成一个算法，这个算法可表示为，由此说明算法具有下列特性.4. 在表示求直线 axbyc0 （ a ， b 为常数，且 a ， b 不同时为 0 ）的斜率的算法的流程图中，判断框中应填入的内容是5. 3 个正实数，设计一个算法， 判断分别以这 3 个数为三边边长的三角形是否存在，画出这个算法的流程图 .6.一队士兵来到一条有鳄鱼的深

12、河的左岸 .只有一条小船和两个小孩， 这条船只能承载两个小孩或一个士兵 .试设计一个算法，将这队士兵渡到对岸，并将这个算法用流程图表示 .13.2 基本算法语句一、知识导学1 赋值语句用符号“”表示， “ xy ”表示将 y的值赋给 x ，其中 x 是一个变量， y 是一个与 x 同类型的变量或表达式 .2 条件语句主要有两种形式： “行 If 语句”和“块 If 语句” .“行 If 语句”的一般形式为：IfAThenBElse C .一个行 If 语句必须在一行中写完，其中方括号中的Else 部分可以缺省 .“块 If 语句”的一般格式为 :IfAThen精品文档精品文档BElseCEnd

13、ifThen部分和Else 部分是可选的，但块If 语句的出口“ End if ”不能省 .3 循环语句主要有两种类型：For 语句和 While 语句 .当循环的次数已经确定，可用“For ”语句表示 .“For ”语句的一般形式为：For I from“初值”tostep “步长” End for上面“ For ”和“ End for ”之间缩进的步骤称为循环体.当循环次数不能确定是，可用“While ”语句来实现循环 .“ While ”语句的一般形式为：While AEnd while其中 A 表示判断执行循环的条件.上面“ While ”和“ End While ”之间缩进的步骤称为

14、循环体.二、疑难知识1. 有的条件语句可以不带“ Else”分支，即满足条件时执行 B，否则不执行任何操作 .条件语句也可以进行嵌套， 在进行条件语句的嵌套时， 书写要有层次 .例如：IfAThenB精品文档精品文档Else ifCThenDElseEEnd if2.“ For ”语句是在执行过程中先操作，后判断.而“ While ”语句的特点是“前测试”，即先判断，后执行 .若初始条件不成立，则一次也不执行循环体中的内容.任何一种需要重复处理的问题都可以用这种前测试循环来实现.三、经典例题例 1 下列程序的运行结果是.X 9 Y 8IfX 5 ThenYY7IfX 4 ThenYY6IfX

15、3 ThenYY6PrintY错解：8+7=15错因：误认为在一个程序中只执行一个条件语句，与在一个条件语句中只选择其中一个分支相混淆 .If A Then B Else C若满足条件 A 则执行 B，否则是执行 C，B 和 C 是这个条件语句的分支，而这个程序省略了Else 部分 .正解：这里是有三个条件语句，各个条件语句是独立的，三个条件均成立，所以按顺序依次执行，结果为8+7+6+6=27. 例 2下面的伪代码的效果是精品文档精品文档i0Whilei 10i i 2End WhileEnd错解：执行 10 次循环错因：将 For 语句和 While 语句混淆 . For 语句中有步长使循

16、环变量不断变化，而 While 语句则无 .正解：无限循环下去，这是因为这里i 始终为 0，总能满足条件“ i10 ”，故是一个“死循环” .点评：“死循环” 是设计循环结构的大忌， 此题可改变 i 的初始值或每一次循环i都增加一个值 . 例 3 下面的程序运行时输出的结果是（）I1WhileI5S0II1S S I IEnd whilePrint SEnd错解：第一次循环时， I 被赋予 2， S 被赋予 4 ；第二次循环时， I 被赋予 3，S被赋予 4+ 32 =13 ；第三次循环时， I 被赋予 4 ，S 被赋予 13+ 42 =29 ；第四次循环时， I 被赋予 5， S 被赋予 2

17、95254 .由于此时 I5 ，故循环终止，输出S为 54.精品文档精品文档正解：由于 S0 在循环内，每经过一次循环后S 都被赋值 0 ，因此，只要求满足条件的最后一次循环S 的值，即当 I4时， S04416 . 例 4 用语句描述求使 1357n1000成立的最大正整数 n 的算法过程 .解：n1T1WhileT1000n n 2 T T nEnd whilePrintn2点评：此题易错的是输出值， 根据 While 循环语句的特征当 T1000时跳出循环体，此时 n 的值是 T1000时的最小的整数，则使T1000的最大整数应为 n 的前一个奇数即 n2 . 例 5 已知当100x10

18、0时， yx1 ，当 x100 时， y4 ，当 x100 时，y x 4 ，设计一算法求 y 的值 .解： Read xIf100x100 thenyx1Else ifx100 Thenyx4Elsey4End ifEnd精品文档精品文档点评：嵌套 If 语句可用如上的紧凑形式书写，要注意的是如不是采取紧凑形式，则需注意一个块If 语句对应一个 End If ，不可省略或缺少 .例 6 设计一个算法，使得输入一个正整数n ，输出 1 ！+2 ！+3 ！+ n ！的值 .写出伪代码 .解：思路一：利用单循环， 循环体中必须包括一个求各项阶乘的语句以及一个求和语句 .ReadnT 1 S 0Fo

19、rIfrom1tonT T I S S TEnd ForPrintS思路二：运用内外双重循环，但尤其注意的是每一次外循环T 的值都要从1 开始 .ReadnS0ForIfrom1tonT1ForJfrom1toITTJEnd ForS S TEnd For精品文档精品文档PrintS四 、典型习题1 下列的循环语句循环的次数为（）For I from 1 to 7For J from 1 to 9Pint I+JEnd forEnd forEndA.7 次B.9 次C.63 次D.16 次2运行下面的程序后输出的结果是，若将程序中的 A 语句与 B 语句的位置互换，再次执行程序后输出的结果为.

20、x 1y 0Whilex3yyxA语句xx1B语句End WhilePrint x,yEnd3.伪代码描述的求T 的代数式是,求 S 的代数式是.Readn精品文档精品文档T 1 S 0For Ifrom 1 tonT T I S S IEndforPrint T,S4.运行下面程序后输出的结果为For I from 10 to 1 step -2Print IEnd forEnd5. 将 100 名学生的一门功课的成绩依次输入并计算输出平均成绩.13 3 算法案例一、知识导学1算法设计思想：（ 1）“韩信点兵孙子问题”对正整数m 从 2 开始逐一检验条件，若三个条件中有任何一个不满足， 则

21、m 递增 1 ，一直到 m 同时满足三个条件为止 (循环过程用 Goto 语句实现 )（ 2）用辗转相除法找出a.b 的最大公约数的步骤是：计算出ab 的余数 r ，若r 0，则 b 为 a, b 的最大公约数；若 r 0 ，则把前面的除数 b 作为新的被除数，继续运算，直到余数为 0 ，此时的除数即为正整数 a,b 的最大公约数 .2.更相减损术的步骤： （1 ）任意给出两个正数，判断它们是否都是偶数.若是，用 2 约简；若不是，执行第二步.（2 ）以较大的数减去较小的数，接着把较小的精品文档精品文档数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所

22、求的最大公约数.（ 3）二分法求方程 f ( x)0 在区间 a, b 内的一个近似解 x * 的解题步骤可表示为S1取 a,b 的中点 x01 ab ，将区间 一分为二；2S2若 f x00 ，则 x0就是方程的根；否则判别根 x 在 x0 的左侧还是右侧：若 f af x00 ， x*x0 , b ，以 x0 代替 a ；若 f af x00 ，则 x*a, x0 ，以 x0 代替 b ；S3若 a bc ，计算终止，此时 xx0 ，否则转 S1.二、疑难知识1int( x) 表示不超过 x 的整数部分， 如 int( 5.86)5,int( 0.32)0 ，但当 x 是负数时极易出错，如

23、 int(1.14)1就是错误的，应为 -2.2 mod( a,b) 表示 a 除以 b 所得的余数，也可用amod b 表示 .3辗转相除法与更相减损术求最大公约数的联系与区别：（1）都是求最大公约数的方法， 计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0 则得到，而更相减损术则以减数与差相等而得到.4 用二分法求方程近似解，必须先判断方程在给定区间 a, b 上是否有解 ,即f x 连续且满足f a f b0 .并在二分搜索过程中需对中点处

24、函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用Goto语句和条件语句实现算法 .精品文档精品文档三、经典例题例 1 int( 5 )，int(0.05)，mod( 67,9)，45mod 7=.A16，-1 ，4，3B.15 ，0，4，3C.15,-1,3,4D.15,-1,4,3错解：根据 int( x) 表示不超过 x 的整数部分 , mod( a, b) 表示 a 除以 b 所得的余数 ,选择 B.错因 :对 int( x) 表示的含义理解不透彻 ,将不超过 -0.05 的整数错认为是 0,将负数的大小比较与正数的大小比较相混淆.正解：不超过 -0.05 的整数是 -1,

25、 所以答案为 D.例 2 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于 0 且小于 1000 的整数是否为同构数 .错解： 算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相等，若相等，则为同构数.Read xyxxIf(xy 10)or( xy 100) or( xy 1000)ThenPrint xEnd ifEnd错因：在表示个位或最后两位或最后三位出现错误，“/ ”仅表示除，y/10,y/100,y/1000都仅仅表示商 .正解：可用 mod( y,10), mod( y,100), mod( y,1000) 来表示个位，最后两位以及最

26、后三位 .精品文档精品文档Read xyxxIf( xmod( y,10)or( xmod( y,100)or( xmod( y,1000)ThenPrint xEnd ifEnd 例 3 孙子算经中的“物不知数”问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上 2 ，每次加 3 ，加成 5 除余 3 的时候停下来，再在这个数上每次加15 ，到得出 7 除 2 的时候，就是答数 .试用流程图和伪代码表示这一算法.解：流程图为：伪代码为：10m220mm330 Ifmod m,53 Then Goto 20精品文档精品文档40 I

27、fmod(m,7)2ThenPrintmGoto8050End if60 m m 1570 Goto 4080End点评：这是孙子思想的体现，主要是依次满足三个整除条件. 例 4 分别用辗转相除法、更相减损法求192 与 81 的最大公约数 .解：辗转相除法：S119281230S28130221S3302119S421923S59330故 3是 192与 81的最大公约数 .更相减损法：S119281111S21118130S3813051S4513021S530219精品文档精品文档S621912S71293S8936S9633故 3 是 192 与 81 的最大公约数 .点评：辗转相除法

28、以除法为主， 更相减损术以减法为主， 计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数， 更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数. 例 5 为了设计用区间二分法求方程x3x 210 在 0 ，1 上的一个近似解 （误差不超过 0.001 ）的算法 ,流程图的各个框图如下所示,请重新排列各框图 ,并用带箭头的流线和判断符号“Y”N、”“组成正确的算法流程图,并写出其伪代码 .(其中 a,b 分别表示区间的左右端点)图 13-3-2流程图为精品文档精品文档图 13-3-3伪代码为10Reada,b20

29、x0(a b)230f (a)a3a213240f (x0 )x0x0150Iff ( x0 )0Then Goto 12060 If f (a) f ( x0 ) 0 Then70 bx0100End if精品文档精品文档80Else90 a x0100End if110If ab 0.001 Then Goto 20120Printx0130End点评：二分法的基本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来. 例 6 用秦九韶算法计算多项式f (x) 12 35 x 8x279x 36x 45x 53x6 在x 4 时的值时， v3 的值为.解： 根据秦九

30、韶算法，此多项式可变形为f xx x x x x 3x567983512按照从内到外的顺序，依次计算一次多项式当x4 时的值：v04v13(4)57v2(4)(7)634v3(4)347957故当 x4 时多项式的值为 57 .点评：秦九韶算法的关键是n 次多项式的变形 .把一个 n次多项式 f (x) an x nan 1 xn 1a1x a0 改写成f ( x) ( ( an xan 1 )x an 2 ) xa1 ) x a0 ，求多项式的值，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值，这样把求n 次精品文档精品文档多项式的值问题转化为求n 个一次多项式的值的

31、问题， 这种方法成为秦九韶算法.这种算法中有反复执行的步骤，因此，可考虑用循环结构实现.四、典型习题1以下短文摘自古代孙子算经一书，其引申出的“大衍求一术”称为“中国剩余原理”：“今有物不知其数， 三三数之剩二， 五五数之剩三， 七七数之剩二，问物几何？”答曰（）.A二十一B.二十二C.二十三D.二十四2用辗转相除法求52 与 39 的最大公约数的循环次数为（） .A1 次B.2 次C.3 次D.5 次3下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和.For I from 1 to 10xint( Rnd90)10Print x;IfThenn2n21

32、s2s2xElses1s1xEnd IfEndfor精品文档精品文档PrintPrint“奇数个数 = ”； n1 ，“偶数个数 = ”； n24若一个数的各因子之和正好等于该数本身，则该数成为完数.请补充完整下列找出 1 100 之间的所有完数的伪代码.Fora from 2 to 100c1For b from 2 toIf mod(a,b)=0ThenEnd ifEnd ForIfThenPrint aEnd if精品文档精品文档End ForEnd5设计求被 9 除余 4 ，被 11 除余 3 的最小正整数的算法，画出流程图，写出伪代码 .6利用辗转相除法或更相减损术求324,243,135的最大公约数 .精品文档