高中数学 算法案例课件 新人教版必修3.ppt

《高中数学 算法案例课件 新人教版必修3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一种科学只有在成功地运用数学时,才算达到完善的地步数学,科学的皇后;数论,数学的皇后算法是数学及其应用的重要组成部分，是计算科学的重要基础数学是科学的大门和钥匙§1.3.1算法案例---辗转相除法和更相减损术1问题1：（1）求30和18的最大公约数，即gcd(18,30)=?（2）求gcd(8251,6105)=?gcd(30,18)=gcd(18,12)解法二：30=18×1+12(1)解法一：（小学已学的短除法）18=12×1+6gcd(18,12)=gcd(12,6)12=6×2＋0gcd(12,6)=6即gcd(30

2、,18)=6这就是求两个正整数的最大公约数的古老有效的算法---辗转相除法（欧几里得算法）§1.3.1算法案例---辗转相除法和更相减损术28251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0gcd(8251,6105)=372：gcd(8251,6105)=?§1.3.1算法案例---辗转相除法和更相减损术思考1：你能用自然语言描述用辗转相除法求8251和6105的最大公约数的算法步骤吗？3思考：2，你能把辗转

3、相除法求任意两个正整数m,n(m>n)的最大公约数编成一个计算机程序吗？§1.3.1算法案例---辗转相除法和更相减损术4写算法步骤：第一步，给定两个正整数m,n第二步，计算m除以n的余数为r第三步，m=n,n=r第四步，若r=0,则m,n的最大公约数等于m,否则，返回第二步。§1.3.1算法案例---辗转相除法和更相减损术5画程序框图关键：确定框图中所用到的结构确定循环结构：1，初始化条件：m,n2，确定循环体：m=n×q+rm=n,n=r3，设置循环控制条件：r=0循环结构的类型选择：直到型或当型§1.3.1算法案例--

4、-辗转相除法和更相减损术6编制程序:直到型：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND§1.3.1算法案例---辗转相除法和更相减损术7当型结构：INPUTm,nr=1WHILEr＞0r=mMODnm=nn=rWENDPRINTmEND只要r≠0都可以§1.3.1算法案例---辗转相除法和更相减损术8自主学习1，请阅读P36–P37《九章算术》中介绍的“更相减损术”求两个正整数的最大公约数的算法。并体会例题1求98和63的最大公约数的过程，设计程序。§1.3.1算法案例---辗转

5、相除法和更相减损术9程序参考：m=98n=63DOd=ABS(m-n)m=nn=dLOOPUNTILd=0PRINTmEND§1.3.1算法案例---辗转相除法和更相减损术102，你能根据更相减损术设计程序框图和程序，求两个任意正整数m,n的最大公约数吗？§1.3.1算法案例---辗转相除法和更相减损术1，用更相减损术完成求104与260的最大公约数，同时设计算法的程序框图和程序？探究：11小结1，体会算法解决问题的全过程2，体会中国古代数学的辉煌成果和对世界数学发展所做的贡献。12再见！13§1.3.1算法案例---辗转相

6、除法和更相减损术1，算法的概念：知识回顾：算法是指按照一定规则解决某一类问题的明确和有限步骤2，设计算法所经历的全过程是？写算法步骤编制程序画程序框图体现了算法“逐步精确”的过程14