案例1辗转相除法与更相减损术

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)用更相减损术求最大公约数.

思想方法:递归思想.


相关文章

  • 第8课时-§1.3算法案例--辗转相除法与更相减损术
  • 课题:§1.3算法案例--辗转相除法与更相减损术 教学目标: 知识与能力:理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析:基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序. 过程与方法:在辗转相除 ...查看


  • 人教版高二年级算法案例的教学设计
  • 人教版高二年级"算法案例--辗转相除法与更相减损术"的教学设计 松滋市贺炳炎中学 袁文 [email protected] 1. 内容和内容解析 (1)内容: 本节内容选自人教版普通高中课程标准实验教科书必修3第一章第3节 ...查看


  • 必修3-1-9秦九韶算法
  • 秦九韶算法 编号:必修3-1-9 内容: P37-39 学习目标:理解秦九韶算法,能够利用秦九韶算法求多项式函数的值,通过秦九韶算法案例的学习,进一步体会算法思想. 学习重点:秦九韶算法求多项式函数的值. 导学过程: 一.复习回忆: 1.辗 ...查看


  • 必修三 算法
  • 流程图 算法:是按照一定规则解决某一类问题的明确和有限的步骤. 算法的特征: . . 流程图:是由一些图框和带箭头的流线组成的,其中图框表示各种操作的类型,图框中的文字和符号表示操作的内容,带箭头的流线表示操作的先后次序 程序框图的基本图形 ...查看


  • 高中数学必修三算法初步习题
  • 必修三第一章算法初步 1.程序框图的运算结果为( ) 2.下面给出的是计算 1111+++...+的值的一个程序框图,其中判断框内应填入 24620 件是( ) 3.下列流程图中,语句1被执行的次数为( ) 4.下图给出的是计算 1111 ...查看


  • 高中数学-算法(基础练习)
  • 高中数学-算法(基础练习) [知识点1]基本概念 1. 算法:广义的算法--某一工作的方法和步骤. 数学中的"算法"是指可以用计算机来解决的某一类问题的程序. 2. 算法三要素:明确性,可行性,有限性. 例题. 给出求1 ...查看


  • [转载]收藏最齐全的高中数学同步教学(辅导)视频
  • 人教版必修一 1.     1.1.1集合的含义与表示(讲授新课) -必修1 2.     1.1.1集合的含义与表示(1)(巩固)-必修1 3.     1.1.1集合的含义与表示(2)(巩固)-必修1 4.     1.1.1集合的基本 ...查看


  • 第一学期计划高中数学必修一和必修三
  • 高一数学第一学期教学工作计划 (2013-2014学年度) 李 海 燕 太原市第五十九中学校 2013.09 高一数学第一学期教学工作计划 2013.9-2013.1 一.学情分析 高一131班全班50人,男生20人,女生30人,高一132 ...查看


  • 数学必修三
  • 第一章 算法初步 ⑴ 算法的特点:明确.有限. ⑵ 画程序框图的规则:①完整的框图必须有终端框,用于表示程序的开始.结束: ②使用标准的图形符号: ③框图一般按从上到下.从左到右的方向画: ④除判断框外,大多数流程图符号只有一个进入点和一个 ...查看


热门内容