专题1.3 算法案例-2020-2021学年高一数学同步课堂帮帮帮（人教版必修3）

第一章 算法初步 1.3 算法案例 1．求两个正整数的最大公约数的算法 （1）辗转相除法 ①定义：辗转相除法是用于求_____________的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数． ②算法步骤 用辗转相除法求两个正整数的最大公约数，其算法步骤如下： 第一步，给定两个正整数． 第二步，计算除以所得的余数． 第三步，． 第四步，若，则的最大公约数等于；否则，返回第二步． ③程序框图如图所示： ④程序如下： INPUT m，n DO r=m MOD n m=n n=r PRINT m END 或 INPUT m，n r=1 While r>0 r=m MOD n m=n n=r PRINT m END （2）更相减损术 ①定义：中国古代的数学专著《九章算术》中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也．以等数约之．” ②算法步骤 第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． ③程序框图 ④程序如下： INPUT “a，b=”;a，b WHILE a≠b r=a−b IF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END 2．秦九韶算法 （1）定义及原理：把一个n次多项式改写成如下形式：．求多项式的值时，首先计算最内层括号内一次多项式的值，即，然后由内向外逐层计算一次多项式的值，即，…，，这种求n次多项式的值的方法叫做秦九韶算法． （2）秦九韶算法程序化的可行性探讨：观察秦九韶算法中的n个一次式，可见计算时要用到的值，若令，我们可以得到下面的递推公式：．这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现．