算法案例 (2).ppt

《算法案例 (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、知识点——算法案例算法案例【常见三大算法】（1）求最大公约数（2）秦九韶算法（3）进位制算法案例【求最大公约数】（1）短除法求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.（2）穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.算法案例【求最大公约数】（3）辗转相除法辗转相除法求两个数的最大公约数，其算法可以描述如下：①输入两个正整数m和n(m>n)；②求余数r：计算m除以n，将所得余数存放到变量r中

2、；③更新被除数和余数：m=n，n=r；④判断余数r是否为0.若r=0，则m，n的最大公约数等于m；否则转向第②步继续循环执行.如此循环，直到得到结果为止.算法案例【求最大公约数】（4）更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术.在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.步骤：Ⅰ．任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.Ⅱ．以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这操作，直到所得的数相等为止，则这

3、个数（等数）就是所求的最大公约数.算法案例【秦九韶算法】秦九韶算法的一般规则：秦九韶算法适用一般的多项式的求值问题.用秦九韶算法求一般多项式算法案例【秦九韶算法】当x=x0时的函数值，可把n次多项式的求值问题转化成求n个一次多项式的值的问题，即求v0=anv1=anx+an－1v2=v1x+an－2v3=v2x+an－3……vn=vn－1x+a0观察秦九韶算法的数学模型，计算vk时要用到vk－1的值，若令v0=an.我们可以得到下面的递推公式：v0=anvk=vk－1+an－k(k=1,2,…n)这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现.算法案例【进位制】(

4、1)概念进位制是为了计数和运算方便而约定的记数系统，约定“满几进一”就是几进制，几进制的基数（大于1的整数）就是几.对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.一般地，若k是一个大于一的整数，那么以k为基数的k进制可以表示为：anan-1…a1a0(k)(0

5、的转换，教科书上以十进制和二进制之间的转换为例讲解，并推广到十进制和其它进制之间的转换.这样做的原因是，计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，显然运算后首次得到的结果为二进制数，同时计算机又把运算结果由二进制数转换成十进制数输出.算法案例【进位制】非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：;anan-1…a1a0(k)=an×kn+an-1×kn-1+…a1×k+a0第一步：从左到右依次取出k进制数anan1……a1a0(k)各位上的数字，乘以相应的k的幂，k的

6、幂从n开始取值，每次递减1，递减到0，即an×kn,an-1×kn-1,…,a1×k,a0×k0;第二步：把所得到的乘积加起来，所得的结果就是相应的十进制数.算法案例【进位制】十进制数转换成非十进制数把十进制数转换为二进制数，教科书上提供了“除2取余法”，我们可以类比得到十进制数转换成k进制数的算法“除k取余法”.非十进制之间的转换一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与16进制数据之间的互化的方法，也就是先由二进制数转化为十进制数，再由十进制数转化成为16进制数.算法案例【典型例题】1、(1)用辗转相除法求123和48的最大公约数？(2)用更相减损

7、来求80和36的最大公约数？解析:(1)辗转相除法求最大公约数的过程如下：（建立带余除式）123＝2×48＋2748＝1×27＋2127＝1×21＋621＝3×6＋36＝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下