第一章　算法初步

1.3　算法案例

1.3　算法案例(第1课时)--辗转相除法与更相减损术

学习目标

　　1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析.

　　2.基本上能根据程序框图与算法语句的知识设计完整的程序框图并写出算法程序.

合作学习

　　一、设计问题,创设情境

　　问题1:18与30的最大公约数是多少?你是怎样得到的?

　　问题2:如何求两个正数8 251和6 105的最大公约数?

　　二、信息交流,揭示规律

　　导引1:对于8 251与6 105这两个数,由于其公有的质因数较大,利用前面的方法求最大公约数比较困难.注意到8 251=6 105×1+2 146,那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系呢?

　　导引2:又6 105=2 146×2+1 813,同理,6 105与2 146的最大公约数和2 146与1 813的最大公约数相等.重复上述操作,你能得到8 251与6 105这两个数的最大公约数吗?

　　问题3:设两个正整数m>n,若m-n=k,则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理,可求得98与63的最大公约数为多少?