高中数学 111算法的概念课件 湘教版必修5.ppt

课标要求 1 通过对解决具体问题过程与步骤的分析 体会算法是解决问题的 机械 程序 并能在有限步内完成 体会算法的思想 2 通过对具体问题解决过程的探索和研究 掌握算法步骤 了解算法与求解一个具体问题在方法上的区别 明确算法的要求 3 初步学会为一个具体问题设计算法 11 1算法的概念 自学导引1 算法的概念算法 algorithm 通常是指由组成的求解某的通用的方法 对于该类问题中的每个给定的具体问题 机械地执行这些步骤就可以得到问题的解答 2 算法的要求 1 写出的算法 必须能解决 例如解任意一个二元一次方程组 并且能 2 算法过程要能 每一步执行的操作 必须 不能含混不清 而且经过有限步后能 有限多个步骤 一类问题 一类问题 重复使用 一步一步执行 确切 得出结果 3 算法的特点算法具有确定性 和 4 更相减损术对于给定两个正整数 作差后将所得的与的数构成一对新数 对这对数再用大数减小数 以同样的操作一直做下去 直到产生一对相等的数 这个数就是最大公约数 有效性 有限性 用较大的数减去较小的数 差 较小 自主探究1 算法与一般意义上的数学问题的解法一样吗 答案算法与一般意义上的数学问题的解法既有联系又有区别 1 联系 算法与解法是一般与特殊 抽象与具体的关系 例如 教材先从分析一个具体的二元一次方程组的求解过程 解法 出发 归纳出了二元一次方程组的求解步骤 并且指出 这样的求解步骤也适合所有满足限制条件的二元一次方程组 这些步骤就构成了解二元一次方程组的算法 2 区别 算法是解决某一类问题所需要的程序和步骤的统称 也可理解为数学中的 通法 解法是解决某一个具体问题的过程和步骤 是具体的解题过程 2 怎样正确理解更相减损术 答案所谓更相减损术就是对于给定的两个数 以两数中较大的数减去较小的数 然后将差和较小的数构成一对新数 再用较大的数减去较小的数 反复执行此步骤直到差数与较小的数相等 此时相等的两数便为原两数的最大公约数 算法步骤 以求a b两整数的最大公约数为例 s1 输入两个正整数a b a b s2 若a不等于b 则执行第三步 否则执行第五步 s3 把a b的差赋给r s4 如果b r 则把b赋给a 把r赋给b 否则把r赋给a 执行第二步 s5 输出最大公约数b 预习测评1 用更相减损术求98与56的最大公约数为 a 2b 7c 14d 56答案c 解析d中所示求解是无限个数相加 不具备算法的有限性特点 因此不可以用算法求解 答案d 3 以下有六个步骤 拨号 等拨号音 提起话筒 或免提功能 开始通话或挂机 线路不通 等复话方信号 结束通话 试写出打一个本地电话的算法 只写编号 答案 4 假设家中生火泡茶有下列几个步骤 最优的一个算法是 只写编号 a 生火 b 将水倒入锅中 c 找茶叶 d 洗茶壶茶杯 e 用开水冲茶 解析遵循时间最短原则设计最优算法 答案bacde 或badce 要点阐释1 算法概念的理解算法就是对一类问题 不是个别问题 都有效 计算可以一步一步地进行 每一步都能得到唯一的结果 通常我们把这一类问题的求解过程 叫做解决这一类问题的算法 算法一般是机械的 有时要进行大量重复的计算 它的优点是一种通法 只要按部就班地去做 总能算出结果 通常把算法过程称为 数学机械化 数学机械化最大的优点 是它可以让计算机来完成 2 算法可概括为以下几个特点 1 有限性一个算法应包含有限的操作步骤 而不能是无限的 2 确定性算法中的每一个步骤都应当是确定的 而不应当是模棱两可的 3 顺序性与正确性算法从初始步骤开始 分为若干明确的步骤 每一个步骤只能有一个确定的后继步骤 前一步是后一步的前提 只有执行完前一步才能进行下一步 并且每一步都准确无误 才能解决问题 4 不唯一性求解某一个问题的解法不一定是唯一的 对于一个问题可以有不同的算法 5 普遍性很多具体的问题 都可以设计合理的算法去解决 如心算 计算器计算都要经过有限的 事先设计好的步骤加以解决 3 更相减损术求两个数的最大公约数时 一定要弄清每一次减法中的被减数 减数 同时要掌握减法应在何种情况下停止运算 得出结果 典例剖析题型一算法的概念 例1 下列关于算法的描述正确的是 a 算法与求解一个问题的方法相同b 算法只能解决一个问题 不能重复使用c 算法过程要一步一步执行 每步执行的操作必须确切d 有的算法执行完后 可能无结果解析算法与求解一个问题的方法既有区别又有联系 故a不对 算法能重复使用 故b不对 每个算法执行后必须有结果 故d不对 由算法的有序性和确定性可知c正确 答案c方法点评算法实际上是解决问题的一种程序性方法 它通常指向某一个或一类问题 而解决的过程是程序性和构造性的 算法也可以看成解决问题的特殊的 有效的方法 1 下列关于算法的说法 正确的有 求解某一类问题的算法是唯一的 算法必须在有限步操作之后停止 算法的每一步操作必须是明确的 不能有歧义或模糊 算法执行后一定产生确定的结果 a 1个b 2个c 3个d 4个解析解决某一类问题的算法不唯一 第 个说法错误 正确 故选c 答案c 题型二更相减损术 例2 用更相减损术求下列两数的最大公约数 1 261 319 2 1734 816 解用更相减损术就是根据m n r 反复执行 直到n r为止 1 更相减损术 319 261 58 261 58 203 203 58 145 145 58 87 87 58 29 58 29 29 319与261的最大公约数是29 2 更相减损术 因为两数皆为偶数 首先除以2得到867 408 再求867与408的最大公约数 867 408 459 459 408 51 408 51 357 357 51 306 306 51 255 255 51 204 204 51 153 153 51 102 102 51 51 1734与816的最大公约数是51 2 102 方法点评通过上例可以发现用更相减损术求最大公约数 运算简单 程序易编 2 用更相减损术求63和98的最大公约数 解由于63不是偶数 把98和63以大数减小数 并辗转相减 如下图所示 所以98和63的最大公约数是7 题型三实际问题的算法 例3 一个人带三只狼和三只羚羊过河 只有一条船 同船可以容一个人和两只动物 没有人在的时候 如果狼的数量不少于羚羊的数量就会吃掉羚羊 请你设计安全渡河的算法 解要想安全过河 每一步都要遵循一个共同原则 在人运送动物过河的过程中 人离开岸边时必须保证每个岸边的羚羊数目要大于狼的数目 算法如下 s1 人带两只狼过河 s2 人自己返回 s3 人带一只狼过河 s4 人自己返回 s5 人带两只羚羊过河 s6 人带两只狼返回 s7 人带一只羚羊过河 s8 人自己返回 s9 人带两只狼过河 方法点评实际问题的算法与数学问题的算法是有区别的 一般数学问题的算法可以设计程序用计算机求解 而实际问题的算法一般不能用计算机解决 3 两个大人和两个小孩一起渡河 渡口只有一条小船 每次只能渡一个大人或两个小孩 他们四人都会划船 但都不会游泳 同学们现在想一想 他们怎样渡过河去 请写一写你的渡河方案 解因为一次只能渡过一个大人 而船还要回来渡其他人 所以只能让两个小孩先过河 渡河的方法与步骤为 s1 两个小孩同船渡过河去 s2 一个小孩划船回来 s3 一个大人独自划船渡过河去 s4 对岸的小孩划船回来 s5 两个小孩再同船渡过河去 s6 一个小孩划船回来 s7 余下的一个大人独自划船渡过河去 s8 对岸的小孩划船回来 s9 两个小孩再同船渡过河去 误区警示因对算法步骤理解不明确而致误 例4 写出求2 4 6 8 100的算法 错解 算法 s1 计算2 4 6 8 100 s2 输出第一步中的结果 错因分析对于连加连乘的问题 不能直接得到答案 应当逐步进行 正解 算法 s1 计算2 4得到6 s2 将第一步的结果与6相加得到12 s3 将第二步的结果与8相加得到20 s4 如此继续下去 一直加到100 s5 输出运算结果 纠错心得算法从初始步骤开始 分为若干明确的步骤 前一步是后一步的前提 只有执行完前一步才能进行下一步 而且每一步都是正确无误的 从而组成了一个有着很强逻辑性的步骤序列 课堂总结1 给出一个问题 设计其算法时应注意 1 认真分析问题 联系解决此问题的一般数学方法 2 综合考虑此类问题中可能涉及的各种情况 3 借助有关的变量或参数对算法加以表述 4 将解决问题的过程划分为若干个步骤 5 用简炼的语言将各个步骤表示出来 2 对于数值计算问题 如解方程 求方程组的解 解不等式 解不等式组 套用公式判断性的问题 累加累乘等这一类算