高中数学必修三《13算法案例》课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《高中数学必修三《13算法案例》课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 13算法案例 高中数学 必修 13 算法 案例 课件
- 资源描述:
-
1、算算 法法 案案 例例(第一课时)1、求两个正整数的最大公约数、求两个正整数的最大公约数(1)求)求25和和35的最大公约数的最大公约数(2)求)求49和和63的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25(1)5535749(2)77639所以,所以,25和和35的最大公约数为的最大公约数为5所以,所以,49和和63的最大公约数为的最大公约数为7辗转相除法(欧几里得算法)辗转相除法(欧几里得算法)观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数,求得商和余数用两数中较
2、大的数除以较小的数,求得商和余数8251=61051+2146结论:结论:8251和和6105的公约数就是的公约数就是6105和和2146的公约数,求的公约数,求8251和和6105的最大公约数,只要求出的最大公约数,只要求出6105和和2146的公约数就可以了。的公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+33
3、31813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约的最大公约数,也就是数,也就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数,也就是的最大公约数,也就是225和和135的最大公约数的最大公约数 思考思考1:从上面的两个例子可以看出计:从上面的两个例子可以看出计算的规律是什么?算的规律是什么?S1:用大数除以小数:用大数除以小数S2:除数变成被除数,余数变成除数:除数变
4、成被除数,余数变成除数S3:重复:重复S1,直到余数为,直到余数为0 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是停止的步骤,这实际上是一个循环结构。一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm=nn=rr=0?是否九章算术九章算术更相减损术更相减损术 算理:算理:可半者半之,不可半者,副置分母、子之数,以少减多,更相减可半者半之,
5、不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。损,求其等也,以等数约之。第一步:第一步:任意给顶两个正整数;判断他们是否都是偶数。若是,则用任意给顶两个正整数;判断他们是否都是偶数。若是,则用2约简;若不是则执行第二步。约简;若不是则执行第二步。第二步:第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止,则这个以大数减小数。继续这个操作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数。等数就是所求的最大公约数。例例3 用更相减损术求用更相减
6、损术求98与与63的最大公约数的最大公约数解:由于解:由于63不是偶数,把不是偶数,把98和和63以大数减小数,并辗转相减以大数减小数,并辗转相减 9863356335283528728721217141477所以,所以,98和和63的最大公约数等于的最大公约数等于7 练习:课本P36练习第1题算法案例(第二课时)计算多项式计算多项式()=当当x=5的值的值算法算法1:因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2:(5)=55555=5(5555)=5(5(555 )=5(5(5(55)=5(5(5(5 (5 )数书九章数书九章秦九韶算法秦九韶算法0
7、111)(axaxaxaxfnnnn设设)(xf是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写:对该多项式按下面的方式进行改写:0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn这是怎样的一种改写方式?最后的结果是什么?0121)()(axaxaxaxaxfnnn要求多项式的值,应该先算最内层的一次多项式的值,即要求多项式的值,应该先算最内层的一次多项式的值,即11nnaxav然后,由内到外逐层计算一次多项式的值,即然后,由内到外逐层计算一次多项式的值,即212naxvv32
8、3naxvv01axvvnn最后的一项是什么?这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求)的值转化成求n个一次多项式的值的个一次多项式的值的方法,称为方法,称为秦九韶算法秦九韶算法。例例2 已知一个五次多项式为已知一个五次多项式为8.07.16.25.325)(2345xxxxxxf用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解:解:将多项式变形:将多项式变形:8.0)7.1)6.2)5.3)25()(xxxxxxf按由里到外的顺序,依此计算一次多项式当按由里到外的顺序,依此计算一次多项式当x=5时的值:时的值:272551v50v5.1385.3
9、5272v9.6896.255.1383v2.34517.159.6894v2.172558.052.34515v所以,当所以,当x=5时,多项式的值等于时,多项式的值等于17255.2你从中看到了怎样的规律?怎么用程序框图来描述呢?开始开始输入输入f(x)的系数:的系数:a0、a1、a2、a3、a4、a5输入输入x0n=0v=a5v=vx0+a5-nn=n+1n 5?输出输出v结束结束否否是是注意:要想使用检验功能,请使用前,先要减低宏的安全限制秦九韶算法检验排序的算法排序的算法将下面数字按由小到大的顺序排列将下面数字按由小到大的顺序排列8,3,2,5,9,6方法方法1:S1:比较第:比较第
10、2个数与第个数与第1个数的大小,并排序得个数的大小,并排序得3,8S2:将第:将第3个数与个数与S1中的数比较,插入适当的位置,得到中的数比较,插入适当的位置,得到2,3,8S3:将第:将第4个数与个数与S2中的数比较,并插入适当的位置,如中的数比较,并插入适当的位置,如此继续下去,直到把最后一个数插入到上一步已排好的数此继续下去,直到把最后一个数插入到上一步已排好的数列的合适位置为止,得到:列的合适位置为止,得到:2,3,5,82,3,5,8,92,3,5,6,8,9S4:S5:排序的算法排序的算法将下面数字按由小到大的顺序排列将下面数字按由小到大的顺序排列8,3,2,5,9,6方法方法1:
11、过过程程演演示示832596开始开始排第排第1次次排第排第2次次排第排第3次次排第排第4次次832596382596238596235896235896排第排第5次次235689排序的算法排序的算法将下面数字按由小到大的顺序排列将下面数字按由小到大的顺序排列8,3,2,5,9,6方法方法2:S1:用第:用第1个数与第个数与第2个数比较,若前者小则两数不变,个数比较,若前者小则两数不变,否则,交换这两个数的位置。否则,交换这两个数的位置。S2:按这样的原则,比较第:按这样的原则,比较第2个数和第个数和第3个数,前者小个数,前者小则两数不变,否则,交换这两个数的位置则两数不变,否则,交换这两个数的
展开阅读全文