当前位置:首页 >> 数学 >>

示范教案(1.3 算法案例)


1.3 算法案例 整体设计 教学分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序框图和程序三种不同 方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在解决 问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表 达能力. 三维目标 1.理解算法案例的算法步骤和程序框图. 2.引导学生得出自己设计的算法程序.

3. 体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 重点难点 教学重点:引导学生得出自己设计的算法步骤、程序框图和算法程序. 教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 课时安排 3 课时 教学过程 第 1 课时 案例 1 辗转相除法与更相减损术 导入新课 思路 1(情境导入) 大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球, 东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的.在小学, 我们学过求两个正整数的最大公约数的方法: 先用两个数公有的质因数连续去除, 一直除到 所得的商是互质数为止, 然后把所有的除数连乘起来. 当两个数公有的质因数较大时 (如?8 251?与 6 105) ,使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法—— 辗转相除法与更相减损术,由此可以体会东、西方文化的差异. 思路 2(直接导入) 前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减 损术来进一步体会算法的思想. 推进新课 新知探究 提出问题 (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 的最大公约数,写出算法分析,画出程序框图,写出算 法程序. 解:用两数中较大的数除以较小的数,求得商和余数:8 251=6 105× 1+2 146. 由此可得,6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数,反过来,8 251 与 6 105 的公约数也是 6 105 与 2 146 的公约数,所以它们的最大公约数相等. 对 6 105 与 2 146 重复上述步骤:6 105=2 146× 2+1 813. 同理,2 146 与 1 813 的最大公约数也是 6 105 与 2 146 的最大公约数.继续重复上述步骤: 2 146=1 813× 1+333, 1 813=333× 5+148, 333=148× 2+37, 148=37× 4. 最后的除数 37 是 148 和 37 的最大公约数,也就是 8 251 与 6 105 的最大公约数. 这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可 以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数. 算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结 构来构造算法. 算法步骤如下: 第一步,给定两个正整数 m,n. 第二步,计算 m 除以 n 所得的余数为 r. 第三步,m=n,n=r. 第四步,若 r=0,则 m,n 的最大公约数等于 m;否则,返回第二步. 程序框图如下图:

程序: INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 点评:从教学实践看,有些学生不能理解算法中的转化过程,例如:求 8 251 与 6 105 的最 大公约数,为什么可以转化为求 6 105 与 2 146 的公约数.因为 8 251=6 105× 1+2 146, 可以化为 8 251-6 105× 1=2 164,所以公约数能够整除等式两边的数,即 6 105 与 2 146 的公 约数也是 8 251 与 6 105 的公约数. 变式训练 你能用当型循环结构构造算法,求两个正整数的最大公约数吗?试画出程序框图和程 序. 解:当型循环结构的程序框图如下图:

程序: INPUT m,n r=1 WHILE r>0 r=m MOD n m=n n=r WEND PRINT m END 例 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. 点评:更相减损术与辗转相除法的比较:尽管两种算法分别来源于东、西方古代数学名著, 但是二者的算理却是相似的, 有异曲同工之妙. 主要区别在于辗转相除法进行的是除法运算, 即辗转相除;而更相减损术进行的是减法运算,即辗转相减,但是实质都是一个不断的递归 过程. 变式训练 用辗转相除法或者更相减损术求三个数 324,243,135 的最大公约数. 解:324=243× 1+81, 243=81× 3+0, 则 324 与 243 的最大公约数为 81. 又 135=81× 1+54,81=54× 1+27, 54=27× 2+0, 则 81 与 135 的最大公约数为 27. 所以,三个数 324、243、135 的最大公约数为 27. 另法:324-243=81,243-81=162,162-81=81,则 324 与 243 的最大公约数为 81. 135-81=54,81-54=27,54-27=27,则 81 与 135 的最大公约数为 27. 所以,三个数 324、243.135 的最大公约数为 27. 例 3 (1)用辗转相除法求 123 和 48 的最大公约数. (2)用更相减损术求 80 和 36 的最大公约数. 解: (1)辗转相除法求最大公约数的过程如下: 123=2× 48+27, 48=1× 27+21, 27=1× 21+6, 21=3× 6+3, 6=2× 3+0, 最后 6 能被 3 整除,得 123 和 48 的最大公约数为 3.

(2)我们将 80 作为大数,36 作为小数,因为 80 和 36 都是偶数,要除公因数 2. 80÷ 2=40,36÷ 2=18. 40 和 18 都是偶数,要除公因数 2. 40÷ 2=20,18÷ 2=9. 下面来求 20 与 9 的最大公约数, 20-9=11, 11-9=2, 9-2=7, 7-2=5, 5-2=3, 3-2=1, 2-1=1, 可得 80 和 36 的最大公约数为 22× 1=4. 点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为 0,更相减损术是到达减 数和差相等. 变式训练 分别用辗转相除法和更相减损术求 1 734,816 的最大公约数. 解:辗转相除法: 1 734=816× 2+102,816=102× 8(余 0) , ∴1 734 与 816 的最大公约数是 102. 更相减损术:因为两数皆为偶数,首先除以 2 得到 867,408,再求 867 与 408 的最大公约 数. 867-408=459, 459-408=51, 408-51=357, 357-51=306, 306-51=255, 255-51=204, 204-51=153, 153-51=102, 102-51=51. ∴1 734 与 816 的最大公约数是 51× 2=102. 利用更相减损术可另解: 1 734-816=918, 918-816=102, 816-102=714, 714-102=612, 612-102=510, 510-102=408, 408-102=306, 306-102=204, 204-102=102. ∴1 734 与 816 的最大公约数是 102. 知能训练

求 319,377,116 的最大公约数. 解:377=319× 1+58, 319=58× 5+29, 58=29× 2. ∴377 与 319 的最大公约数为 29,再求 29 与 116 的最大公约数. 116=29× 4. ∴29 与 116 的最大公约数为 29. ∴377,319,116 的最大公约数为 29. 拓展提升 试写出利用更相减损术求两个正整数的最大公约数的程序. 解:更相减损术程序: INPUT “m,n=”;m,n WHILE m<>n IF m>n THEN m=m-n ELSE m=n-m END IF WEND PRINT m END 课堂小结 (1)用辗转相除法求最大公约数. (2)用更相减损术求最大公约数. 思想方法:递归思想. 作业 分别用辗转相除法和更相减损术求 261,319 的最大公约数. 分析:本题主要考查辗转相除法和更相减损术及其应用.使用辗转相除法可依据 m=nq+r, 反复执行,直到 r=0 为止;用更相减损术就是根据 m-n=r,反复执行,直到 n=r 为止. 解:辗转相除法: 319=261× 1+58, 261=58× 4+29, 58=29× 2. ∴319 与 261 的最大公约数是 29. 更相减损术: 319-261=58, 261-58=203, 203-58=145, 145-58=87, 87-58=29, 58-29=29, ∴319 与 261 的最大公约数是 29. 设计感想 数学不仅是一门科学,也是一种文化,本节的引入从东、西方文化的不同开始,逐步向

学生渗透数学文化.从知识方面主要学习用两种方法求两个正整数的最大公约数,从思想方 法方面,主要学习递归思想.本节设置精彩例题,不仅让学生学到知识,而且让学生进一步 体会算法的思想,培养学生的爱国主义情操. 第 2 课时 案例 2 秦九韶算法 导入新课 思路 1(情境导入) 大家都喜欢吃苹果吧, 我们吃苹果都是从外到里一口一口的吃, 而虫子却是先钻到苹果 里面从里到外一口一口的吃,由此看来处理同一个问题的方法多种多样.怎样求多项式 f(x)=x5+x4+x3+x2+x+1 当 x=5 时的值呢?方法也是多种多样的,今天我们开始学习秦九韶算 法. 思路 2(直接导入) 前面我们学习了辗转相除法与更相减损术, 今天我们开始学习秦九韶算法. 推进新课 新知探究 提出问题 (1)求多项式 f(x)=x5+x4+x3+x2+x+1 当 x=5 时的值有哪些方法?比较它们的特点. (2)什么是秦九韶算法? (3)怎样评价一个算法的好坏? 讨论结果: (1)怎样求多项式 f(x)=x5+x4+x3+x2+x+1 当 x=5 时的值呢? 一个自然的做法就是把 5 代入多项式 f(x),计算各项的值,然后把它们加起来,这时, 我们一共做了 1+2+3+4=10 次乘法运算,5 次加法运算. 另一种做法是先计算 x2 的值,然后依次计算 x2· (x2· x,(x2· x)· 的值,这 x, x)· ( x)· x 样每次都可以利用上一次计算的结果,这时,我们一共做了 4 次乘法运算,5 次加法运算. 第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率,对于 计算机来说, 做一次乘法运算所用的时间比做一次加法运算要长得多, 所以采用第二种做法, 计算机能更快地得到结果. (2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约 1202~1261)在 他的著作《数书九章》中提出了下面的算法: 把一个 n 次多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 改写成如下形式: f(x)=anxn+an-1xn-1+…+a1x+a0 =(anxn-1+an-1xn-2+…+a1)x+ a0 =( nxn-2+an-1xn-3+…+a2)x+a1)x+a0 (a =… =(…( nx+an-1)x+an-2)x+…+a1)x+a0. (a 求多项式的值时,首先计算最内层括号内一次多项式的值,即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值,即 v2=v1x+an-2, v3=v2x+an-3, … vn=vn-1x+a0, 这样,求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值. 上述方法称为秦九韶算法.直到今天,这种算法仍是多项式求值比较先进的算法.

(3)计算机的一个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标志 仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这 样的算法就只能是一个理论的算法. 应用示例 例 1 已知一个 5 次多项式为 f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8, 用秦九韶算法求这个多项式当 x=5 时的值. 解:根据秦九韶算法,把多项式改写成如下形式: f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8, 按照从内到外的顺序,依次计算一次多项式当 x=5 时的值: v0=5; v1=5× 5+2=27; v2=27× 5+3.5=138.5; v3=138.5× 5-2.6=689.9; v4=689.9× 5+1.7=3 451.2; v5=3 415.2× 5-0.8=17 255.2; 所以,当 x=5 时,多项式的值等于 17 255.2. 算法分析: 观察上述秦九韶算法中的 n 个一次式, 可见 vk 的计算要用到 vk-1 的值, 若令 v0=an, 我们可以得到下面的公式:

?v0 ? an , ? ?vk ? vk ?1 x ? an?k (k ? 1,2,?, n).
这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现. 算法步骤如下: 第一步,输入多项式次数 n、最高次的系数 an 和 x 的值. 第二步,将 v 的值初始化为 an,将 i 的值初始化为 n-1. 第三步,输入 i 次项的系数 ai. 第四步,v=vx+ai,i=i-1. 第五步,判断 i 是否大于或等于 0.若是,则返回第三步;否则,输出多项式的值 v. 程序框图如下图:

程序: 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 点评:本题是古老算法与现代计算机语言的完美结合,详尽介绍了思想方法、算法步骤、程 序框图和算法语句,是一个典型的算法案例. 变式训练 请以 5 次多项式函数为例说明秦九韶算法,并画出程序框图. 解:设 f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0 首先,让我们以 5 次多项式一步步地进行改写: f(x)=(a5x4+a4x3+a3x2+a2x+a1)x+a0 =( 5x3+a4x2+ a3x+a2)x+a1)x+a0 (a =((a5x2+a4x+ a3)x+a2)x+a1)x+a0 ( =(( 5x+a4)x+ a3)x+a2)x+a1)x+a0. ((a 上面的分层计算,只用了小括号,计算时,首先计算最内层的括号,然后由里向外逐层计算, 直到最外层的括号,然后加上常数项即可. 程序框图如下图:

k 例 2 已知 n 次多项式 Pn(x)=a0xn+a1xn-1+…+an-1x+an,如果在一种算法中,计算 x0 (k=2,3,

4,…,n)的值需要 k-1 次乘法,计算 P3(x0)的值共需要 9 次运算(6 次乘法,3 次加法) , 那 么计 算 P10(x0)的 值共需 要 __________次运 算 .下 面给 出一 种减 少运 算次 数的 算法 : P0(x)=a0,Pk+1(x)=xPk(x)+ak+1(k=0,1,2,…,n-1) .利用该算法,计算 P3(x0)的值共需要 6 次运算,计算 P10(x0)的值共需要___________次运算. 答案:65 20 点评:秦九韶算法适用一般的多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 的求值问题.直接法乘法运 算的次数最多可到达

( n ? 1) n ,加法最多 n 次.秦九韶算法通过转化把乘法运算的次数减少 2

到最多 n 次,加法最多 n 次.

例 3 已知多项式函数 f(x)=2x5-5x4-4x3+3x2-6x+7,求当 x=5 时的函数的值. 解析:把多项式变形为:f(x)=2x5-5x4-4x3+3x2-6x+7 =((((2x-5)x-4)x+3)x-6)x+7. 计算的过程可以列表表示为:

最后的系数 2 677 即为所求的值. 算法过程: v0=2; v1=2× 5-5=5; v2=5× 5-4=21; v3=21× 5+3=108; v4=108× 5-6=534; v5=534× 5+7=2 677. 点评:如果多项式函数中有缺项的话,要以系数为 0 的项补齐后再计算. 知能训练 当 x=2 时,用秦九韶算法求多项式 f(x)=3x5+8x4-3x3+5x2+12x-6 的值. 解法一:根据秦九韶算法,把多项式改写成如下形式: f(x)=((((3x+8)x-3)x+5)x+12)x-6. 按照从内到外的顺序,依次计算一次多项式当 x=2 时的值. v0=3; v1=v0× 2+8=3× 2+8=14; v2=v1× 2-3=14× 2-3=25; v3=v2× 2+5=25× 2+5=55; v4=v3× 2+12=55× 2+12=122; v5=v4× 2-6=122× 2-6=238. ∴当 x=2 时,多项式的值为 238. 解法二:f(x)=((((3x+8)x-3)x+5)x+12)x-6, 则 f(2)=((((3× 2+8)× 2-3)× 2+5)× 2+12)× 2-6=238. 拓展提升 用秦九韶算法求多项式 f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x 当 x=3 时的值. 解:f(x)=((((((7x+6)+5)x+4)x+3)x+2)x+1)x v0=7; v1=7× 3+6=27; v2=27× 3+5=86; v3=86× 3+4=262; v4=262× 3+3=789; v5=789× 3+2=2 369; v6=2 369× 3+1=7 108; v7=7 108× 3+0=21 324. ∴f(3)=21 324. 课堂小结

1.秦九韶算法的方法和步骤. 2.秦九韶算法的计算机程序框图. 作业 已知函数 f(x)=x3-2x2-5x+8,求 f(9)的值. 解:f(x)=x3-2x2-5x+8=(x2-2x-5)x+8=((x-2)x-5)x+8 ∴f(9)=((9-2)× 9-5)× 9+8=530. 设计感想 古老的算法散发浓郁的现代气息,这是一节充满智慧的课.本节主要介绍了秦九韶算法. 通过对秦九韶算法的学习,对算法本身有哪些进一步的认识? 教师引导学生思考、讨论、概括,小结时要关注如下几点: (1)算法具有通用的特点, 可以解决一类问题; (2)解决同一类问题,可以有不同的算法,但计算的效率是不同的,应 该选择高效的算法; (3)算法的种类虽多,但三种逻辑结构可以有效地表达各种算法等等. 第 3 课时 案例 3 进位制 导入新课 情境导入 在日常生活中,我们最熟悉、最常用的是十进制,据说这与古人曾以手指计数有关,爱 好天文学的古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、一 年十二个月、一小时六十分的历法.今天我们来学习一下进位制. 推进新课 新知探究 提出问题 (1)你都了解哪些进位制? (2)举出常见的进位制. (3)思考非十进制数转换为十进制数的转化方法. (4)思考十进制数转换成非十进制数及非十进制之间的转换方法. 活动:先让学生思考或讨论后再回答,经教师提示、点拨,对回答正确的学生及时表扬,对 回答不准确的学生提示引导考虑问题的思路. 讨论结果: (1)进位制是人们为了计数和运算方便而约定的计数系统,约定满二进一,就是二进制; 满十进一,就是十进制;满十二进一,就是十二进制;满六十进一,就是六十进制等等.也 就是说:“满几进一”就是几进制,几进制的基数(都是大于 1 的整数)就是几. (2)在日常生活中,我们最熟悉、最常用的是十进制,据说这与古人曾以手指计数有关, 爱好天文学的古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、 一年十二个月、一小时六十分的历法. (3)十进制使用 0~9 十个数字.计数时,几个数字排成一行,从右起,第一位是个位,个位 上的数字是几,就表示几个一;第二位是十位,十位上的数字是几,就表示几个十;接着依 次是百位、千位、万位…… 例如:十进制数 3 721 中的 3 表示 3 个千,7 表示 7 个百,2 表示 2 个十,1 表示 1 个一.于 是,我们得到下面的式子: 3 721=3× 3+7× 2+2× 1+1× 0. 10 10 10 10 与十进制类似,其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同,所 用的数字个数也不同.如二进制用 0 和 1 两个数字,七进制用 0~6 七个数字. 一般地, k 是一个大于 1 的整数, 若 那么以 k 为基数的 k 进制数可以表示为一串数字连写在 一起的形式

anan-1…a1a0(k) (0<an<k,0≤an-1,…,a1,a0<k). 其他进位制的数也可以表示成不同位上数字与基数的幂的乘积之和的形式,如 110 011(2)=1× 5+1× 4+0× 3+0× 2+1× 1+1× 0, 2 2 2 2 2 2 3 2 1 0 7 342(8)=7× +3× +4× +2× . 8 8 8 8 非十进制数转换为十进制数比较简单,只要计算下面的式子值即可: anan-1…a1a0(k)=an× n+an-1× n-1+…+a1× 0. k k k+a 第一步:从左到右依次取出 k 进制数 anan-1…a1a0(k)各位上的数字,乘以相应的 k 的幂,k 的 幂从 n 开始取值,每次递减 1,递减到 0,即 an× n,an-1× n-1,…,a1× 0× 0; k k k,a k 第二步:把所得到的乘积加起来,所得的结果就是相应的十进制数. (4)关于进位制的转换,教科书上以十进制和二进制之间的转换为例讲解,并推广到十进 制和其他进制之间的转换.这样做的原因是,计算机是以二进制的形式进行存储和计算数据 的, 而一般我们传输给计算机的数据是十进制数据, 因此计算机必须先将十进制数转换为二 进制数,再处理,显然运算后首次得到的结果为二进制数,同时计算机又把运算结果由二进 制数转换成十进制数输出. 1°十进制数转换成非十进制数 把十进制数转换为二进制数,教科书上提供了“除 2 取余法”,我们可以类比得到十进制数转 换成 k 进制数的算法“除 k 取余法”. 2°非十进制之间的转换 一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与 16 进制数据之间 的互化的方法,也就是先由二进制数转化为十进制数,再由十进制数转化成为 16 进制数. 应用示例 思路 1 例 1 把二进制数 110 011(2)化为十进制数. 解:110 011(2)=1× 5+1× 4+0× 3+0× 2+1× 1+1× 0=1× 2 2 2 2 2 2 32+1× 16+1× 2+1=51. 点评: 先把二进制数写成不同位上数字与 2 的幂的乘积之和的形式, 再按照十进制的运算规 则计算出结果. 变式训练 设计一个算法,把 k 进制数 a(共有 n 位)化为十进制数 b. 算法分析:从例 1 的计算过程可以看出,计算 k 进制数 a 的右数第 i 位数字 ai 与 ki-1 的乘积 ai·i-1,再将其累加,这是一个重复操作的步骤.所以,可以用循环结构来构造算法. k 算法步骤如下: 第一步,输入 a,k 和 n 的值. 第二步,将 b 的值初始化为 0,i 的值初始化为 1. 第三步,b=b+ai·i-1,i=i+1. k 第四步,判断 i>n 是否成立.若是,则执行第五步;否则,返回第三步. 第五步,输出 b 的值. 程序框图如下图:

程序: INPUT “a,k,n=”;a,k,n b=0 i=1 t=a MOD 10 DO b=b+t*k^(i-1) a=a\\10 t=a MOD 10 i=i+1 LOOP UNTIL i>n PRINT b END 例 2 把 89 化为二进制数. 解:根据二进制数“满二进一”的原则,可以用 2 连续去除 89 或所得商,然后取余数.具体计 算方法如下: 因为 89=2× 44+1,44=2× 22+0, 22=2× 11+0, 11=2× 5+1, 5=2× 2+1, 2=2× 1+0, 1=2× 0+1, 所以 89=2× (2× (2× (2× (2× 2+1)+1)+0)+0)+1 2 =2× (2× (2× (2× (2 +1)+1)+0)+0)+1 6 5 =…=1×2 +0× +1× 4+1× 3+0× 2+0× 1+1× 0 2 2 2 2 2 2 =1 011 001(2). 这种算法叫做除 2 取余法,还可以用下面的除法算式表示:

把上式中各步所得的余数从下到上排列,得到 89=1 011 001(2). 上述方法也可以推广为把十进制数化为 k 进制数的算法,称为除 k 取余法. 变式训练 设计一个程序,实现“除 k 取余法”. 算法分析:从例 2 的计算过程可以看出如下的规律: 若十制数 a 除以 k 所得商是 q0,余数是 r0,即 a=k·0+r0,则 r0 是 a 的 k 进制数的右数第 q 1 位数. 若 q0 除以 k 所得的商是 q1,余数是 r1,即 q0=k·1+r1,则 r1 是 a 的 k 进制数的左数第 2 q 位数. …… 若 qn-1 除以 k 所得的商是 0,余数是 rn,即 qn-1=rn,则 rn 是 a 的 k 进制数的左数第 1 位 数. 这样,我们可以得到算法步骤如下: 第一步,给定十进制正整数 a 和转化后的数的基数 k. 第二步,求出 a 除以 k 所得的商 q,余数 r. 第三步,把得到的余数依次从右到左排列. 第四步,若 q≠0,则 a=q,返回第二步;否则,输出全部余数 r 排列得到的 k 进制数. 程序框图如下图:

程序: INPUT “a,k=”;a,k b=0 i=0 DO

q=a\\k r=a MOD k b=b+r*10^i i=i+1 a=q LOOP UNTIL q=0 PRINT b END 思路 2 例 1 将 8 进制数 314 706(8)化为十进制数,并编写出一个实现算法的程序. 解:314 706(8)=3× 5+1× 4+4× 3+7× 2+0× 1+6× 0=104 902. 8 8 8 8 8 8 所以,化为十进制数是 104 902. 点评:利用把 k 进制数转化为十进制数的一般方法就可以把 8 进制数 314 706(8)化为十进制 数. 例 2 把十进制数 89 化为三进制数,并写出程序语句. 解:具体的计算方法如下: 89=3× 29+2, 29=3× 9+2, 9=3× 3+0, 3=3× 1+0, 1=3× 0+1, 所以:89(10)=10 022(3). 点评:根据三进制数满三进一的原则,可以用 3 连续去除 89 及其所得的商,然后按倒序的 顺序取出余数组成数据即可. 知能训练 将十进制数 34 转化为二进制数. 分析:把一个十进制数转换成二进制数,用 2 反复去除这个十进制数,直到商为 0,所得余 数(从下往上读)就是所求. 解:

即 34(10)=100 010(2) 拓展提升 把 1 234(5)分别转化为十进制数和八进制数. 解:1 234(5)=1× 3+2× 2+3× 5 5 5+4=194.

则 1 234(5)=302(8) 所以,1 234(5)=194=302(8) 点评: 本题主要考查进位制以及不同进位制数的互化. 五进制数直接利用公式就可以转化为

十进制数;五进制数和八进制数之间需要借助于十进制数来转化. 课堂小结 (1)理解算法与进位制的关系. (2)熟练掌握各种进位制之间转化. 作业 习题 1.3A 组 3、4. 设计感想 计算机是以二进制的形式进行存储和计算数据的, 而一般我们传输给计算机的数据是十 进制数据,因此计算机必须先将十进制数转换为二进制数,再处理,显然运算后首次得到的 结果为二进制数,同时,计算机又把运算结果由二进制数转换成十进制数输出.因此学好进 位制是非常必要的,另外,进位制也是高考的重点,本节设置了多种题型供学生训练,所以 这节课非常实用.


相关文章:
案例示范1
示范教案(1.3 算法案例... 16页 免费 教育案例反思示例1 11页 免费 一、案例...过分完美期待信念引发情绪障碍 咨询案例分析一、 来访者一般资料: 来访者,女,...
1.3算法案例教案
1.3算法案例教案_数学_高中教育_教育专区。考试指南报——课堂网(www.k45.cn) 算法案例一. 【课标要求】通过阅读中国古代数学中的算法案例,体会中国古代数学对...
1.示范教案(1.1.1 算法的概念)
3.示范教案(1.2.1 输入语... 7页 免费如要投诉违规内容,请到百度文库投诉...本章主要内容:算法与程序框图、基本算法语句、算法案例和小结.教材从学生最熟悉 ...
高中数学必修3《1.3算法案例)》教案设计
高中数学必修3《1.3算法案例)教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用注册,免费下载! 1.3...
1.示范教案(1.1.1 算法的概念)
1.示范教案(1.1.1 算法的概念)_数学_高中教育_教育专区。第一章 算法初步 ...1.2.2 条件语句 1.2.3 循环语句 1.3 算法案例 本章复习 1.1 算法与...
【数学】1.3《算法案例》教案(新人教A版必修3)
【数学】1.3算法案例教案(新人教A版必修3)_一年级数学_数学_小学教育_教育专区。知识改变命运, 知识改变命运,学习成就未来 1.3 算法案例(1)教学目标 (a...
数学:1.3 《算法案例》教案(新人教A版必修3)
数学:1.3算法案例教案(新人教A版必修3)_数学_高中教育_教育专区。1.3算法案例》教案 1.3 算法案例 第一、二课时 辗转相除法与更相减损术 (1)...
【数学】1.3《算法案例---秦九韶算法》教案(新人教A版...
【数学】1.3算法案例---秦九韶算法》教案(新人教A版必修3)_初三数学_数学_初中教育_教育专区。知识改变命运, 知识改变命运,学习成就未来 〔教案〕 教学目标...
...§1.3算法案例(复习)教案(精品)
高中数学 §1.3 算法案例(复习)教案 新人教 A 版必修 3 一、教学目标 1、知识与技能 (1)明确算法的含义,熟悉算法的三种基本 结构:顺序、条件和循环,以及...
算法案例教案
算法案例教案_其它课程_高中教育_教育专区。算法案例教案课题:§1.3 算法案例 第 1 课时 辗转相除法与更相减损术、秦九韶算法一、教学目标:根据课标要求:在学生...
更多相关标签:
1.3算法案例教案 | 算法案例教案 | 1.3算法案例 | 智能算法30个案例分析 | 对外汉语教学示范教案 | pagerank算法应用案例 | 算法案例 | ppp示范项目案例选编 |