11.3算法案例.pptVIP

情境创设 韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上的士兵的人数,韩信先令士兵排成3列纵队,结果有2人多余,接着下令排成5列纵队,结果又多出3人,随后他又下令改为7列纵队,这次又剩下2人无法成整行.在场的人都哈哈大笑,以为韩信不能清点出准确的人数,不料笑声刚落,韩信高声报告共有士兵2333人.众人听了一楞,不知道韩信用什么方法这么快就能得到正确的结果的.今天,我们将以这些古典案例的思想,设计出适宜计算机的运行程序,提高我们对基本算法结构和算法语句在实际中的运用能力. 探究一,辗转相除法 思考1:在小学中我们是如何求出两个正整数的最大公约数的呢? 探究一,辗转相除法 思考2:当两个数的公有质因数较大时,我们怎样去求两个数的最大公约数呢? 辗转相除法:用于求两个正整数的最大公约数的一种算法,是由欧几里得在公元前300年左右首先提出的,因而又叫做欧几里得算法. 定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数. 探究二,更相减损术 九章算术 “可半者半之,不可半者,副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。” 讨论：你能根据更相减损术的算法步骤画出其程序框图并写出程序语句吗? 思考：辗转相除法与更相减损术有什么区别和联系？ 区别： 计算上辗转相除法以除法为主，更相减损术以减法为主； 在计算次数上，辗转相除法计算次数相对较少，特别当两个数大小差别较大时计算次数的区别较明显； 从结果输出的时候看，辗转相除法当余数为0时输出除数，更相减损术当差和减数相等时输出差。 联系：都是求最大公约数的方法。因为做一次除法与做若干次减法效果相同，商就是减法的次数，余数就是最后的差，由此可知二者是完全统一的！ 例3，求三个数319，377，116的最大公约数（计算，不编程） 辗转相除法 1，4830与3289的最大公约数为_______ 2，用更相减损术求87与27的最大公约数时，反复相减，直至求出最大公约数，需要进行减法运算的次数是______ 3，用辗转相除法求87与27的最大公约数，需要进行除法运算的次数是_____ 4，46，115，276的最大公约数是____ 探究三、秦九昭算法 思考1,在初中,我们是如何求一个多项式的值的? 思考2,已知一个n 次多项式 f(x)=anxn+an-1xn-1+…+a1x+a0当x=x0时，除了用代入法求解外是否还有更好的方法呢？ 探究：以f(x)=a5x5+a4x4+…+a1x+a0为例 秦九昭算法问题： 秦九昭（约1202~1261）是我国南宋时期享誉世界的数学家，在他的代表作《数学九章》中介绍了计算一个n次多项式值的算法，即“秦九韶算法”。它的特点是：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。 秦九韶算法是求一元多项式值的一种方法，现在它仍是世界上多项式求值最先进的方法，这一成就比西方同样的算法早五六百年，且该算法很容易在计算机上实现！ 6，用秦九昭算法求多项式f(x)=x4+2x3+3x2+x+1,当x=2时的值时，第一次运算的步骤是（ ） A 1×2 B 24 C 2+2 D 1×2+2 7，用秦九昭算法求多项式 f(x)=a3x3+a2x2+a1x+a0,当x=x0时的值最多要做____次乘法运算，_____次加法运算。 8，用秦九昭算法，求 f(x)=3x5-2x3+2x2-1当x=2时的值。 10，用秦九昭算法计算多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6在x=-4时的值时，v3的值为（ ） A -845 B 220 C -57 D 34 探究四、进位制 情境创设 古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向国内报告，如图：烽火台上点火表示数字1，不点火表示数字0，约定二进制数对应的十进制数的单位是1000，请你计算一下，这组烽火台表示有多少敌人入侵？ 探究一、进位制的概念 思考1，我们在学习过程中所处理的数据一般都是几进制的，你能说说它有什么规律吗？你还能举出哪些有关进位制的例子？ 谈谈你对进位制的认识！ 进位制是人们为了计算和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制等。即“满几进一”就是几进制，几进制的基数就是几。 探究二、进位制之间的转换 思考1：根据十进制的表示方法，你能把k进制的数转化为十进制吗？