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

| 26页
| 636人阅读
| 11人下载

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!页眉3学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!

第一章   算法初步

1.3 算法案例

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!

1.求两个正整数的最大公约数的算法

(1)辗转相除法

①定义:辗转相除法是用于求_____________的最大公约数的一种算法,这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,则这时较小的数就是原来两个数的最大公约数.

②算法步骤

用辗转相除法求两个正整数的最大公约数,其算法步骤如下:

第一步,给定两个正整数学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!.

第二步,计算学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!除以学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!所得的余数学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!.

第三步,学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!.

第四步,若学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!,则学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!的最大公约数等于学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!;否则,返回第二步.

③程序框图如图所示:

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!page number 0

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!原创精品资源学科网独家享有版权,侵权必究!


学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!页眉3学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!

④程序如下:

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约简;若不是,执行第二步.

第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

③程序框图

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!page number 1

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!原创精品资源学科网独家享有版权,侵权必究!


学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!页眉3学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!

④程序如下:

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次多项式学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!改写成如下形式:学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!.求多项式的值时,首先计算最内层括号内一次多项式的值,即学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!,然后由内向外逐层计算一次多项式的值,即学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!,…,学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!,这种求n次多项式学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!的值的方法叫做秦九韶算法.

(2)秦九韶算法程序化的可行性探讨:观察秦九韶算法中的n个一次式,可见计算学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!时要用到学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!的值,若令学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!,我们可以得到下面的递推公式:学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!.这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现.

(3)算法步骤

第一步,输入多项式次数n、最高次项的系数学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!和x的值.

第二步,将v的值初始化为学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!,将i的值初始化为n-1.

第三步,输入i次项的系数学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!.page number 2

学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!学科网(www.zxxk.com)--教育资源门户,提供试题试卷、教案、课件、教学论文、素材等各类教学资源库下载,还有大量丰富的教学资讯!原创精品资源学科网独家享有版权,侵权必究!


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。