高中数学 第二章 算法初步 1 算法的基本思想课件 北师大版必修3(1).ppt

第二章算法初步 1算法的基本思想 1 通过几个具体问题的求解过程 体会算法的基本思想 2 了解算法的含义和特征 3 会用自然语言描述简单的具体问题的算法 学习目标 知识梳理自主学习 题型探究重点突破 当堂检测自查自纠 栏目索引 知识梳理自主学习 知识点一算法的含义及特征 答案 1 算法的概念在解决某些问题时 需要设计出一系列的或的步骤 通过实施这些步骤来解决问题 通常把这些步骤称为解决这些问题的算法 2 算法的特征 1 有限性 一个算法的步骤序列是的 必须在的操作之后停止 不能是无限的 2 确定性 算法中的每一步应该是的 并且能有效地执行且得到确定的结果 而不应当模棱两可 可操作 可计算 有限 有限 确定 答案 3 顺序性与正确性 算法从初始步骤开始 分为若干明确的步骤 每一个步骤只能有一个确定的后续步骤 前一步是后一步的前提 只有执行完前一步才能进行下一步 并且每一步都准确无误 才能完成问题 4 不唯一性 求解某一问题的解法不一定是的 对于同一个问题可以有的算法 5 普遍性 很多具体的问题 都可以设计合理的算法去解决 如心算 计算器计算都要经过有限 事先设计好的步骤加以解决 3 算法与计算机计算机解决任何问题都要依赖于算法 只有将解决问题的过程分解为若干个明确的步骤 即 并用计算机能够接受的 语言 准确地描述出来 计算机才能够解决问题 唯一 不同 算法 知识点二算法的设计 1 设计算法的目的设计算法的目的实际上是寻求一类问题的算法 它可以通过计算机来完成 设计算法的关键是把过程分解成若干个明确的步骤 然后用计算机能够接受的 语言 准确地描述出来 从而达到让计算机执行的目的 2 设计算法的要求 1 写出的算法必须能解决一类问题 2 要使算法尽量简单 步骤尽量少 3 要保证算法步骤有效 且计算机能够执行 思考一次青青草原园长包包大人带着灰太狼 懒羊羊和一捆青草过河 河边只有一条船 由于船太小 只能装下两样东西 在无人看管的情况下 灰太狼要吃懒羊羊 懒羊羊要吃青草 请问包包大人如何才能带着他们平安过河 答包包大人采取的过河的算法可以是第一步 包包大人带懒羊羊过河 第二步 包包大人自己返回 第三步 包包大人带青草过河 第四步 包包大人带懒羊羊返回 第五步 包包大人带灰太狼过河 第六步 包包大人自己返回 第七步 包包大人带懒羊羊过河 答案 返回 题型探究重点突破 题型一算法的概念 解析答案 例1下列关于算法的说法 正确的个数有 求解某一类问题的算法是唯一的 算法必须在有限步操作之后停止 算法的每一步操作必须是明确的 不能有歧义或模糊 算法执行后一定产生确定的结果 a 1b 2c 3d 4 反思与感悟 解由于算法具有有限性 确定性等特点 因而 正确 而解决某类问题的算法不一定唯一 从而 错 答案c 算法实际上是解决问题的一种程序性方法 它通常解决某一个或某一类问题 在用算法解决问题时 体现了特殊与一般的数学思想 反思与感悟 跟踪训练1下列说法中是算法的有 填序号 从上海到拉萨旅游 先坐飞机 再坐客车 解一元一次不等式的步骤是去分母 去括号 移项 合并同类项 系数化为1 求以a 1 1 b 1 2 两点为端点的线段ab的中垂线方程 可先求出ab中点坐标 再求kab及中垂线的斜率 最后用点斜式方程求得线段ab的中垂线方程 求1 2 3 4的值 先计算1 2 2 再计算2 3 6 6 4 24 得最终结果为24 解析答案 解析 说明了从上海到拉萨的行程安排 给出了解一元一次不等式这类问题的解法 给出了求线段的中垂线的方法及步骤 给出了求1 2 3 4的值的过程并得出结果 故 都是算法 答案 题型二算法的设计 解析答案 例2所谓正整数p为素数是指 p的所有约数只有1和p 例如 35不是素数 因为35的约数除了1 35外 还有5与7 29是素数 因为29的约数就只有1和29 试设计一个能够判断一个任意正整数n n 1 是否为素数的算法 解算法如下 第一步 给出任意一个正整数n n 1 第二步 若n 2 则输出 2是素数 判断结束 第三步 令m 1 第四步 将m的值增加1 仍用m表示 第五步 如果m n 则输出 n是素数 判断结束 第六步 判断m能否整除n 如果能整除 则输出 n不是素数 判断结束 如果不能整除 则转第四步 设计一个具体问题的算法 通常按以下步骤 1 认真分析问题 找出解决该问题的一般数学方法 2 借助有关变量或参数对算法加以表述 3 将解决问题的过程划分为若干步骤 4 用简练的语言将这个步骤表示出来 反思与感悟 跟踪训练2判断一个大于2的整数是否为质数的算法步骤如何设计 解第一步 给定大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 解析答案 题型三算法的应用 解析答案 例3一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 无砝码 将假银元找出来吗 反思与感悟 解方法一算法如下 第一步 任取2枚银元分别放在天平的两边 若天平左 右不平衡 则轻的一枚就是假银元 若天平平衡 则进行第二步 第二步 取下右边的银元放在一边 然后把剩下的7枚银元依次放在右边进行称量 直到天平不平衡 偏轻的那一枚就是假银元 方法二算法如下 第一步 把9枚银元平均分成3组 每组3枚 第二步 先将其中两组放在天平的两边 若天平不平衡 则假银元就在轻的那一组 否则假银元在未称量的那一组 第三步 取出含假银元的那一组 从中任取2枚银元放在天平左 右两边称量 若天平不平衡 则假银元在轻的那一边 若天平平衡 则未称量的那一枚是假银元 对于查找 变量代换 文字处理等非数值型计算问题 设计算法时 首先建立过程模型 然后根据过程设计步骤 完成算法 反思与感悟 跟踪训练3 韩信点兵 问题 韩信是汉高祖手下的大将 他英勇善战 谋略超群 为汉朝的建立立下了不朽功勋 据说他在一次点兵的时候 为保住军事秘密 不让敌人知道自己部队的军事实力 采用下述点兵方法 先令士兵从1 3报数 结果最后一个士兵报2 又令士兵从1 5报数 结果最后一个士兵报3 又令士兵从1 7报数 结果最后一个士兵报4 这样韩信很快算出自己部队里士兵的总数 请设计一个算法 求出士兵至少有多少人 解析答案 解第一步 首先确定最小的满足除以3余2的正整数 2 第二步 依次加3就得到所有除以3余2的正整数 2 5 8 11 14 17 20 第三步 在上列数中确定最小的满足除以5余3的正整数 8 第四步 然后在自然数内 在8的基础上依次加上15的倍数 得到8 23 38 53 第五步 在上列数中确定最小的满足除以7余4的正整数应为53 对算法的含义及特征的理解 易错点 例4计算下列各式中的s值 能设计算法求解的是 1 s 1 2 3 100 2 s 1 2 3 100 3 s 1 2 3 n n n 解析答案 返回 错解算法是为解决某一类问题而设计的一系列操作或可计算的步骤 也就是说在实际的算法中的值是具体的 因此 1 正确 而 3 中的值不具体 错误 对于 2 显然不符合算法的有限性 故只有 1 正确 错解分析错识的根本原因在于对算法的理解不透彻 自我矫正算法是为解决某一类问题而设计的一系列操作或可计算的步骤 也就是说在实际的算法中n的值是具体确定的 因此 1 3 是正确的 而算法又是具有有限性的 即执行有限步操作后一定能解决问题 而 2 显然不符合算法的有限性 所以 2 不正确 答案 1 3 返回 当堂检测 1 2 3 4 5 1 下列关于算法的说法中正确的是 a 算法是某个具体的解题过程b 算法执行后可以不产生确定的结果c 解决某类问题的算法不是唯一的d 算法可以无限地操作下去不停止 解析答案 解析算法与一般意义上具体问题的解法 既有区别 又有联系 算法的获得要借助一类问题的求解方法 而这一类具体问题都可以用这种方法来解决 因此a不对 算法中的每一步都应该是确定的 并且能有效执行 得到确定的结果 而不能含糊其辞或有歧义 所以b不正确 算法的操作步骤必须是有限的 必须在有限的步骤内完成 因此d不对 算法具有不唯一性 c正确 答案c 1 2 3 4 5 2 下列四种自然语言叙述中 能称为算法的是 a 在家里一般是妈妈做饭b 做米饭需要刷锅 淘米 添水 加热这些步骤c 在野外做饭叫野炊d 做饭必须要有米 解析算法是做一件事情或解决一个问题等的程序或步骤 故选b b 解析答案 1 2 3 4 5 3 在用二分法求方程零点的算法中 下列说法正确的是 a 这个算法可以求所有的零点b 这个算法可以求任何方程的零点c 这个算法能求所有零点的近似解d 这个算法可以求变号零点近似解 d 解析答案 解析二分法的理论依据是函数的零点存在定理 它解决的是求变号零点的问题 并不能求所有零点的近似值 1 2 3 4 5 解析答案 2 1 3 解析算法的步骤是有先后顺序的 第一步是输入 最后一步是输出 中间的步骤是赋值 计算 1 2 3 4 5 5 下面是解决一个问题的算法 第一步 输入x 第二步 若x 4 转到第三步 否则转到第四步 第三步 输出2x 1 第四步 输出x2 2x 3 当输入x的值为 时 输出的数值最小值为 解析答案 1 2 3 4 5 当x 4时