2020届二轮复习算法案例课件（32张）（全国通用）

2020届二轮复习算法案例课件（32张）（全国通用）

由于 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 PROCEDURE CPOLY （ A ， n ， x ， P ） FOR i=2 TO n DO OUTPUT P RETURN 在这个算法中，为了计算一个 x 点处的函数 , 共需要作 2n-1 次乘法和 n 次加法。还能不能减少乘法的次数呢？我们可以将式 (3. 4. 1) 的右端按降幂次序重新排列，并将它表述成如下嵌套形式 这样，就可以利用式 (3.4.4) 的特殊结构，从里往外一层一层地进行计算，即按如下递推关系进行计算： 最后可得结果 (3.4.4) （ 3.4.5 ） 这种多项式求值的方法是由我国宋代的一位数学家秦九韶最先提出的，我们称之为秦九韶方法，在有的书上也叫霍纳 (Horner) 方法。其算法描述如下 : 算法 3.2 多项式求值的秦九韶方法． 输入：存放 的系数数组 A(0 ： n) ； 自变量 x 值。其中 。 输出： 值 P 。 PROCEDURE CHORNER （ A,n,x,P ） FOR i=n-1 TO 0 BY -1 DO OUTPUT P RETURN 由秦九韶算法可以看出，多项式函数的求值只要用一个很简单的循环就能完成，并且在这个循环中只需要作 n 次乘法和 n 次加法就够了。它在实际使用中是一个很有效的方法。 例 . 中国剩余定理（孙子定理）若 k>2 ，且 m 1 ， m 2 ， …m k 是两两互素的 k 个正整数，令 M= m 1 m 2 …m k =m 1 M 1 =m 2 M 2 =…=m k M k 。 则同余式组： x 1 =b 1 (modm 1 ) ， x 2 =b 2 (modm 2 ) ， …x k =b k (modm k ) 其正整数解是： X≡b 1 M 1 ’M 1 +b 2 M 2 ’M 2 +…+b k M k ’M k (modM) 其中 M i ’ 是满足同余式： M i ’M i ≡1(mod m i ) （ i = 1 ， 2…k ） ∴用孙子定理解同余式组： x i =b i (modm i ) （ i = 1 ， 2…k ）的算法步骤如下： 2. 对半法查找 ( 二分法 ) 算法 对 这种算法的实质是在一个有限且有序的对象中，通过每次缩减一半查找范围而达到迅速确定目的一个有效算法。因此有着很广泛的应用。例如，在数学中有很多方程是写不出根的解析表达式的，但是根的存在范围比较容易确定，那么如何才能找到它的根的一个足够准确的近似值呢？这时对半查找算法就可以大显身手了。 由初等函数 f(x)=0 构成的方程，如果有 f(a)f(b)<0 ，则可以肯定方程 f(x)=0 在（ a , b ）至少有一个实数根。 选择（ a , b ）的中点 c ，若 f(c)=0 ，则根就是 x=c 。若 f(c)<0 或 f(c)>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 所示，试图寻找一些规律。 第 1 次 第 2 次 第 3 次 第 4 次 …… 下落 10 7 4.9 3.43 …… 弹起 10×0.7=4.9 7×0.7=4.9 4.9×0.7=3.43 3.43×0.7=2.3401 …… 从表中容易看出：小球每次弹起的距离就是本次下落距离的 0.7 倍，而每一次下落距离等于上一次弹起的距离，即 Ln=0.7Hn Hn+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 ： Click to display 汉诺 (Hanoi) 塔问题是一个著名的应用递归算法解决的问题。 问题 4-17 ： 传说在古代印度的贝拿勒斯神庙里安放了一块黄铜板，板上插了三根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着 64 个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面 3 条规则： ⒈一次只能移动一个金盘。 ⒉每个金盘只能由一根宝石柱移到另外一根宝石柱。 ⒊任何时候都不能把大的金盘放在小的金盘上。 神化说，如果僧人把 64 个金盘完全地从一根宝石柱移到了另外一根上，世界的末日就要到了。当然，神化只能当故事听，世界不可以因为个别人的活动而导致末日。不过，如果能够计算出僧人按规则搬完 64 个金盘，地球能否继续存在也的确是个问题！因为即使僧人的动作十分敏捷，每秒都能移动一个金盘，那也得要几亿年！