高一数学 算法案例课件 新人教A版必修3.ppt

四 算法案例 1 多项式求值的秦九韶方法 如果给定一个多项式 3 4 1 其中现在的问题是 给定一个x的值 要求多项式函数的值 对于这个问题 一种看起来很 自然 的方法是直接逐项求和 如果用表示x的k次幂 表示式 3 4 1 右端前k l项的部分和 即 由于x的k次幂实际上等于其次幂再乘上x 而前k 1项的部分和等于前k项的部分和再加上第k l项 因此 逐项求和的方法可以归结为如下的递推关系 3 4 2 作为递推公式 3 4 2 的初值为 3 4 3 这样 就可以利用初值 3 4 3 对于k 1 2 直到n 反复利用公式 3 4 2 进行计算 最后就可以得到 其算法描述如下 1 逐项法多项式求值 输入 存放的系数数组a 0 n 自变量x值 其中 输出 值p procedurecpoly a n x p fori 2tondooutputpreturn 在这个算法中 为了计算一个x点处的函数 共需要作2n 1次乘法和n次加法 还能不能减少乘法的次数呢 我们可以将式 3 4 1 的右端按降幂次序重新排列 并将它表述成如下嵌套形式 这样 就可以利用式 3 4 4 的特殊结构 从里往外一层一层地进行计算 即按如下递推关系进行计算 最后可得结果 3 4 4 3 4 5 这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的 我们称之为秦九韶方法 在有的书上也叫霍纳 horner 方法 其算法描述如下 算法3 2多项式求值的秦九韶方法 输入 存放的系数数组a 0 n 自变量x值 其中 输出 值p procedurechorner a n x p fori n 1to0by 1dooutputpreturn 由秦九韶算法可以看出 多项式函数的求值只要用一个很简单的循环就能完成 并且在这个循环中只需要作n次乘法和n次加法就够了 它在实际使用中是一个很有效的方法 例 中国剩余定理 孙子定理 若k 2 且m1 m2 mk是两两互素的k个正整数 令m m1m2 mk m1m1 m2m2 mkmk 则同余式组 x1 b1 modm1 x2 b2 modm2 xk bk modmk 其正整数解是 x b1m1 m1 b2m2 m2 bkmk mk modm 其中mi 是满足同余式 mi mi 1 modmi i 1 2 k 用孙子定理解同余式组 xi bi modmi i 1 2 k 的算法步骤如下 2 对半法查找 二分法 算法 对这种算法的实质是在一个有限且有序的对象中 通过每次缩减一半查找范围而达到迅速确定目的一个有效算法 因此有着很广泛的应用 例如 在数学中有很多方程是写不出根的解析表达式的 但是根的存在范围比较容易确定 那么如何才能找到它的根的一个足够准确的近似值呢 这时对半查找算法就可以大显身手了 由初等函数f x 0构成的方程 如果有f a f b 0 则用c值取代相应的a或b 取代原则是 保证有f a f b 0 这样 a b 的长度就只有原来的一半 我们可以更小的范围找到根 当有根的区间的长度足够小 通常是小于预先指定的误差 这时区间内任意两点的距离都小于区间的长度 所以区间内的任意一点都可以用来当方程根的近似值 这个就是对半求根法 参考算法 第一步确定有解区间 第二步取的中点 第三步计算函数f x 在中点处的函数值 第四步判断函数值是否为0 1 如果为0 就是方程的解 问题就得到了解决 2 如果函数值不为0 则分下列两种情形 若 则确定新的有解区间为 若 则确定新的有解区间为 第五步判断新的有解区间的长度是否小于精确度 1 如果新的有解区间长度大于精确度 则在新的有解区间的基础上重复上述步骤 2 如果新的有解区间长度小于或等于精确度 则取新的有解区间的中点为方程的近似解 对半求根的过程可以用如下框图表示 图4 1 用流程图表示如下 例 对半法求方程解 方程x 3sinx 0有一个根 试把它求出来 要求准确到0 0001 例闰年问题 输入年份y 判断该年份是否为闰年并输出结果 设y为年份 按照历法的规定 如果y为闰年 那么或者y能被4整除但不能被100整除 或者y能被400整除 可以用选择结构将上述算法表示如下 若y不能被4整除 则输出 y不是闰年 若y能被4整除 则判断y是否被100整除 则 2 若y能被100整除 则判断y是否能被400整除 则 1 若y不能被100整除 则输出 y是闰年 若y能被400整除 则输出 y是闰年 若y不能被400整除 则输出 y不是闰年 这个算法的流程图如下图4 3 小球运动问题问题 小球从10米高处自由下落 每次弹回的高度大约是下落高度的70 当小球弹起的高度不足最初高度的千分之一时 小球很快就会停止跳动 计算小球在整个弹跳过程中所经历的总路程 忽略高度不足原高度千分之一的部分 分析问题小球的运动由多次的下落和弹起构成 但弹起的次数并不容易知道 小明把小球每次下落和弹起的路程列出 如表3 1所示 试图寻找一些规律 从表中容易看出 小球每次弹起的距离就是本次下落距离的0 7倍 而每一次下落距离等于上一次弹起的距离 即ln 0 7hnhn 1 ln其中hn第n次下落的距离 ln为第n次弹起的距离 n 1 2 3 h1 10 把它们都相加 即可求出问题的解 s h1 l1 h2 l2 h3 l3 设计算法根据上述的分析 我们可以写出解决问题的算法如下 令h 10 令s 0 l 0 7 h s s h l h l 如果l 10 1000 返回第 输出s的值 结束 例一个关于栽树数量的i q 题 小陆学校的3个环保活动小组经常利用节假日去栽树 有一天 李老师问小陆3个小组各栽了多少树 因为李老师是教数学的 小陆就调皮的回答 3个小组的栽树数量相乘的积是30723 您能把3个组的栽树数量算出来吗 李老师说 只有这个条件不能确定答案呀 你能补充点情况吗 于是小陆补充说 a组都是大个子同学组成的 栽的树虽然不到100棵 但比另外两组合起来的还要多 栽树最少的c组也早就超过了10棵 这是李老师说 那我算出来了 李老师是怎样算出来的呢 老师后来告诉小陆 她用的是穷举法 穷举算法的思路是 列举出所有可能的情况 逐个判断有哪些是符合问题所要求的条件 从而得到问题的解答 q 题很有意思 但它用对话的形式表达 有些条件不够明确 因此需要用数学语言来描述它 用数学语言描述问题 叫做建立数学模型 在解决实际问题时 一般都需要为这个问题建立数学模型 问题a b c是三个整数 100 a b c 10 a b c 30723 且a b c 试确定a b c的值 分析问题解决这个问题应当从a b c 30723入手 把30723三个整数相乘的积 只能有有限种情况 我们可以把这些情况一一罗列出来 然后分析哪一种情况是符合条件的 从而找到答案 在列举所有情况时 注意三个因子都大于10 这可以减少列举的工作量 把30723分解为3个大于10的因子的乘积只有5种情况 11 19 147 三个因子的和是177 11 21 133 三个因子的和是165 19 49 57 三个因子的和是101 11 49 57 三个因子的和是117 19 21 77 三个因子的和是117 在这5种情况中考察 符合a b c而且最大的数小于100的 只有最后一种情况 即a 77 b 21 c 19 计算算法设计穷举算法的关键是如何列举所有可能的情况 绝对不能遗漏 最好不要重复 在列举时注意变量的范围 可以减少工作量 我们可以从最小的变量c入手 让它从10开始变化 但变化的范围到哪里为止呢 粗略估算一下 三个数相乘是30723 最小的c不超过它的立方根 我们可以用平方根做近似替代 不必作太多推算 当c值产生之后 就可以处理变量b 因为它不小于c 让它从c开始 也让它变化到30723的平方根 有了c和b的值之后 就要判断他们是否都是30723的因子 如果是 计算出第三个因子a 然后进行判断 a是否大于b c并且a 100 满足条件就是解答了 例题 钱币问题 在日程生活中常常需要用一些较小面额的钱币去组合出一定的币值 现有面值为1元 2元和5元的钞票 假设每种钞票的数量都足够多 从这些钞票中取出30张使其总面值为100元 问有多少种取法 每种取法的各种面值的钞票各为多少张 分析问题 显然列出一条算式来解决钱币问题是有困难的 既然解析法很难用上 我们尝试通过列举所有可能的情况 穷举 从中判断出合符条件的解答 当钞票数量比较多 总币值比较大时 人工列举所有钞票组合 穷举 就很麻烦 这时需要使用计算机来帮我们穷举 但使用计算机来穷举 必须清楚地说出穷举的每一个步骤 并通过程序设计语言转化为计算机能后执行的过程 才能解决问题 钱币问题有3种面额的钞票 钞票的总张数是30张 又应当如何穷举呢 经分析可以知道 当有两种面额的钞票数目确定了之后 可以从总张数为30确定第三种钞票的张数 然后由总面额是否100元而判断这个组合是否合乎要求 此外 先确定面额大的钞票可以使穷举的次数少些 设计算法用one two five分别记录1元 2元 5元钞票的张数 变量answer记录符合条件的解的数目 穷举的过程如下 让answer 0 five 0 two 0 让one 30 two five 检查5 five 2 two one是否等于100 若是 则得到一组解 这时让answer增加1 并且输出解答 如果two 30 那么让two增加1 转步骤 如果five 20 那么让five增加1 转步骤 结束可把这些步骤用框图表示如图4 7 clicktodisplay 汉诺 hanoi 塔问题是一个著名的应用递归算法解决的问题 问题4 17 传说在古代印度的贝拿勒斯神庙里安放了一块黄铜板 板上插了三根宝石柱 在其中一根宝石柱自上而下由小到大地叠放着64个大小不等的金盘 一名僧人把这些金盘从一根宝石柱移到另外一根上 僧人在移动金盘时遵守下面3条规则 一次只能移动一个金盘 每个金盘只能由一根宝石柱移到另外一根宝石柱 任何时候都不能把大的金盘放在小的金盘上 神化说 如果僧人把64个金盘完全地从一根宝石柱移到了另外一根上 世界的末日就要到了 当然 神化只能当故事听 世界不可以因为个别人的活动而导致末日 不过 如果能够计算出僧人按规则搬完64个金盘 地球能否继续存在也的确是个问题 因为即使僧人的动作十分敏捷 每秒都能移动一个金盘 那也得要几亿年 分析问题要模拟金盘的移动过程是比较困难的 但如果用递归的思想来进行 压缩规模 把问题解决在最简单的情况 则问题可以解决 我们把3根宝石柱分别命名为a b c 最初有n个金盘放在a 需要把它们全部按规则移动到b 当n 1时 直接把金盘从a搬到b就可以了 1次成功 当n 2 那么需要利用c柱来过渡 按照递归的思想 我们假设已经找到一种把n 1个金盘从一根柱搬到另外一根柱的方法 然后看看如何通过它来实现搬