专题1.3 算法案例-2020-2021学年高一数学同步课堂帮帮帮(人教版必修3)
第一章 算法初步
1.3 算法案例
1.求两个正整数的最大公约数的算法
(1)辗转相除法
①定义:辗转相除法是用于求_____________的最大公约数的一种算法,这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,则这时较小的数就是原来两个数的最大公约数.
②算法步骤
用辗转相除法求两个正整数的最大公约数,其算法步骤如下:
第一步,给定两个正整数.
第二步,计算除以
所得的余数
.
第三步,.
第四步,若,则
的最大公约数等于
;否则,返回第二步.
③程序框图如图所示:
原创精品资源学科网独家享有版权,侵权必究!
④程序如下:
INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END | 或 | INPUT m,n r=1 While r>0 r=m MOD n m=n n=r WEND 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个一次式,可见计算时要用到
的值,若令
,我们可以得到下面的递推公式:
.这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现.
(3)算法步骤
第一步,输入多项式次数n、最高次项的系数和x的值.
第二步,将v的值初始化为,将i的值初始化为n-1.
第三步,输入i次项的系数.
原创精品资源学科网独家享有版权,侵权必究!