搜索
1一种科学只有在成功地运用数学时,才算达到完善的地步数学,科学的皇后;数论,数学的皇后算法是数学及其应用的重要组成部分，是计算科学的重要基础数学是科学的大门和钥匙2问题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,18)=6这就是求两个正整数的最大公约数的古老有效的算法---辗转相除法（欧几里得算法）§1.3.1算法案例---辗转相除法和更相减损术3•8251=6105×1+2146•6105=2146×2+1813•2146=1813×1+333•1813=333×5+148•333=148×2+37•148=37×4+0•gcd(8251,6105)=372：gcd(8251,6105)=?§1.3.1算法案例---辗转相除法和更相减损术思考1：你能用自然语言描述用辗转相除法求8251和6105的最大公约数的算法步骤吗？4思考：2，你能把辗转相除法求任意两个正整数m,n(mn)的最大公约数编成一个计算机程序吗？§1.3.1算法案例---辗转相除法和更相减损术5写算法步骤：•第一步，给定两个正整数m,n•第二步，计算m除以n的余数为r•第三步，m=n,n=r•第四步，若r=0,则m,n的最大公约数等于m,否则，返回第二步。§1.3.1算法案例---辗转相除法和更相减损术6画程序框图•关键：确定框图中所用到的结构•确定循环结构：1，初始化条件：m,n2，确定循环体：m=n×q+rm=n,n=r3，设置循环控制条件：r=0•循环结构的类型选择：直到型或当型§1.3.1算法案例---辗转相除法和更相减损术7编制程序:•直到型：INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND§1.3.1算法案例---辗转相除法和更相减损术8当型结构：INPUTm,nr=1WHILEr＞0r=mMODnm=nn=rWENDPRINTmEND只要r≠0都可以§1.3.1算法案例---辗转相除法和更相减损术9自主学习1，请阅读P36–P37《九章算术》中介绍的“更相减损术”求两个正整数的最大公约数的算法。并体会例题1求98和63的最大公约数的过程，设计程序。§1.3.1算法案例---辗转相除法和更相减损术10程序参考：m=98n=63DOd=ABS(m-n)m=nn=dLOOPUNTILd=0PRINTmEND§1.3.1算法案例---辗转相除法和更相减损术112，你能根据更相减损术设计程序框图和程序，求两个任意正整数m,n的最大公约数吗？§1.3.1算法案例---辗转相除法和更相减损术1，用更相减损术完成求104与260的最大公约数，同时设计算法的程序框图和程序？探究：12小结•1，体会算法解决问题的全过程•2，体会中国古代数学的辉煌成果和对世界数学发展所做的贡献。13再见！14§1.3.1算法案例---辗转相除法和更相减损术1，算法的概念：知识回顾：算法是指按照一定规则解决某一类问题的明确和有限步骤2，设计算法所经历的全过程是？写算法步骤编制程序画程序框图体现了算法“逐步精确”的过程