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

问题 1 求 204 与 85 的最大公约数 问题 2 求 8251 与 6105 的最大公约数 204 与 85 的最大公约数是 17 8251 与 6105 的最大公约数是 34 辗转相除法 : 我们可以证明，对于任意两个正整数，上述步骤总可以在有限步之后完成，从而总可以用辗转相除的方法求出最大公约数 案例 1 ：辗转相除法 例 1 观察用辗转相除法求 8251 和 6105 的最大公约数的过程 第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146 结论： 8251 和 6105 的公约数就是 6105 和 2146 的公约数，求 8251 和 6105 的最大公约数，只要求出 6105 和 2146 的公约数就可以了。 第二步 对 6105 和 2146 重复第一步的做法 6105=2146×2+1813 同理 6105 和 2146 的最大公约数也是 2146 和 1813 的最大公约数。 完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然 37 是 148 和 37 的最大公约数，也就是 8251 和 6105 的最大公约数 例 2 用辗转相除法求 225 和 135 的最大公约数 显然 45 是 90 和 45 的最大公约数，也就是 225 和 135 的最大公约数 思考 1 ：从上面的两个例子可以看出计算的规律是什么？ S1 ：用大数除以小数 S2 ：除数变成被除数，余数变成除数 S3 ：重复 S1 ，直到余数为 0 225=135×1+90 135=90×1+45 90=45×2 辗转相除法中的关键步骤是哪种逻辑结构？辗转相除法是一个反复执行直到余数等于 0 停止的步骤，这实际上是一个循环结构。 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 m = n × q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否 思考 2 ：辗转相除法中的关键步骤是哪种逻辑结构？ 算理： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 第一步： 任意给顶两个正整数；判断他们是否都是偶数。若是，则用 2 约简；若不是则执行第二步。 第二步： 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。 更相减损术 例 3 用更相减损术求 98 与 63 的最大公约数 解：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减 98 － 63 ＝ 3563 － 35 ＝ 2835 － 28 ＝ 728 － 7 ＝ 21 21 － 7 ＝ 14 14 － 7 ＝ 7 所以， 98 和 63 的最大公约数等于 7 例 1 计算多项式 ｆ （ ｘ ） = ｘ ５ ＋ ｘ ４ ＋ ｘ ３ ＋ ｘ ２ ＋ ｘ ＋１当 x = 5 的值 因为 ｆ （ ｘ ） = ｘ ５ ＋ ｘ ４ ＋ ｘ ３ ＋ ｘ ２ ＋ ｘ ＋１ 所以 ｆ （ 5 ） =5 ５ ＋ 5 ４ ＋ 5 ３ ＋ 5 ２ ＋ 5 ＋１ = 3125 ＋ 625 ＋ 125 ＋ 25 ＋ 5 ＋１ = 3906 算法 2 ： ｆ （ 5 ） =5 ５ ＋ 5 ４ ＋ 5 ３ ＋ 5 ２ ＋ 5 ＋１ = 5× （ 5 ４ ＋ 5 ３ ＋ 5 ２ ＋ 5 ＋１） ＋１ = 5× （ 5× （ 5 ３ ＋ 5 ２ ＋ 5 ＋１ ）＋１ ） ＋１ = 5× （ 5× （ 5× （ 5 ２ ＋ 5 ＋１） ＋１ ）＋１ ） ＋１ = 5× （ 5× （ 5× （ 5 × （ 5 ＋１ ） ＋１ ） ＋１ ）＋１ ） ＋１ 案例 2 ：秦九韶算法 算法 1 ： 设 是一个 n 次的多项 式 对该多项式按下面的方式进行改写 ： 要求多项式的值，应该先算最内层的一次多项式的值，即 然后，由内到外逐层计算一次多项式的值，即 这种将求一个 n 次多项式 f （ x ）的值转化成求 n 个一次多项式的值的方法，称为 秦九韶算法 。 例 2 已知一个五次多项式为 用秦九韶算法求这个多项式当 x = 5 的值。 解： 将多项式变形： 按由里到外的顺序，依此计算一次多项式当 x = 5 时的值： 所以，当 x = 5 时，多项式的值等于 17255.2 你从中看到了怎样的规律？怎么用程序框图来描述呢？ 开始 输入 f (x) 的系数： a 0 、 a 1 、 a 2 、 a 3 、 a 4 、 a 5 输入 x 0 n=0 v=a 5 v= v·x 0 +a 5 -n n=n+1 n < 5? 输出 v 结束 否 是 1 、什么是进位制？ 2 、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明． 进位制是人们为了计数和运算方便而约定的记数系统。 案例 3 ： 进位制 1 、我们了解十进制吗？所谓的十进制，它是如何构成的？ 十进制由两个部分构成 例如： 3721 其它进位制的数又是如何的呢？ 第一、它有 0 、 1 、 2 、 3 、 4 、 5 、 6 、 7 、 8 、 9 十个数字； 第二、它有 “权位” ，即 从右往左 为个位、十位、百位、千位等等。 ( 用 10 个数字来记数，称 基数 为 10) 表示有： 1 个 1 ， 2 个十， 7 个百即 7 个 10 的平方， 3 个千即 3 个 10 的立方 2 、 二进制 二进制是用 0 、 1 两个数字来描述的。如 11001 等 一、二进制的表示方法 区分的写法： 11001 （ 2 ） 或者（ 11001 ） 2 8 进制呢？ 如 7342 (8) k 进制呢？ a n a n-1 a n-2 …a 2 a 1(k) ？ 二、二进制与十进制的转换 1 、二进制数转化为十进制数 例 1 将二进制数 110011 (2) 化成十进制数 解： 根据进位制的定义可知 所以， 110011 （ 2 ） =51 。 练习 将下面的二进制数化为十进制数？ （ 1 ） 11 （ 2 ） 111 （ 3 ） 1111 （ 4 ） 11111 2 、十进制转换为二进制 ( 除 2 取余法：用 2 连续去除 89 或所得的商，然后取余数 ) 例 2 把 89 化为二进制数 根据“逢二进一”的原则，有 89 ＝ 2× 44 ＋ 1 ＝ 2× (2× 22 ＋ 0) +1 ＝ 2×( 2× ( 2× 11 ＋ 0) +0)+1 ＝ 2× (2× (2× (2× 5 ＋ 1) +0)+0)+1 5 ＝ 2× 2 ＋ 1 ＝ 2× （ 2× （ 2× （ 2× （ 2 2 ＋ 1 ） ＋ 1 ）＋ 0 ）＋ 0 ）＋ 1 89 ＝ 1×2 6 ＋ 0×2 5 ＋ 1×2 4 ＋ 1×2 3 ＋ 0×2 2 ＋ 0×2 1 ＋ 1×2 0 所以： 89=1011001 （ 2 ） ＝ 2× （ 2× （ 2× （ 2 3 ＋ 2 ＋ 1 ） ＋ 0 ）＋ 0 ）＋ 1 ＝ 2× （ 2× （ 2 4 ＋ 2 2 ＋ 2 ＋ 0 ） ＋ 0 ）＋ 1 ＝ 2× （ 2 5 ＋ 2 3 +2 2 ＋ 0 ＋ 0 ） ＋ 1 ＝ 2 6 ＋ 2 4 +2 3 ＋ 0 ＋ 0 ＋ 2 1 89 ＝ 2× 44 ＋ 1 44 ＝ 2× 22 ＋ 0 22 ＝ 2× 11 ＋ 0 11 ＝ 2× 5 ＋ 1 ＝ 2× (2× (2× ( 2× (2× 2 ＋ 1) +1) +0)+0)+1 所以 89 ＝ 2× （ 2× （ 2× （ 2× （ 2 × 2 ＋ 1 ） ＋ 1 ）＋ 0 ）＋ 0 ）＋ 1 余数 注意： 1. 最后一步商为 0 ， 2. 将上式各步所得的余数 从下到上排列 ，得到： 89=1011001 （ 2 ） 1 0 0 1 1 0 1 2 2 2 2 2 2 2 5 2 1 0 11 22 48 89 ！ 练习 将下面的十进制数化为二进制数？ （ 1 ） 10 （ 2 ） 20 （ 3 ） 128 （ 4 ） 256 例 4 把 89 化为五进制数 3 、十进制转换为其它进制 解： 根据 除 k 取余法 以 5 作为除数，相应的除法算式为： 所以， 89=324 （ 5 ） 。 89 5 17 5 3 5 0 4 2 3 余数 将 k 进制数 a 转换为十进制数 ( 共有 n 位 ) 的程序 a=a n a n-1 … a 3 a 2 a 1(k) =a n k (n-1)+ a n-1 k (n-2) + … + a 3 k 2 +a 2 k 1 + a 1 k 0 b=a 1 k 0 b=a 2 k 1 +b b=a 3 k 2 + b … b=a n k n-1 +b a i =GET a[i] GET 函数用于取出 a 的右数第 i 位数 INPUT a,k,n i=1 b=0 WHILE i<=n t=GET a[i] b=t*k^(i-1)+b i=i+1 WEND PRINT b END i=i+1 i=1