网站地图
【www.arisingsemi.com--语言培训】
秦九昭 高一数学学案 序号___067__ 高一 年级 _1、6___ 班 教师 张杰 学生 _____
课 题 1.3 算法案例————辗转相除法、更相减损术与秦九韶算法
一、学习目的
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2．了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。
3.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
二、学习重点、难点
重点：理解辗转相除法与更相减损术求最大公约数的方法。理解秦九韶算法的思想。
难点：把辗转相除法与更相减损术、秦九韶算法的方法转换成程序框图与程序语言。
三、学习过程
复习回顾
直到型循环与当型循环的程序语言分别是什么。
知识探究
（一）:辗转相除法
思考
1:18与30的最大公约数是多少。
你是怎样得到的。
思考
2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系。
思考
3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗。
例
1：用辗转相除法求225和135的最大公约数
练习：利用辗转相除法求两数4081与20723的最大公约数.
思考
4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法。
其算法步骤如何设计。
第一步，给定两个正整数m，n(m>n).
第二步，
第三步，
第四步，
第五步，
思考
5:该算法的程序框图如何表示。 思考
6:该程序框图对应的程序如何表述。
思考
7：如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n
的最大公约数的程序框图和程序分别如何表示。
知识探究
（二）:更相减损术
思考
1:设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少。
练习：用更相减损术求两个正数84与72的最大公约数
思考
2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法。其算法步骤如何设计。
第一步，给定两个正整数m，n(m>n).
第二步，
第三步，
第四步，
第五步，
思考
3:该算法的程序框图如何表示。
思考
4:该程序框图对应的程序如何表述。
知识探究
（三）:辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以 为主，更相减损术以 为主，计算次数上辗转相除法计算次数相对 ，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是 则得到，而更相减损术则以 相等而得到
例2 分别用辗转相除法和更相减损术求168与93的最大公约数.
辗转相除法：
更相减损术:
例3 求325，130，270三个数的最大公约数.
知识探究(四):秦九韶算法的基本思想
思考
1:对于多项式，求的值. 若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算。
思考
2:在上述问题中，若先计算的值，然后依次计算，，的值，这样每次都可以利用上一次计算的结果，那么一共做了多少次乘法运算和多少次加法运算。
小结：第二种做法和第一种做法相比，乘法的运算次数减少了，因而能提高运算效率。而且对于计算机来说，做一次乘法运算所需的时间比做一次加法运算需要的时间要长得多，
因此第二种算法能更快的得到结果。
思考
3:对于多项式表示为的形式，则由内向外逐层计算一次多项式的值，其算法步骤如何。一共做多少次乘法运算和多少次加法运算。
思考
4:上述求多项式的值的方法称为秦九韶算法，利用该算法求的值，一共需要多少次乘法运算，多少次加法运算。
思考
5:在秦九韶算法中，记那么第步的算式是什么。
高一数学学案 序号___067__ 高一 年级 _
1、6___ 班 教师 张杰 学生 _____
课 题 1.3 算法案例————辗转相除法、更相减损术与秦九韶算法
知识探究(五):秦九韶算法的程序设计
思考
1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法。其算法步骤如何设计。
第一步，
第二步，
第三步，
第四步，
第五步，
思考
2:该算法的程序框图如何表示。 思考
3:该程序框图对应的程序如何表述。
例4 已知一个5次多项式为 用秦九韶算法求的值.
练习： 阅读下列程序，说明它解决的实际问题是什么。
INPUT “x=”；a
n=0
y=0
WHLE n