算法案例辗转相除法与更相减损术秦九韶算法与进位制第一课时课件_数学高一必修3第一章算法初步1.3人教A版.ppt

;;;目标导航;;1.辗转相除法的算法步骤 第一步，给定两个正整数 m，n(mn). 第二步，计算________除以________所得的______数 r. 第三步，m＝n，n＝r. 第四步，若 r＝0，则 m，n 的最大公约数等于______；否; 2.更相减损术的算法步骤 第一步，任意给定两个正整数，判断它们是否都是偶数.若 是用 2 约简；若不是，执行第二步. 第二步，以较大的数减去较小的数，接着把所得的差与 ________比较，并以大数减小数.继续这个操作，直到所得的数 ________为止，则这个数(等数)或这个数与约简的数的乘积就 是所求的最大公约数.;3.秦九韶算法 把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写; 求多项式的值时，首先计算最内层括号内的一次多项式的 值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值，;4.进位制;;【问题导思】　 1．如何求18与54的最大公约数？ 【提示】　短除法． 2．要求6 750与3 492的最大公约数，上述法还好用吗？ 【提示】　数值太大，短除法不方便用．;(1)更相减损之术(等值算法) 用两个数中较大的数减去较小的数，再用 和 构成新的一对数，对这一对数再用 减 ，以同样的操作一直做下去，直到产生 ，这个数就是最大公约数． (2)辗转相除法(欧几里得算法) 用较大的数除以较小的数所得的 和__________构成新的一对数，继续做上面的除法，直到 ，这个较小的数就是最大公约数.;【问题导思】　 1．怎样计算多项式f(x)＝x5＋x4＋x3＋x2＋x＋1当x＝5时的值呢？统计所做的计算的种类及计算次数分别是什么？ 　【提示】　f(5)＝55＋54＋53＋52＋5＋1＝3 906.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算．;2．我们把多项式变形为f(x)＝x2(1＋x(1＋x(1＋x)))＋x＋1，再统计一下计算当x＝5时的计算的种类及计算次数分别是什么？ 【提示】　从里往外计算仅需4次乘法和5次加法运算即可得出结果．;　(1)把一元n次多项式P(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写为 P(x)＝anxn＋an－1xn－1＋…＋a1x＋a0 ＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0 ＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0 ＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 令vk＝(…(anx＋an－1)x＋…＋an－(k－1))x＋an－k，;(2)计算P(x0)的方法 先计算 ，然后 逐层计算，直到 ，然后加上 ．;知识3 进位制 ;;例1 .分别用辗转相除法和等值算法求319和261的最大公约数． 【分析】　使用辗转相除法可依据m＝nq＋r，反复执行，直到r＝0为止；用等值算法是根据m－n＝r，直到n＝1为止．;【解析】　辗转相除法：319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)． 所以319与261的最大公约数是29. 等值算法：319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29. 即(319，261)→(261，58)→(203，58)→(145，58)→(87，58)→(58，29)→(29，29)． 所以319与261的最大公约数是29.;1．利用“等值算法”求给定的两个数的最大公约数，即多次利用减法，用数对中较大的数减去较小的数，直到相减的差与数对中较小的数相等为止． 2．更相减损之术的步骤： (1)判断两数是否都为偶数，若是，则都除以2直到所得两数不全为偶数．;(2)用较大的数减去较小的数，将差和较小的数构成一对新数，继续用较大数减去较小数，重复执行． (3)当差和较小数相等时，结束执行，此时差(或较小数)为不全为偶数的两数的最大公约数．;用“等值算法”(更相减损之术)求下列两数的最大公约数． (1)98，280；(2)72，168. 【解】　(1)(98，280)→(98，182)→(98，84)→(14，84)→(14，70)→(14，56)→(14，42)→(14，28)→(14，14)． ∴最大公约数为14. (2)(72，168)→(72，96)→(72，24)→(48，24)→(24，24)． ∴最大公约数为24.;例2. 用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值． 【分析】;【解析】　将f(x)改写为 f(x)＝(((((x－12)x＋60)x－160)x＋240)x