数学考点专项突破算法与二分法讲义pdf

算法与二分法算法与二分法 教 师：苗金利 爱护环境，从我做起 提倡使用电子讲义 爱护环境，从我做起 提倡使用电子讲义 - 第 1 页 - 第第 1 讲讲 算法与二分法算法与二分法 一、算法一、算法 【地位作用地位作用】算法是高中数学课程中的新内容，算法是人类认识世界的三大手段（科学计算、实验、 理论）之一科学计算的重要基础。通过本章中分析具体的事例，通过模仿、操作、 探索的过程，使学生体会算法的基本思想，发展学生思维、表达的条理性，提高逻辑思 维能力。 【重点难点重点难点】理解算法的概念及重要性、框图的概念及画框图的规则是重点，难点是写出简单数学问 题的算法及正确画出框图。 【教学内容教学内容】 1算法的概念算法的概念 （1）算法的定义：广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明 书是操作洗衣机的算法，菜谱是做菜的算法等等。 在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步 骤必须是明确和有效的，而且能够在有限步之内完成。 （2）高斯消去法 2算法的特点算法的特点 （1）确定性：算法的每一步都应当做到准确无误、 “不重不漏” 。 “不重”是指不是可有可无的、甚至 无用的步骤， “不漏”是指缺少哪一步都无法完成任务。 （2）逻辑性：算法从开始的“第一步”直到“最后一步”之间做到环环相扣。分工明确， “前一步”是 “后一步”的前提， “后一步”是“前一步”的继续。 （3）有穷性：算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果， 也就是说必须在有限步内完成任务，不能无限制的持续进行。 3算法的描述：自然语言、程序框图、程序语言。算法的描述：自然语言、程序框图、程序语言。 4程序框图程序框图 （1）程序框图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直 观地表示算法的图形； （2）构成程序框的图形符号及其作用 - 第 2 页 - 程序框 名称 功能 起止框 表示一个算法的起始和结束， 是任何算法程序 框图不可缺少的。 输入、输出框 表示一个算法输入和输出的信息， 可用在算法 中任何需要输入、输出的位置。 处理框 赋值、计算。算法中处理数据需要的算式、公 式等， 它们分别写在不同的用以处理数据的处 理框内。 判断框 判断某一条件是否成立， 成立时在出口处标明 “是”或“Y”；不成立时在出口处标明则标明 “否”或“N”。 流程线 算法进行的前进方向以及先后顺序 连结点 连接另一页或另一部分的框图 注释框 帮助编者或阅读者理解框图 （3）程序框图的构成 一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框 内必要的说明文字。 （4）画程序框图的规则 使用标准的框图的符号。 框图一般按从上到下、从左到右的方向画。 除判断框外，其他框图符号只有一个进入点一个退出点。判断框是具有超过一个退出点的唯一符 号。 一种判断框是二择一形式的判断，有且只有两个可能结果；另一种是多分支判断，可能有几种不 同的结果。 在图形符号内描述的语言要非常简练清楚。 3几种重要的结构几种重要的结构 （1）顺序结构 顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的。它是 - 第 3 页 - 由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构。 见示意图和实例： 顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步 骤。如在示意图中，A 框和 B 框是依次执行的，只有在执行完 A 框指定的操作后，才能接着执行 B 框所指定的操作。 （2）条件分支结构 如下面图示中虚线框内是一个条件结构，此结构中含有一个判断框，算 法执行到此判断给定的条件 P 是否成立，选择不同的执行框（A 框、B 框） 。 无论 P 条件是否成立，只能执行 A 框或 B 框之一，不可能既执行 A 框又执行 B 框，也不可能 A 框、B 框都不执行。A 框或 B 框中可以有一个是空的，即不 执行任何操作。见示意图。 （3）循环结构 在一些算法中根据指定条件决定是否重复执行一条或多条指令的控制结构称为循环结构。 即从算 法某处开始，按照一定条件重复执行某一处理过程。重复执行的 处理步骤称为循环体。见示意图。 例题讲解例题讲解 例 1 写出一个将任意三个不同实数按由小到大列出的算法. 例 2 画出一个能够判断任意三个正数能否构成三角形的程序框图，如果能构成三角形并输出三角形 的形状（锐角、直角或钝角三角形）. 例 3 画出一个解一元二次型方程 2 0axbxc+=(a、b、c 为实数)的程序框图. - 第 4 页 - 例 4 给出 30 个数：1，2，4，7，其规律是：第 1 个数是 1，第 2 个数比第 1 个数大 1, 第 3 个 数比第 2 个数大 2，第 4 个数比第 3 个数大 3，依此类推.要计算这 30 个数的和，现已给出了该 问题算法的程序框图（如图所示） ，请在图中判断框内(1)处和执行框中的(2)处填上合适的语句， 使之能完成该题算法功能. 例 5 对任意给定的正整数 n，写出一个求 3333 123n+?的算法的程序框图. 练习练习 一、选择题 1算法的有穷性是指（ ） A. 算法必须包含输出 B. 算法中每个操作步骤都是可执行的 C. 算法的步骤必须有限 D. 以上说法均不正确 2算法共有三种逻辑结构，即顺序结构，条件结构和循环结构，下列说法正确的是（ ） A. 一个算法只能含有一种逻辑结构 B. 一个算法最多可以包含两种逻辑结构 C. 一个算法必须含有上述三种逻辑结构 D. 一个算法可以含有上述三种逻辑结构的任意组合 3以下给出的各数中不可能是八进制数的是（ ） A. 312 B. 10 110 C. 82 D. 7 457 4840 和 1 764 的最大公约数是（ ） A. 84 B. 12 C. 168 D. 252 5下图给出的是计算 1111 24620 +的值的一个程序框图，其中判断框内应填入的条件是（ ） A. i10 B. i20 D. i20 - 第 5 页 - 第5题图 第6题图 第7题图 6给出以下一个算法的程序框图（如上图所示） ，该程序框图的功能是（ ） A. 输出 a,b,c 三数的最大数 B. 输出 a,b,c 三数的最小数 C. 将 a,b,c 按从小到大排列 D. 将 a,b,c 按从大到小排列 7右边的程序框图（如图所示） ，能判断任意输入的数x的奇偶性：其中判断框内的条件是（ ） A. m=0 B. x=0 C. x=1 D. m=1 二、解答题 8已知一个正三角形的周长为 a ，求这个三角形的面积.设计一个算法解决这个问题. 9设计算法求 1111 1 2233499 100 + 的值.要求画出程序框图. - 第 6 页 - 10某电信部门规定：拨打市内电话时，如果通话时间不超过3分钟，则收取通话费0.2元，如果通 话时间超过3分钟，则超过部分以每分钟0.1元收取通话费（通话不足1分钟时按1分钟计） ， 试设计一个计算通话费用的算法.要求写出算法，画出程序框图. 二、二分法二、二分法 【学习目标】 1、结合图像，判断函数的零点与方程根的联系； 2、根据具体函数的图像，能够借助计算器用二分法求相应方程的近似解，了解这种方法是求方程近 似解的常用方法。 【教学重、难点】 1、理解函数零点的概念，分类讨论含字母参数函数的零点个数； 2、利用图形（结合图象变换、值域）分类讨论含字母参数函数的零点个数。 【教学内容和过程】 1、函数的零点、函数的零点 1、定义定义(函数零点) 如果函数 y = f (x)在实数 处的值等于零，即 f () = 0，则 叫做这个函数的零点零点。在坐标系中表 示图象与 x 轴的公共点是(, 0)点。 若 f (x) = (x-)ng(x)， （( )g x 不含零点） ，则 叫做这个函数的为 n 阶零点阶零点。 如果函数图象通过零点时穿过 x 轴，则称这样的零点为变号零点变号零点。如果函数图象通过零点时没有 穿过 x 轴，则称这样的零点为不变号零点不变号零点。奇数阶零点是变号零点，偶数阶零点是不变号零点。 2、二分法、二分法 对于在区间a, b 上连续不断， 且满足( )f a( )f b0的函数( )yf x=， 通过不断地把函数( )f x 的 零点所在的区间一分为二， 使区间的两个端点逐步逼近零点， 进而得到零点近似值的方法叫做二分法。 目的：目的：求函数零点近似值的方法，但不能确定零点个数。 依据：依据： 零点存在性定理零点存在性定理：如果函数( )yf x=在区间 , a b 上的图象是连续不断的一条曲线，并且有 ( ) ( )0f a f b，那么函数( )yf x=在区间( , )a b 内有有零点。即存在存在( , )ca b，使得 ( )0f c=，这个c也就是方程的根。 - 第 7 页 - 注意：注意： （1） 函数( )yf x=的图像在区间, a b上连续不断连续函数； 在区间, a b上连续， 在区间(), a b内 有零点； （2）( )f a与( )f b异号； （3）存在(),ca bc 不一定唯一； 步骤步骤： 给定精度，用二分法求函数( )f x 的零点近似值的步骤如下： （1）确定区间a，b ，验证( )f a( )f b0，给定精度； （2）求区间(a，)b的中点 1 x； （3）计算 1 ()f x： 若 1 ()f x=0，则 1 x就是函数的零点； 若( )f a 1 ()f x0，则令b= 1 x（此时零点 01 ( ,)xa x） ； 若 1 ()f x( )f b0，则令a= 1 x（此时零点 01 ( , )xx b） ； （4）判断是否达到精度； 即若|ab，则得到零点值a（或b） ；否则重复步骤（2）（4） 三、例题分析三、例题分析 例例1.利用二分法求函数 3 ( )2f xxx=的零点。 （精确到0.01） - 第 8 页 - 参考答案参考答案 例1解：S1：输入a，b，c S2：若ab，则tb=，ba=，at= S