当前位置:首页 >> 数学 >> 1.3 算法案例_图文

1.3 算法案例_图文

第一章 算法初步 1.3 算法案例 学习 目标 1.理解辗转相除法与更相减损术的含义,了解其执行过程. 2.理解秦九韶算法的计算过程,并了解它提高计算效率的实质. 3.理解进位制的概念,能进行不同进位制间的转化. 4.了解进位制的程序框图和程序. 栏目 索引 知识梳理 题型探究 当堂检测 自主学习 重点突破 自查自纠 知识梳理 自主学习 知识点一 辗转相除法与更相减损术 1.辗转相除法 (1)辗转相除法,又叫欧几里得算法,是一种求两个正整数的 最大公约数 的 古老而有效的算法. (2)辗转相除法的算法步骤 第一步,给定两个正整数m,n . 第二步,计算 m除以n所得的余数r . 第三步, m=n,n=r . 第四步,若r=0,则m,n的最大公约数等于 m ;否则,返回 第二步 . 答案 2.更相减损术 第一步,任意给定两个正整数,判断它们是否都是偶数 .若是,用 2 约 简;若不是,执行 第二步 . 第二步,以 较大的数减去 较小 的数,接着把所得的差与 较小 的数比较, 并以大数减小数.继续这个操作,直到所得的数相等 为止,则这个数(等 数)或这个数与约简的数的乘积就是所求的最大公约数. 答案 3.辗转相除法和更相减损术的区别与联系: 名称 辗转相除法 (1)以除法为主; 区别 时,运算次数较少; 结果 更相减损术 (1)以减法为主; 较多; (4)相减前要进行是否都是偶数的判断 (2)两个整数的差值较大 (2)两个整数的差值较大时,运算次数 (3)相除,余数为0时得 (3)相减,减数与差相等时得结果; (1)都是求两个正整数最大公约数的方法; 联系 (2)二者的实质都是递推的过程; (3)二者都要用循环结构来实现 思考 答 实际应用更相减损术时要做的第一步工作是什么? 先判断a,b是否为偶数,若是,都除以2再进行. 答案 知识点二 秦九韶算法 1.秦九韶算法简介 (1)秦九韶算法要解决的问题是求多项式的值. (2)秦九韶算法的特点: 通过一次式的反复计算,逐步得到高次多项式的值,即将一个n次多项 式的求值问题归结为重复计算n个一次多项式的值的问题. (3)秦九韶算法的原理: 将f(x)=anxn+an-1xn-1+?+a1x+a0改写为: f(x)=(anxn-1+an-1xn-2+?+a1)x+a0 =((anxn-2+an-1xn-3+?+a2)x+a1)x+a0 =? 先计算最内层括号内一次多项式的值,即v1=anx+an-1,再由内向外 逐层计算一次多项式vk的值. 2.秦九韶算法的操作方法 (1)算法步骤如下: 第一步,输入多项式次数n、最高次项的系数an和x的值. 第二步,将v的值初始化为an,将i的值初始化为n-1. 第三步,输入i次项的系数ai. 第四步,v=vx+ai,i=i-1. 第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多 项式的值v. (2)程序框图如图所示. (3)程序如下: INPUT “n=”;n INPUT “an=”;a INPUT “x=”;x v=a i=n-1 WHILE i>=0 PRINT “i=”;i INPUT “ai=”;a v=v*x+a i=i-1 WEND PRINT v END 知识点三 进位制 1.进位制的概念 进位制是为了计数和运算方便而约定的记数系统,约定“满几进一” 就是几进制,几进制的基数(大于1的整数)就是几. 2.常见的进位制 (1)二进制: ①只使用0和1两个数学; ②满二进一,即1+1=10(2). (2)八进制: ①使用0,1,2,3,4,5,6,7这八个不同数学; ②满八进一,即7+1=10(8). (3)十六进制: ①使用0~9十个数字和A~F表示10~15; ②F+1=10(16) 思考 答 任何进位制中都要用到的数字是什么? 0和1. 答案 返回 题型探究 重点突破 题型一 求两个正整数的最大公约数 例1 分别用辗转相除法和更相减损术求261和319的最大公约数. 方法二 (更相减损术) 解 方法一 (辗转相除法) 319÷261=1(余58), 319-261=58, 261-58=203, 261÷58=4(余29), 58÷29=2(余0), 203-58=145, 145-58=87, 87-58=29, 58-29=29, 29-29=0, 所以319与261的最大公约数为29. 所以319与261的最大公约数是29. 反思与感悟 解析答案 跟踪训练1 验你的结果. 解 用辗转相除法求80与36的最大公约数,并用更相减损术检 80=36×2+8,36=8×4+4,8=4×2+0, 即80与36的最大公约数是4. 验证: 80÷2=40,36÷2=18;40÷2=20,18÷2=9; 20—9=11,11-9=2;9-2=7,7-2=5; 5-2=3,3-2=1;2-1=1,1×2×2=4; 所以80与36的最大公约数为4. 解析答案 题型二 秦九韶算法的应用 例2 用秦九韶算法求多项式f(x)=x5+5x4+10x3+10x2+5x+1当x=-2 时的值. 解 f(x)=x5+5x4+10x3+10x2+5x+1=((((x+5)x+10)x+10)x+5)x+1. 当x=-2时,有v0=1; v1=v0x+a4=1×(-2)+5=3; v2=v1x+a3=3×(-2)+10=4; v3=v2x+a2=4×(-2)+10=2; v4=v3x+a1=2×(-2)+5=1; v5=v4x+a0=1×(-2)+1=-1. 故f(-2)=-1. 反思与感悟 解析答案 跟踪训练 2 解 用秦九韶算法计算多项式 f(x) = x6 - 12x5 + 60x4 - 160x3 + 240x2-192x+64当x=2时的值. 根据秦九韶算法,

更多相关文档:

1.3 算法案例_图文.ppt

1.3 算法案例 - 1.3 算法案例 案例1 辗转相除法与更相减损术 [问题1

1.3算法案例_图文.ppt

1.3算法案例 - 新课导入 方法: 先用两个公有的质因数连续去除,一 直除到所

《1.3算法案例》ppt课件_图文.ppt

1.3算法案例》ppt课件_数学_高中教育_教育专区。算法案例(1) 1. 回

1.3算法案例_图文.ppt

1.3算法案例 - 情境创设 ? 韩信是秦末汉初的著名军事家.据说有一次汉高祖

1.3算法案例(适用)ppt_图文.ppt

1.3算法案例(适用)ppt - 1.3 算法案例 1.3 算法案例 1.3.1 辗转相除法和更相减损术 1.3.2 秦...

1.3算法案例ppt_图文.ppt

1.3算法案例ppt - 1.3 算法案例 1.3 算法案例 1.3.1 辗转相除法和更相减损术 1.3.2 秦九韶算法 1.3.3 K进制化十进制 1.3.4 十进制化K进制 ...

1-3算法案例课件_图文.ppt

1-3算法案例课件 - 案例1 辗转相除法与更相减损术 、学习目标 1.理解辗

1.3 算法案例_图文.ppt

1.3 算法案例 - 第一章 算法初步 1.3 算法案例 学习 目标 1.理解辗

1.3算法案例_图文.ppt

1.3算法案例 - § 复习引入 1. 回顾算法的三种表示方法: (1)、自然语

1.3算法案例_图文.ppt

1.3算法案例 - 算法案例(1) 1. 回顾算法的三种表述: 自然语言 程序框

1.3算法案例_图文.ppt

1.3算法案例_高一数学_数学_高中教育_教育专区。 [问题1]:在小学,我们已

1.3算法案例_图文.ppt

1.3算法案例 - 1.3 算法案例 一、辗转相除法 1、求两个正整数的最大公约

1.3 算法案例_图文.ppt

1.3 算法案例 - 1.3 算法案例 案例1 辗转相除法与更相减损术 [问题1

1.3算法案例_图文.ppt

1.3算法案例 - 1.3.1 案例1、辗转相除法与更相减损术 复习引入 回顾算

1.3算法案例ppt_图文.ppt

1.3算法案例ppt_数学_高中教育_教育专区。1.3 算法案例 1.3 算法案例 1.3.1 辗转相除法和更相减损术 1.3.2 秦九韶算法 1.3.3 K进制化十进制 1.3...

1.3算法案例_图文.ppt

1.3算法案例 - 华侨中学 张爱梅 案例1 辗转相除法与更相减损术 一、三维目

1.3算法案例_图文.ppt

1.3算法案例 - 1.3 算法案例 案例1辗转相除法和更相减损术 在初中,我们

1.3算法案例_图文.ppt

1.3算法案例 - 一位美国的幼儿园老师为了教育孩子火海逃生,引导学生做了一个非

1.3算法案例_图文.ppt

1.3算法案例 - 案例1 辗转相除法与更相减损术 〖创设情景,揭示课题〗 [问

1.3算法案例(一)_图文.ppt

1.3算法案例(一) - 1.3 算法案例 辗转相除法与更相减损术 秦九韶算法

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com