120622高一数学辗转相除法与更相减损术课件

20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法和更相减损法辗转相除法和更相减损法20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 151.求两个正整数的最大公约数求两个正整数的最大公约数 (1)求求18和和30的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 151.求两个正整数的最大公约数求两个正整数的最大公约数 (1)求求18和和30的最大公约数的最大公约数 18和和30的最大公约数为的最大公约数为6 (18,30)=620122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 151.求两个正整数的最大公约数求两个正整数的最大公约数 (1)求求18和和30的最大公约数的最大公约数 18和和30的最大公约数为的最大公约数为6 (18,30)=6 求公因数的方法求公因数的方法:先用两个数公有的先用两个数公有的质因数连续去除质因数连续去除,一直除到所得的商是互一直除到所得的商是互质数为止质数为止,然后把所有的除数连乘起来然后把所有的除数连乘起来.20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 151.求两个正整数的最大公约数求两个正整数的最大公约数 (1)求求18和和30的最大公约数的最大公约数 18和和30的最大公约数为的最大公约数为6 (18,30)=6 求公因数的方法求公因数的方法:先用两个数公有的先用两个数公有的质因数连续去除质因数连续去除,一直除到所得的商是互一直除到所得的商是互质数为止质数为止,然后把所有的除数连乘起来然后把所有的除数连乘起来.2.求求8251和和6105的最大公约数的最大公约数 (8251,6105)=?20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法辗转相除法(欧几里得算法欧几里得算法)20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法辗转相除法(欧几里得算法欧几里得算法)观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公的最大公约数的过程约数的过程20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法辗转相除法(欧几里得算法欧几里得算法)观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公的最大公约数的过程约数的过程 第一步第一步 用两数中较大的数除以较小的数，用两数中较大的数除以较小的数，求得商和余数求得商和余数8251=61051+214620122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法辗转相除法(欧几里得算法欧几里得算法)观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公的最大公约数的过程约数的过程 第一步第一步 用两数中较大的数除以较小的数，用两数中较大的数除以较小的数，求得商和余数求得商和余数8251=61051+2146 结论：结论：8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，的最大公约数，只要求出只要求出6105和和2146的公约数就可以了。的公约数就可以了。(8251,6105)=(6105,2146)20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法 6105=21462+1813 同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。(8251,6105)=(6105,2146)=(2146,1813)20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法 6105=21462+1813 同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。(8251,6105)=(6105,2146)=(2146,1813)思考：从上述的过程你体会到了什么？思考：从上述的过程你体会到了什么？20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+214620122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+181320122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+33320122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+14820122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+3720122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90135=901+45完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90135=901+4590=452完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90135=901+4590=452完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数 显然显然45是是90和和45的的最大公约数，也就是最大公约数，也就是225和和135的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90135=901+4590=452完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数 显然显然45是是90和和45的的最大公约数，也就是最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1:从上面的两从上面的两个例子可以看出计算的个例子可以看出计算的规律是什么？规律是什么？20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90135=901+4590=452完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数 显然显然45是是90和和45的的最大公约数，也就是最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1:从上面的两从上面的两个例子可以看出计算的个例子可以看出计算的规律是什么？规律是什么？20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15225=1351+90135=901+4590=452完整的过程完整的过程8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最的最大公约数，也就是大公约数，也就是8251和和6105的最大公约数的最大公约数例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数 显然显然45是是90和和45的的最大公约数，也就是最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1:从上面的两从上面的两个例子可以看出计算的个例子可以看出计算的规律是什么？规律是什么？20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考1：从上面的两个例子可以看：从上面的两个例子可以看出计算的规律是什么？出计算的规律是什么？S1：用大数除以小数：用大数除以小数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考1：从上面的两个例子可以看：从上面的两个例子可以看出计算的规律是什么？出计算的规律是什么？S1：用大数除以小数：用大数除以小数S2：除数除数变成变成被除数被除数，余数余数变成变成除数除数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考1：从上面的两个例子可以看：从上面的两个例子可以看出计算的规律是什么？出计算的规律是什么？S1：用大数除以小数：用大数除以小数S2：除数除数变成变成被除数被除数，余数余数变成变成除数除数S3：重复：重复S1，直到余数为，直到余数为020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考2：辗转相除法中的关键步骤是：辗转相除法中的关键步骤是哪种逻辑结构？哪种逻辑结构？8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考2：辗转相除法中的关键步骤是：辗转相除法中的关键步骤是哪种逻辑结构？哪种逻辑结构？m=nq+r8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考2：辗转相除法中的关键步骤是：辗转相除法中的关键步骤是哪种逻辑结构？哪种逻辑结构？辗转相除法是一个反复辗转相除法是一个反复执行直到余数等于执行直到余数等于0停止的步停止的步骤骤,这实际上是一个循环结构。这实际上是一个循环结构。m=nq+r8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考2：辗转相除法中的关键步骤是：辗转相除法中的关键步骤是哪种逻辑结构？哪种逻辑结构？辗转相除法是一个反复辗转相除法是一个反复执行直到余数等于执行直到余数等于0停止的步停止的步骤骤,这实际上是一个循环结构。这实际上是一个循环结构。用程序框图表示出右边的过程用程序框图表示出右边的过程m=nq+r8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 思考思考2：辗转相除法中的关键步骤是：辗转相除法中的关键步骤是哪种逻辑结构？哪种逻辑结构？辗转相除法是一个反复辗转相除法是一个反复执行直到余数等于执行直到余数等于0停止的步停止的步骤骤,这实际上是一个循环结构。这实际上是一个循环结构。用程序框图表示出右边的过程用程序框图表示出右边的过程m=nq+r8251=61051+21466105=21462+18132146=18131+3331813=3335+148333=1482+37148=374+020122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法的程序辗转相除法的程序20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15辗转相除法的程序辗转相除法的程序INPUT 输入输入m,n;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT 最大公约数是最大公约数是:;mEND 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15九章算术九章算术更相减损术更相减损术 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 算理算理:可半者半之可半者半之,不可半者不可半者,副置分母、副置分母、子之数子之数,以少减多以少减多,更相减损更相减损,求其等也求其等也,以以等数约之。等数约之。九章算术九章算术更相减损术更相减损术 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 算理算理:可半者半之可半者半之,不可半者不可半者,副置分母、副置分母、子之数子之数,以少减多以少减多,更相减损更相减损,求其等也求其等也,以以等数约之。等数约之。第一步第一步:任意给定两个正整数；判断他任意给定两个正整数；判断他们是否都是偶数。若是，则用们是否都是偶数。若是，则用2约简；若约简；若不是则执行第二步。不是则执行第二步。九章算术九章算术更相减损术更相减损术 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15 算理算理:可半者半之可半者半之,不可半者不可半者,副置分母、副置分母、子之数子之数,以少减多以少减多,更相减损更相减损,求其等也求其等也,以以等数约之。等数约之。第一步第一步:任意给定两个正整数；判断他任意给定两个正整数；判断他们是否都是偶数。若是，则用们是否都是偶数。若是，则用2约简；若约简；若不是则执行第二步。不是则执行第二步。第二步第二步:以较大的数减较小的数以较大的数减较小的数,接着把所接着把所得的差与较小的数比较得的差与较小的数比较,并以大数减小数。并以大数减小数。继续这个操作继续这个操作,直到所得的减数和差相等为直到所得的减数和差相等为止止,则这个等数就是所求的最大公约数。则这个等数就是所求的最大公约数。九章算术九章算术更相减损术更相减损术 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：解：由于由于63不是偶数，把不是偶数，把98和和63以大数以大数减小数，并辗转相减减小数，并辗转相减 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：解：由于由于63不是偶数，把不是偶数，把98和和63以大数以大数减小数，并辗转相减减小数，并辗转相减 98-63=3563-35=2835-28=728-7=2121-7=1414-7=720122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15所以，所以，98和和63的最大公约数等于的最大公约数等于7例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：解：由于由于63不是偶数，把不是偶数，把98和和63以大数以大数减小数，并辗转相减减小数，并辗转相减 98-63=3563-35=2835-28=728-7=2121-7=1414-7=720122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15练习：练习：课本课本P48第第1题题 用辗转相除法求下列两数的最大公用辗转相除法求下列两数的最大公约数，并用更相减损术检验你的结果。约数，并用更相减损术检验你的结果。（1）228，1995；（2）5280，12155.20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15数书九章数书九章秦九韶算法秦九韶算法20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150111)(axaxaxaxfnnnn 数书九章数书九章秦九韶算法秦九韶算法设设f(x)是一个是一个n次的多项式次的多项式20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150111)(axaxaxaxfnnnn0111)(axaxaxaxfnnnn 01211)(axaxaxannnn 012312)(axaxaxaxannnn 数书九章数书九章秦九韶算法秦九韶算法设设f(x)是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150111)(axaxaxaxfnnnn 0111)(axaxaxaxfnnnn 01211)(axaxaxannnn 012312)(axaxaxaxannnn 数书九章数书九章秦九韶算法秦九韶算法设设f(x)是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150111)(axaxaxaxfnnnn 0111)(axaxaxaxfnnnn 01211)(axaxaxannnn 012312)(axaxaxaxannnn 0121)(axaxaxaxannn 数书九章数书九章秦九韶算法秦九韶算法设设f(x)是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150111)(axaxaxaxfnnnn 0111)(axaxaxaxfnnnn 01211)(axaxaxannnn 012312)(axaxaxaxannnn 0121)(axaxaxaxannn 数书九章数书九章秦九韶算法秦九韶算法设设f(x)是一个是一个n次的多项式次的多项式对该多项式按下面的方式进行改写：对该多项式按下面的方式进行改写：20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150121)()(axaxaxaxaxfnnn 20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150121)()(axaxaxaxaxfnnn 11 nnaxav要求多项式的值要求多项式的值,应该先算最内层的一次多应该先算最内层的一次多项式的值项式的值,即即20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150121)()(axaxaxaxaxfnnn 11 nnaxav212 naxvv323 naxvv01axvvnn 要求多项式的值要求多项式的值,应该先算最内层的一次多应该先算最内层的一次多项式的值项式的值,即即然后然后,由内到外逐层计算一次多项式的值由内到外逐层计算一次多项式的值,即即20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150121)()(axaxaxaxaxfnnn 11 nnaxav212 naxvv323 naxvv01axvvnn 要求多项式的值要求多项式的值,应该先算最内层的一次多应该先算最内层的一次多项式的值项式的值,即即然后然后,由内到外逐层计算一次多项式的值由内到外逐层计算一次多项式的值,即即20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 150121)()(axaxaxaxaxfnnn 11 nnaxav212 naxvv323 naxvv01axvvnn 要求多项式的值要求多项式的值,应该先算最内层的一次多应该先算最内层的一次多项式的值项式的值,即即然后然后,由内到外逐层计算一次多项式的值由内到外逐层计算一次多项式的值,即即这种将求一个这种将求一个n次多项式次多项式f(x)的值转化成求的值转化成求n个一次多项式的值的方法个一次多项式的值的方法,称为称为秦九韶算法秦九韶算法20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 158.07.16.25.325)(2345 xxxxxxf例例2 已知一个五次多项式为已知一个五次多项式为用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值的值.20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15解：将多项式变形：解：将多项式变形：8.0)7.1)6.2)5.3)25()(xxxxxxf20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15解：将多项式变形：解：将多项式变形：8.0)7.1)6.2)5.3)25()(xxxxxxf272551 v50 v5.1385.35272 v9.6896.255.1383 v2.34517.159.6894 v2.172558.052.34515 v按由里到外的顺序按由里到外的顺序,依此计算一次多项式依此计算一次多项式当当x=5时的值时的值:20122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15解：将多项式变形：解：将多项式变形：8.0)7.1)6.2)5.3)25()(xxxxxxf272551 v50 v5.1385.35272 v9.6896.255.1383 v2.34517.159.6894 v2.172558.052.34515 v按由里到外的顺序按由里到外的顺序,依此计算一次多项式依此计算一次多项式当当x=5时的值时的值:所以所以,当当x=5时时,多项式的值等于多项式的值等于17255.220122012年上学期年上学期湖南长郡卫星远程学校湖南长郡卫星远程学校制作制作 15作业：学法大视野作业：学法大视野