2016-2017学年高中数学 专题1.5 算法案例课件 新人教A版必修3.ppt
《2016-2017学年高中数学 专题1.5 算法案例课件 新人教A版必修3.ppt》由会员分享,可在线阅读,更多相关《2016-2017学年高中数学 专题1.5 算法案例课件 新人教A版必修3.ppt(31页珍藏版)》请在三一文库上搜索。
1、算法案例,1.辗转相除法,所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数.若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.,基础回顾,2、作用:辗转相除法是用于求两个正整数_的一种 算法,这种算法是由欧几里得在公元前300年左右首先提出 的,因此又叫_,最大公约数,欧几里得算法,【小结】辗转相除法的步骤: 第一步,给定两个正整数m,n不妨令mn. 第二步,计算m除以n所得的余数r 第三步,_,_ 第四步,若r=0,则m,n的最大公约数等于_; 否则,返回第二步,m=n,n=r,m,1、算理: 所谓更相减
2、损术,就是对于给定的两个数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,再用较大的数减去较小的数,反复执行此步骤,直到差数和较小的数相等,此时相等的两数便为原来两个数的最大公约数.,类型二:更相减损术,2、作用:更相减损术是我国古代数学专著_中 介绍的一种求两个正整数最大公约数的方法,九章算术,(1)算法步骤 第一步,输入两个正整数a,b(ab); 第二步,若a不等于b ,则执行第三步;否则转到第五步; 第三步,把a-b的差赋予r; 第四步,如果br, 那么把b赋给a,把r赋给b;否则把r赋给 a,执行第二步; 第五步,输出最大公约数b.,3、试根据更相减损术设计一个计算机程序,
3、求两个正整数的最大公约数。,类型三:秦九韶算法,1秦九韶算法: 秦九韶算法的是通过一次式的反复计算,逐步求出n次多项式的值因此对于一个n次多项式,利用秦九韶算法求多项式的值,只要做n次乘法运算和n次加法运算即可,2、作用:用秦九韶算法求n次多项式f(x)=anxn+an1xn1+a1x+a0, 当x=x0时的值. 3、基本原理:首先将多项式改写成如下形式: f(x)=anxn+an1xn1+a1x+a0=(anxn1+an1xn2+a1)x+a0 =(anxn2+an1xn3+a2)x+a1)x+a0= _,,=(anx+an1)x+an2)x+a1)x+a0,求多项式的值时,首先计算最内层括
4、号内的一次多项式的值, 即v1= _,然后由内向外逐层计算一次多项式的值,即 v2=v1x+an2,v3=v2x+an3, vn= _. 这样,求n次多项式f(x)的值就转化为求_,anx+an1,vn1x+a0,n个一次多项式的值,【小结】秦九韶算 法的步骤,1. 进位制的概念:进位制是人们为计数和运算方便而约定的计数系统,约定满二进一,就是_进制;满十进一,就是_进制;,也就是说,“满几进一”就是_进制,几进制的基数就是_.,二,十,几,几,类型四:二进制,2、表示:一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式:anan-1a1a0(k)(an
5、,an-1,a1,a0N,0an_,0_an-1,a1,a0k),k,3.进位制之间的转化 (1)k进制的数转化为十进制:若anan-1a1a0(k)表示一个k进 制的数,则转化为十进制数为: anan-1a1a0(k)=_. (2)将十进制化为k进制:用除k取余法,用k连续去除_,直到_为止,然后将所得的余数_,即为相应的k进制数.,ankn+an-1kn-1+a1k1+a0,十进制数所得的商,商为零,倒序写出,类型一、 求最大公约数,问题探讨与解题研究,例1.分别用辗转相除法和更相减损术求779与209的最大公约数.,【分析】(1)辗转相除法的操作是较大的数除以较小的数,直到余数为零 (2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2016-2017学年高中数学 专题1.5 算法案例课件 新人教A版必修3 2016 2017 学年 高中数学 专题 1.5 算法 案例 课件 新人 必修
链接地址:https://www.31doc.com/p-2772747.html