1.3 算法案例
编写人:丁建龙
第1课时 案例1 辗转相除法与更相减损术
教学目标:
(1)知识与技能:
①理解辗转相除法、更相减损术原理;
②能用自然语言、流程图和伪代码表达辗转相除法、更相减损术;
③能应用迭代算法思想。
(2)过程与方法:
①培养学生把具体问题抽象转化为算法语言的能力;
②培养学生自主探索和合作学习的能力。
(3)情感、态度和价值观:
①使学生进一步了解从具体到抽象,抽象到具体的辨证思想方法,对学生进行辨证唯物主义教育;
②创设和谐融洽的教学氛围和阶梯形问题,使学生在活动中获得成功感,从而培养学生热爱数学、积极学习数学、应用数学的热情。
重点难点
教学重点:引导学生得出自己设计的算法步骤、程序框图和算法程序.
教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.
新知探究
提出问题
(1)怎样用短除法求最大公约数?
(2)怎样用穷举法(也叫枚举法)求最大公约数?
(3)怎样用辗转相除法求最大公约数?
(4)怎样用更相减损术求最大公约数?
讨论结果:
(1)短除法
求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得的商是两个互质数为止,然后把所有的除数连乘起来.
(2)穷举法(也叫枚举法)
穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.
(3)辗转相除法
辗转相除法求两个数的最大公约数,其算法步骤可以描述如下:
第一步,给定两个正整数m,n.
第二步,求余数r:计算m除以n,将所得余数存放到变量r中.
第三步,更新被除数和余数:m=n,n=r.
第四步,判断余数r是否为0.若余数为0,则输出结果;否则转向第二步继续循环执行.
如此循环,直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.
(4)更相减损术
我国早期也有解决求最大公约数问题的算法,就是更相减损术. 《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现代语言如下:
第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简;若不是,执行第二步.
第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
应用示例
例1 用辗转相除法求8 251与6 105的最大公约数,写出算法分析,画出程序框图,写出算法程序.
变式训练
你能用当型循环结构构造算法,求两个正整数的最大公约数吗?试画出程序框图和程序.
例2 用更相减损术求98与63的最大公约数.
例3 (1)用辗转相除法求123和48的最大公约数.
(2)用更相减损术求80和36的最大公约数.
知能训练
求319,377,116的最大公约数.
课堂小结
(1)用辗转相除法求最大公约数.
(2)用更相减损术求最大公约数.
思想方法:递归思想.
1.3 算法案例
编写人:丁建龙
第1课时 案例1 辗转相除法与更相减损术
教学目标:
(1)知识与技能:
①理解辗转相除法、更相减损术原理;
②能用自然语言、流程图和伪代码表达辗转相除法、更相减损术;
③能应用迭代算法思想。
(2)过程与方法:
①培养学生把具体问题抽象转化为算法语言的能力;
②培养学生自主探索和合作学习的能力。
(3)情感、态度和价值观:
①使学生进一步了解从具体到抽象,抽象到具体的辨证思想方法,对学生进行辨证唯物主义教育;
②创设和谐融洽的教学氛围和阶梯形问题,使学生在活动中获得成功感,从而培养学生热爱数学、积极学习数学、应用数学的热情。
重点难点
教学重点:引导学生得出自己设计的算法步骤、程序框图和算法程序.
教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.
新知探究
提出问题
(1)怎样用短除法求最大公约数?
(2)怎样用穷举法(也叫枚举法)求最大公约数?
(3)怎样用辗转相除法求最大公约数?
(4)怎样用更相减损术求最大公约数?
讨论结果:
(1)短除法
求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得的商是两个互质数为止,然后把所有的除数连乘起来.
(2)穷举法(也叫枚举法)
穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.
(3)辗转相除法
辗转相除法求两个数的最大公约数,其算法步骤可以描述如下:
第一步,给定两个正整数m,n.
第二步,求余数r:计算m除以n,将所得余数存放到变量r中.
第三步,更新被除数和余数:m=n,n=r.
第四步,判断余数r是否为0.若余数为0,则输出结果;否则转向第二步继续循环执行.
如此循环,直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.
(4)更相减损术
我国早期也有解决求最大公约数问题的算法,就是更相减损术. 《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现代语言如下:
第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简;若不是,执行第二步.
第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
应用示例
例1 用辗转相除法求8 251与6 105的最大公约数,写出算法分析,画出程序框图,写出算法程序.
变式训练
你能用当型循环结构构造算法,求两个正整数的最大公约数吗?试画出程序框图和程序.
例2 用更相减损术求98与63的最大公约数.
例3 (1)用辗转相除法求123和48的最大公约数.
(2)用更相减损术求80和36的最大公约数.
知能训练
求319,377,116的最大公约数.
课堂小结
(1)用辗转相除法求最大公约数.
(2)用更相减损术求最大公约数.
思想方法:递归思想.