经全国中小学教材审定委员会 0o4年初审通过 普通高中课程标准实验教科书 数孥e 人民教育出版社课程教材研究所 中学数学课程教材研究开发中心 《1.3秦九韶算法与进位制(1)》 ◆教材分析 在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序语句三种 不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在 解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数 学表达能力。秦九韶算法是我国古代数学中的著名算法,其中蕴含的算法思想深刻,也更能 体现算法的重要性:与进位制有关的算法是计算机科学中普遍使用的算法,其中蕴含的算法 思想深刻,也更能体现算法的重要性 ◆教学目标 【知识与能力目标】 了解秦九韶算法的计算过程,并理解利用秦九韶算法可以减少计算次数,提高计算效率 的实质:了解各种进位制与十进制之间转换的规律,会利用各种进位制与十进制之间的联系 进行各种进位制之间的转换。 【过程与方法目标】 学习秦九韶算法在多项式求值中的应用,并理解其中的数学规律;学习各种进位制转 换成十进制的计算方法,研究十进制转换为各种进位制的除k取余法,并理解其中的数学规 律
《1.3 秦九韶算法与进位制(1)》 在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序语句三种 不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在 解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数 学表达能力。秦九韶算法是我国古代数学中的著名算法,其中蕴含的算法思想深刻,也更能 体现算法的重要性;与进位制有关的算法是计算机科学中普遍使用的算法,其中蕴含的算法 思想深刻,也更能体现算法的重要性。 【知识与能力目标】 了解秦九韶算法的计算过程,并理解利用秦九韶算法可以减少计算次数,提高计算效率 的实质;了解各种进位制与十进制之间转换的规律,会利用各种进位制与十进制之间的联系 进行各种进位制之间的转换。 【过程与方法目标】 学习秦九韶算法在多项式求值中的应用,并理解其中的数学规律;学习各种进位制转 换成十进制的计算方法,研究十进制转换为各种进位制的除 k 取余法,并理解其中的数学规 律。 ◆ 教材分析 ◆ 教学目标
【情感态度价值观目标】 理解秦九韶算法,领悟十进制、二进制的特点,培养学生热爱生活勤于实践的品质。 ◆教学重难点 【教学重点】 秦九韶算法的特点及其程序设计:各进位制表示数的方法及各进位制之间的转换。 【教学难点】 对秦九韶算法的先进性及其程序设计的理解:对除k取余法理解以及各进位制之间转换的 程序框图的设计。 ◆课前准备 电子课件调整、相应的教具带好、熟悉学生名单、电子白板要调试好。 ◆教学过程 、导入部分 设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法程序 设计意图:从生活实际切入,激发了学生的学习兴趣,又为新知作好铺垫。 、研探新知,建构概念 1.电子白板投影出实例。 y=2*x5-5*x4-4*x3+3*x2-6*x+7 PRINT y END 上述算法一共做了15次乘法运算,5次加法运算。优点是简单,易懂;缺点是不通用,不能 解决任意多项多求值问题,而且计算效率不高。那么有没有更高效的算法? 2.教师组织学生分组讨论:先让学生分析,师生一起归纳 (1)秦九韶算法的定义:一般地,对于一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+ ao,我们可以改写成如下形式:f(x)=((anx+an-1)x+an-2)x+…+a1)x+ao
【情感态度价值观目标】 理解秦九韶算法,领悟十进制、二进制的特点,培养学生热爱生活勤于实践的品质。 【教学重点】 秦九韶算法的特点及其程序设计;各进位制表示数的方法及各进位制之间的转换。 【教学难点】 对秦九韶算法的先进性及其程序设计的理解;对除 k 取余法理解以及各进位制之间转换的 程序框图的设计。 电子课件调整、相应的教具带好、熟悉学生名单、电子白板要调试好。 一、导入部分 设计求多项式f(𝑥) = 2𝑥 5 − 5𝑥 4 − 4𝑥 3 + 3𝑥 2 − 6𝑥 + 7当 x=5 时的值的算法程序。 设计意图:从生活实际切入,激发了学生的学习兴趣,又为新知作好铺垫。 二、研探新知,建构概念 1.电子白板投影出实例。 x=5 y=2*x^5-5*x^4-4*x^3+3*x^2-6*x+7 PRINT y END 上述算法一共做了 15 次乘法运算,5 次加法运算。优点是简单,易懂;缺点是不通用,不能 解决任意多项多求值问题,而且计算效率不高。那么有没有更高效的算法? 2.教师组织学生分组讨论:先让学生分析,师生一起归纳。 (1)秦九韶算法的定义:一般地,对于一个 n 次多项式f(x) = 𝑎𝑛𝑥 𝑛 + 𝑎𝑛−1𝑥 𝑛−1 + ⋯ + 𝑎1𝑥 + 𝑎0,我们可以改写成如下形式: f(x) = (… (𝑎𝑛x + 𝑎𝑛−1 )x + 𝑎𝑛−2 )x + ⋯ + 𝑎1 )𝑥 + 𝑎0 ◆ 教学重难点 ◆ ◆ 课前准备 ◆ ◆ 教学过程
求多项式的值时,首先计算最内层括号内一次多项式的值,即1=anx+an-1,然后由内向 外逐层计算一次多项式的值,即v2=v1x+an-2,U3=12x+an-3,…1n2=vn-1x+a0;这 样,求n次多项式f(x)的值就转化为求n个一次多项式的值。这种算法称为秦九韶算法。 (2)秦九韶算法的用处是什么?秦九韶算法是求一元多项式的值的一种方法。 (3)秦九韶算法的特点:把求一个n次多项式的值转化为求n个一次多项式的值,通过这 种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算 和n次加法运算,大大提高了运算效率。 设计意图:在自主探究,合作交流中构建新知,体验秦九韶算法的优点。 三、质疑答辩,发展思维 1、举例:用秦九韶算法求多项式f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值。 解:原多项式先化为:f(x)=2x6-5x5+0×x4-4x3+3x2-6x+0.在将多项式 改成如下的形式:f(x)=(((2x-5)x+0)x-4)x+3)x-6)x+0;按照从内到外的顺序, 依次计算一次多项式当x=5时的值。v1=2×5-5=5,v2=5×5+0 25,3=25×5-4=121,v4=121×5+3=608 vs=608×5-6=3034v6=3034×5+0=15170 2、思考1:观察上述秦九韶算法中的n个一次式,可见vk的计算要用到uk-1的值。怎么 用秦九韶算法求多项式的 k=vk-1x+ a (k=1,2,……n)这是一个在秦九韶算法中反 复执行的步骤,因此可用循环结构来实现。 INPUTal, a2, a3, a4,as NPUT v-a WHILE n<=5 V-vo as tan-5 n=n+1 PRiNT END 思考2:我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的。比 如时间和角度的单位用六十进位制,电子计算机用的是二进制。那么什么是进位制?不同的
求多项式的值时,首先计算最内层括号内一次多项式的值,即𝑣1 = 𝑎𝑛𝑥 + 𝑎𝑛−1,然后由内向 外逐层计算一次多项式的值,即𝑣2 = 𝑣1𝑥 + 𝑎𝑛−2, 𝑣3 = 𝑣2𝑥 + 𝑎𝑛−3,…𝑣𝑛 = 𝑣𝑛−1𝑥 + 𝑎0;这 样,求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值。这种算法称为秦九韶算法。 (2)秦九韶算法的用处是什么?秦九韶算法是求一元多项式的值的一种方法。 (3)秦九韶算法的特点:把求一个 n 次多项式的值转化为求 n 个一次多项式的值,通过这 种转化,把运算的次数由至多 n(n+1)/2 次乘法运算和 n 次加法运算,减少为 n 次乘法运算 和 n 次加法运算,大大提高了运算效率。 设计意图:在自主探究,合作交流中构建新知,体验秦九韶算法的优点。 三、质疑答辩,发展思维 1、举例:用秦九韶算法求多项式 f(𝑥) = 2𝑥 6 − 5𝑥 5 − 4𝑥 3 + 3𝑥 2 − 6𝑥当 x=5 时的值。 解:原多项式先化为: f(𝑥) = 2𝑥 6 − 5𝑥 5 + 0 × 𝑥 4 − 4𝑥 3 + 3𝑥 2 − 6𝑥 + 0.在将多项式 改成如下的形式:f(x)=(((((2x-5)x+0)x-4)x+3)x-6)x+0;按照从内到外的顺序, 依次计算一次多项式当 x=5 时的值。𝑣1 = 2 × 5 − 5 = 5, 𝑣2 = 5 × 5 + 0 = 25, 𝑣3 = 25 × 5 − 4 = 121, 𝑣4 = 121 × 5 + 3 = 608, 𝑣5 = 608 × 5 − 6 = 3034𝑣6 = 3034 × 5 + 0 = 15170; 2、思考 1: 观察上述秦九韶算法中的 n 个一次式,可见𝑣𝑘 的计算要用到𝑣𝑘−1 的值。怎么 用秦九韶算法求多项式的值{ 𝑣0 = 𝑎𝑛 𝑣𝑘 = 𝑣𝑘−1𝑥 + 𝑎𝑛−𝑘 (k=1,2,……n)这是一个在秦九韶算法中反 复执行的步骤,因此可用循环结构来实现。 INPUT𝑎1 ,𝑎2 , 𝑎3 ,𝑎4 ,𝑎5 INPUT 𝑥6 n=1 v= 𝑎5 WHILE n<=5 v=𝑣0 𝑎5 +𝑎𝑛−5 n=n+1 WEND PRINT v END 思考 2:我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的。比 如时间和角度的单位用六十进位制,电子计算机用的是二进制。那么什么是进位制?不同的
进位制之间又有什么联系呢? 进位制是人们为了计数和运算的方便而约定的一种记数系统,约定满二进一,就是二进制 满十进一,就是十进制:满十六进一,就是十六进制;等等。“满几进一”,就是几进制 几进制的基数就是几。可使用数字符号的个数称为基数。基数都是大于1的整数 如二进制可使用的数字有0和1,基数是2;十进制可使用的数字有0,1,2,…,8,9等十个数 字,基数是10;十六进制可使用的数字或符号有0-9等10个数字以及AF等6个字母(规定 字母AF对应10-15),十六进制的基数是16。 注意:为了区分不同的进位制,常在数字的右下脚标明基数,如100101表示二进制数, 34表示5进制数。十进制数一般不标注基数 思考3:k进制数怎么转化成十进制数? 其方法是先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式,即 1…a1a1(k)=an×kh+ kn-1+…+a1×k1+ 再按照十进制数的运算规则计算出结果。 思考4:十进制数怎么转化成k进制数? 其方法是除k取余法,用十进制数除以k进制数,将各步所得的余数从下到上排列,就会得 到相应的k进制数。 3、例题 例1求多项式f(x)=x5-x3+2x2-3在x=5时的函数值。 解:原多项式先化为:fx)=x5+0×x14-x3+2x2+0×x-3;在将多项式改成 如下的形式:f(x)=(((x+0)x-1)x+2)x+0)x-3.按照从内到外的顺序,依次计算 次多项式当x=5时的值 U1=1×5+0=5,12=5×5-1=24,13=24×5+2=122,v4=122×5+0=610 Us5=610×5-3=3047,所以多项式在x=5时的函数值为3047 例2把89化为五进制的数 解:以5作为除数,相应的除法算式为:5L89 余数 5|17 4 2 ∴89=3244 4、巩固练习
进位制之间又有什么联系呢? 进位制是人们为了计数和运算的方便而约定的一种记数系统,约定满二进一,就是二进制; 满十进一,就是十进制;满十六进一,就是十六进制;等等。 “满几进一”,就是几进制, 几进制的基数就是几。可使用数字符号的个数称为基数。基数都是大于 1 的整数。 如二进制可使用的数字有 0 和 1,基数是 2;十进制可使用的数字有 0,1,2,…,8,9 等十个数 字,基数是 10;十六进制可使用的数字或符号有 0-9 等 10 个数字以及 A-F 等 6 个字母(规定 字母 A-F 对应 10-15),十六进制的基数是 16。 注意:为了区分不同的进位制,常在数字的右下脚标明基数,如100101(2)表示二进制数, 34(5)表示 5 进制数。十进制数一般不标注基数。 思考 3:k 进制数怎么转化成十进制数? 其方法是先把 k 进制的数表示成不同位上数字与基数 k 的幂的乘积之和的形式,即 𝑎𝑛𝑎𝑛−1 … 𝑎1𝑎1(𝑘) = 𝑎𝑛 × 𝑘 𝑛 + 𝑎𝑛−1 × 𝑘 𝑛−1 + ⋯ + 𝑎1 × 𝑘 1 + 𝑎0 × 𝑘 0 再按照十进制数的运算规则计算出结果。 思考 4:十进制数怎么转化成 k 进制数? 其方法是除 k 取余法,用十进制数除以 k 进制数,将各步所得的余数从下到上排列,就会得 到相应的 k 进制数。 3、例题 例 1 求多项式𝑓(𝑥) = 𝑥 5 − 𝑥 3 + 2𝑥 2 − 3在𝑥 = 5时的函数值。 解:原多项式先化为: f(𝑥) = 𝑥 5 + 0 × 𝑥 4 − 𝑥 3 + 2𝑥 2 + 0 × 𝑥 − 3 ;在将多项式改成 如下的形式:f(x)=((((x+0)x-1)x+2)x+0)x-3.按照从内到外的顺序,依次计算 一次多项式当 x=5 时的值。 𝑣1 = 1 × 5 + 0 = 5, 𝑣2 = 5 × 5 − 1 = 24, 𝑣3 = 24 × 5 + 2 = 122, 𝑣4 = 122 × 5 + 0 = 610, 𝑣5 = 610 × 5 − 3 = 3047,所以多项式在𝑥 = 5时的函数值为 3047 例 2 把 89 化为五进制的数。 解:以 5 作为除数,相应的除法算式为: 5 89 余数 5 17 …… 4 5 3 …… 2 0 …… 3 ∴ 89 = 324(5) 4、巩固练习
(1)求多项式f(x)=4x5-3x4+2x2-x在x=5时的函数值 原多项式先化为:f(x)=4x5-3×x4+0×x3+2x2-1×x+0:在将多项式改成如 下的形式:f(x)=(((4x-3)x+0)x+2)x-1)x+0.按照从内到外的顺序,依次计算一次多项式当 5时的值 U1=4×5-3=17,v2=17×5+0=85,3=85×5+2=427,v4=427×5-1= 2134U5=2134×5+0=10670,所以多项式在x=5时的函数值为10670 (2)三进制数10221化为二进制数 解:第一步:先把三进制数化为十进制数 10221=1×34+0×3+2×32+2×32+1×3%=81+18+6+1=106 第二步:再把十进制数化为二进制数 2 余数 2 2|13 01010 106=1101010 10221=106=1101010 四、课堂小结: 1、秦九韶算法 2、进位制 五、作业布置: 课后书面作业:习题1.3A组第2和3题 ◆教学反思
(1) 求多项式𝑓(𝑥) = 4𝑥 5 − 3𝑥 4 + 2𝑥 2 − 𝑥在𝑥 = 5时的函数值。 解:原多项式先化为: f(𝑥) = 4𝑥 5 − 3 × 𝑥 4 + 0 × 𝑥 3 + 2𝑥 2 − 1 × 𝑥 + 0 ;在将多项式改成如 下的形式:f(x)=((((4x-3)x+0)x+2)x-1)x+0.按照从内到外的顺序,依次计算一次多项式当 x=5 时的值。 𝑣1 = 4 × 5 − 3 = 17 , 𝑣2 = 17 × 5 + 0 = 85 , 𝑣3 = 85 × 5 + 2 = 427 , 𝑣4 = 427 × 5 − 1 = 2134,𝑣5 = 2134 × 5 + 0 = 10670,所以多项式在𝑥 = 5时的函数值为 10670。 (2)三进制数 10221(3)化为二进制数 解:第一步:先把三进制数化为十进制数: 10221(3)=1×34 +0×33 +2×32 +2×31 +1×30 =81+18+6+1=106 第二步:再把十进制数化为二进制数: 2 106 余数 2 53 …… 0 2 26 …… 1 2 13 …… 0 2 6 …… 1 2 3 …… 0 2 1 …… 1 0 …… 1 106=1101010(2) ∴10221(3)=106=1101010(2) 四、课堂小结: 1、秦九韶算法 2、进位制 五、作业布置: 课后书面作业: 习题 1.3A 组第 2 和 3 题。 略。 ◆ 教学反思
《1.3辗转相除法与更相减损术(2)》 ◆教材分析 在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序语句三种 不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在 解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数 学表达能力。更相减损术是我国古代数学中的著名算法,而辗转相除法是西方古代数学中的 一个典型算法,其中蕴含的算法思想深刻,也更能体现算法的重要性。 ◆教学目标 【知识与能力目标】 理解辗转相除法与更相减损术所蕴涵的数学原理,并能根据这些原理进行算法分析,基 本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 【过程与方法目标】 利用辗转相除法与更相减损术求最大公约数的学习过程中,对比我们常见的约分求公因 式的方法,比较它们在算法上的区别,并从程序的学习中体会数学的严谨,领会数学算法计 算机处理的结合方式,初步掌握把数学算法转化成计算机语言的一般步骤 【情感态度价值观目标】 通过阅读中国古代数学家的算法案例,体会中国古代数学对世界数学发展的贡献,在学 习外国古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力,在利用算法解决 数学问题的过程中培养动手实践的能力 ◆教学重难点 【教学重点】 理解辗转相除和更相减损术求最大公约数的方法。 【教学难点】 把辗转相除和更相减损术转换成程序框图与程序语言
《1.3 辗转相除法与更相减损术(2)》 在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序语句三种 不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在 解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数 学表达能力。更相减损术是我国古代数学中的著名算法,而辗转相除法是西方古代数学中的 一个典型算法,其中蕴含的算法思想深刻,也更能体现算法的重要性。 【知识与能力目标】 理解辗转相除法与更相减损术所蕴涵的数学原理,并能根据这些原理进行算法分析,基 本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 【过程与方法目标】 利用辗转相除法与更相减损术求最大公约数的学习过程中,对比我们常见的约分求公因 式的方法,比较它们在算法上的区别,并从程序的学习中体会数学的严谨,领会数学算法计 算机处理的结合方式,初步掌握把数学算法转化成计算机语言的一般步骤。 【情感态度价值观目标】 通过阅读中国古代数学家的算法案例,体会中国古代数学对世界数学发展的贡献,在学 习外国古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力,在利用算法解决 数学问题的过程中培养动手实践的能力。 【教学重点】 理解辗转相除和更相减损术求最大公约数的方法。 【教学难点】 把辗转相除和更相减损术转换成程序框图与程序语言。 ◆ 教材分析 ◆ 教学目标 ◆ 教学重难点 ◆
◆课前准备 电子课件调整、相应的教具带好、熟悉学生名单、电子白板要调试好 ◆教学过程 导入部分 在小学,我们学过求最大公约数的知识,你能求出18与30的最大公约数吗? 先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连 乘起来。 18和30的最大公约数是2×3= 我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不 能得到一些公约数,我们又应该怎样求它们的最大公约数? 比如求8251与6105的最大公约数? 设计意图:从生活实际切入,激发了学生的学习兴趣,又为新知作好铺垫 二、研探新知,建构概念 1、电子白板投影出上述问题。 2、教师组织学生分组讨论:先让学生分析,师生一起归纳。 分析:8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据 已有的知识即可求出最大公约数。 8251=6105×1+2146 显然8251与6105的最大公约数也必是2146的约数,同样6105与2146的公约数也必是8251 的约数,所以8251与6105的最大公约数也是6105与2146的最大公约数。 6105=2146×2+1813; 2146=1813×1+333 183=333×5+148 333=148×2+37; 148=37×4+0 则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在 公元前300年左右首先提出的
电子课件调整、相应的教具带好、熟悉学生名单、电子白板要调试好。 一、导入部分 在小学,我们学过求最大公约数的知识,你能求出 18 与 30 的最大公约数吗? 先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连 乘起来。 ∴18 和 30 的最大公约数是 2×3=6 我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不 能得到一些公约数,我们又应该怎样求它们的最大公约数? 比如求 8251 与 6105 的最大公约数? 设计意图:从生活实际切入,激发了学生的学习兴趣,又为新知作好铺垫。 二、研探新知,建构概念 1、电子白板投影出上述问题。 2、教师组织学生分组讨论:先让学生分析,师生一起归纳。 分析:8251 与 6105 两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据 已有的知识即可求出最大公约数。 解:8251=6105×1+2146 显然 8251 与 6105 的最大公约数也必是 2146 的约数,同样 6105 与 2146 的公约数也必是 8251 的约数 ,所 以 8251 与 6105 的最 大公约 数也 是 6105 与 2146 的最 大公 约数。 6105=2146×2+1813; 2146=1813×1+333; 1813=333×5+148; 333=148×2+37; 148=37×4+0; 则 37 为 8251 与 6105 的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在 公元前 300 年左右首先提出的。 ◆ 教学过程
(1)利用辗转相除法求最大公约数的步骤如下 第一步:用较大的数m除以较小的数n得到一个商q和一个余数r;( Fn X go+r) 第二步:若r=0,则n为m,n的最大公约数:若r≠0,则用除数n除以余数r得到一个 商q1和一个余数r1;(n=ro×q+r1) 第三步:若r=0,则r为m,n的最大公约数:若r1≠0,则用除数r除以余数r得到 个商q2和一个余数r2;(ro=n1×q2+r2)……依次计算直至=0,此时所得到的即为 所求的最大公约数。它的程序为: m, n IF m0 I-r r=m mod n PRINT n END 在过去,我国是怎么解决求最大公约数问题的呢? 更相减损术:我国早期也有解决求最大公约数问题的算法,就是更相减损术。更相减损术求 最大公约数的步骤如下:可半者半之,不可半者,副置分母·子之数,以少减多,更相减损, 求其等也,以等数约之。 翻译出来为 第一步:任意给出两个正数:判断它们是否都是偶数。若是,用2约简:若不是,执行第 二步。第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小 数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。它
(1)利用辗转相除法求最大公约数的步骤如下: 第一步:用较大的数 m 除以较小的数 n 得到一个商 q0 和一个余数 r 0 ;(m=n× q0 + r 0 ) 第二步:若 r 0=0,则 n 为 m,n 的最大公约数;若 r 0 ≠0,则用除数 n 除以余数 r 0 得到一个 商 q1 和一个余数 r1 ;(n= r 0 × q1 + r1 ) 第三步:若 r1=0,则 r 0 为 m,n 的最大公约数;若 r1 ≠0,则用除数 r 0 除以余数 r1 得到一 个商 q2 和一个余数 r 2 ;( r 0 = r1 × q2 + r 2 ) …… 依次计算直至=0,此时所得到的 即为 所求的最大公约数。它的程序为: INPUT m,n IF m0 m=n n=r r=m MOD n WEND PRINT n END 在过去,我国是怎么解决求最大公约数问题的呢? (2) 更相减损术: 我国早期也有解决求最大公约数问题的算法,就是更相减损术。更相减损术求 最大公约数的步骤如下:可半者半之,不可半者,副置分母·子之数,以少减多,更相减损, 求其等也,以等数约之。 翻译出来为: 第一步:任意给出两个正数;判断它们是否都是偶数。若是,用 2 约简;若不是,执行第 二步。第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小 数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。它
的程序为: IF mn then ELSE d=m-n Wend d=2 k print d 设计意图: 在自主探究,合作交流中构建新知,体会辗转相除法与更相减损术这两种求最大公约数的 方法
的程序为: INPUT “m,n=“;m,n IF mn IF d>n then m=d ELSE m=n n=d End if d=m-n Wend d=2^k*d PRINT d End 设计意图: 在自主探究,合作交流中构建新知,体会辗转相除法与更相减损术这两种求最大公约数的 方法
三、质疑答辩,发展思维 1、举例:(1)利用辗转相除法求两数4081与20723的最大公约数。 解:20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0 所以,4081与20723的最大公约数是53 (2)用更相减损术求98与63的最大公约数 解:由于63不是偶数,把98和63以大数减小数,并辗转相减,即:98-63=35;63-35 8;35-28=7;28-7=21;21-7=14;14-7=7.所以,98与63的最大公约数是7。 2、思考:辗转相除法与更相减损术的区别是什么? ①都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主;计算 次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明 显。②从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术 则以减数与差相等而得到。 3、例题 例1求4557,1953,5115的最大公约数。 解:利用辗转相除法先求4557与1953的最大公约数。4557=19532+651,1953=6513,所以 651是4557和1953的最大公约数,在求651与5115的最大公约数, 5115=6517+558,651=5581+93 558=936,所以最大公约数是93 例2求390,455,546的最大公约数 解:利用更相减损术先求390与455的最大公约数 455-390=65,390-65=325,325-65=260,260-65=195,195-65=130,130-65=65,65-65=0, 所以290与455的公约数是65,再求65与546的最大公约数 546-65=481,481-65=416,416-65=351,351-65=286,286-65=221,221-65=156,156-65=91,91 65=26,65-26=39,39-26=13,26-13=13,13-13=0,所以最大公约数是13 4、巩固练习 求两个正数84与72的最大公约数。 解法一:84=721+12,72=126,所以12是最大公约数 解法二:84-72=12,72-12=60,60-12=48,48-12=24,24-12=12,12-12=0,所以12是最大公约 四、课堂小结:
三、质疑答辩,发展思维 1、举例:(1)利用辗转相除法求两数 4081 与 20723 的最大公约数。 解:20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0 所以,4081 与 20723 的最大公约数是 53。 (2)用更相减损术求 98 与 63 的最大公约数。 解:由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减,即:98-63=35; 63-35 =28;35-28=7;28-7=21; 21-7=14;14-7=7.所以,98 与 63 的最大公约数是 7。 2、思考: 辗转相除法与更相减损术的区别是什么? ①都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主;计算 次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明 显。②从结果体现形式来看,辗转相除法体现结果是以相除余数为 0 则得到,而更相减损术 则以减数与差相等而得到。 3、例题 例 1 求 4557,1953,5115 的最大公约数。 解:利用辗转相除法先求 4557 与 1953 的最大公约数。4557=19532+651,1953=6513,所以 651 是 4557 和 1953 的 最 大 公 约 数 , 在 求 651 与 5115 的 最 大 公 约 数 , 5115=6517+558,651=5581+93, 558=936,所以最大公约数是 93 例 2 求 390,455,546 的最大公约数。 解:利用更相减损术先求 390 与 455 的最大公约数。 455-390=65,390-65=325,325-65=260,260-65=195,195-65=130,130-65=65,65-65=0, 所以 290 与 455 的公约数是 65,再求 65 与 546 的最大公约数, 546-65=481,481-65=416,416-65=351,351-65=286,286-65=221,221-65=156,156-65=91,91- 65=26,65-26=39,39-26=13,26-13=13,13-13=0,所以最大公约数是 13 4、巩固练习 求两个正数 84 与 72 的最大公约数。 解法一:84=721+12,72=126,所以 12 是最大公约数。 解法二:84-72=12,72-12=60,60-12=48,48-12=24,24-12=12,12-12=0,所以 12 是最大公约 数。 四、课堂小结: