2021年上海市新高二数学校本知识点梳理及习题汇编第十四讲 算法案例.pdfVIP

第十四讲 4.3 算法案例 一、知识点梳理 1.辗转相除法：辗转相除法是求两个正整数的最大公约数的方法。 2.辗转相除法具体算法：用两个数中较大的数除以较小的数判断玉树是否为0，若不为0，则用较小的数 除以余数再判断余数是否为0，反复进行上述步骤，直到余数为0为止。这时的除数就是最大公约数。 3.更相减损术：更相减损术是求两个正整数的最大公约数的方法。 4.更相减损术的内容：任意给定两个正整数，判断它们是否都是偶数。若是，用2约简；若不是，则以较 大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的 数相等为止，这个数就是所求的最大公约数。 5.更相减损术与辗转相除法比较：更相减损术是作减法运算，而辗转相除法是作除法运算；更相减损术运 算次数较多，但每一次的计算都较简单。 6.秦九昭算法：秦九昭算法是能求多项式函数值的一种算法。 7.秦九昭算法步骤：对于任意一元n次多项式，首先将多项式改写为 n n 1     P x a x a x  a x a   n n 1 1 0 n1 n2     a x a  x  a x a n n 1 1 0 n2 n3 a x  a  x  a x  a x  a n n 1 2 1 0       a x a x a x  a x a   n n 1  n 2  1  0 令 v a x a x  a x a k   n n 1  n k 1  n k   则递推公式为 v a 其中k 1, 2, ,n. 0 n v v x a k k 1 n k 所谓递推，就是在一系列数中已知第一个数，则其后的每一个数都可由前面的数求出。根据上面的递推公 式，我们可由 依次求出所有的 。 v v 0 k v v x a ,v v x a ,v v x a , ,v v a , ,v v x a 1 0 n1 2 1 n2 3 2 n3 k k 1 nk n n1 0 在上述公式中， 是反复执行的，因此可用循环结构实现。 v v a k k 1 n k 8.进位制：①概念：进位制是人们为了计数或计算方便而约定的计数系统。约定“满几进一”就是几进制， 几进制的基数就是几。如果 是大于1的整数，那么以 为基数的 进制数可以表示为 k k k a a a a a k a a a a k n n1 1 0 k 0 k , 0 n1 , n2 , , 1 , 0