江西省遂川二中高中数学 算法的基本思想课件（1） 北师大版必修3.ppt

第二章算法初步 随着计算科学和信息技术的飞速发展 算法的思想已经渗透到社会的方方面 在以前的学习中 虽然没有出现算法这个名词 但实际上在数学教学中已经渗透了大量的算法思想 如四则运算的过程 求解方程的步骤等等 完成这些工作都需要一系列程序化的步骤 这就是算法的思想 第一个算学家 刘徽 祖冲之 第二个算学家 1算法的基本思想 1 一 算法概念的理解 1 提出问题 1 解二元一次方程组有几种方法 代入消元法和加减消元法 第一步 2 得5x 1 第二步 解 得 第三步 2 得 5y 第四步 解 得 第五步 得到方程组的解为 第二步 把 代入 得 第三步 解 得 第四步 把 代入 得 第五步 得到方程组的解为 第一步 得 第二步 解 得 第三步 得 第四步 解 得 第五步 得到方程组的解为 5 根据上述实例谈谈你对算法的理解 算法的定义 广义的算法是指完成某项工作的方法和步骤 在数学中 算法通常是指按照一定规则解决某一类问题的明确有限的步骤 6 总结算法的特征 确定性 算法的每一步都应当做到准确无误 不重不漏 逻辑性 算法从开始的 第一步 直到 最后一步 之间做到环环相扣 分工明确 前一步 是 后一步 的前提 后一步 是 前一步 的继续 有穷性 算法要有明确的开始和结束 当到达终止步骤时所要解决的问题必须有明确的结果 即必须在有限步内完成任务 不能无限制地持续进行 7 学习算法的意义 在解决某些问题时 需要设计出一系列可操作或可计算的步骤来解决问题 这些步骤称为解决这些问题的算法 它的优点是一种通法 只要按部就班地去做 总能得到结果 因此算法是计算机科学的重要基础 二 算法案例分析 例1 在给定素数表的前提下 设计算法 将936分解成素因素的乘积 4000以内的素数表见书p161附录1 分析理解 1 查表判断936是否是素数 1 如果963是素数 则分解结束 2 如果963不是素数 则进行第2步 2 确定936的最小素因素 2 3 查表判断468是否是素数 1 如果468是素数 则分解结束 2 如果468不是素数 则重复上述步骤 确定468的最小素因素 重复进行上述步骤 直到找出936的所有素因素 二 算法案例分析 例1 在给定素数表的前提下 设计算法 将936分解成素因素的乘积 4000以内的素数表见书p161附录1 解 算法步骤如下 1 判断936是否是素数 否 2 确定936最小素因素 2 3 判断468是否是素数 否 4 确定468最小素因素 2 5 判断234是否是素数 否 6 确定234最小素因素 2 7 判断117是否是素数 否 8 确定117最小素因素 3 9 判断39是否是素数 否 10 确定39最小素因素 3 11 判断13是否是素数 是 分解结束 分解结果是 短除法 例2 设计一个算法 求840与1764的最大公因数 解 算法步骤如下 1 先将840进行素因素分解 2 然后将1764进行素因素分解 3 确定它们的公共素因素 4 确定公共素因素的指数 公共素因素2 3 7的指数分别为2 1 1 5 最大公因数为 三 课堂练习 练习1 设计一个算法 求324 440 5