资源描述
四四.算法案例算法案例多项式求值的秦九韶方法多项式求值的秦九韶方法 nnnxaxaxaaxP22101n xPnktkukkxt kk2210kxaxaxaau kk1kk1kktauuxttn, 2 , 1k (3.4.2)作为递推公式(3.4.2)的初值为: 000au1t(3.4.3)(1)逐项法多项式求值。 输入：存放 的系数数组A(0：n）； xPn自变量x值。其中1n 输出： 值P xPn xt;x1A0Ap tiAPP;xtt 012n1nnnaxaxaxaxaxP k1kknnaxuuau0 , 1 , 1 nk 0nuxP xPn xPn1n nAP iAxPP 例. 中国剩余定理（孙子定理）若k2，且m1，m2，mk是两两互素的k个正整数，令M= m1m2mk=m1M1=m2M2=mkMk。 则同余式组：x1=b1(modm1)，x2=b2(modm2)，xk=bk(modmk) 其正整数解是：Xb1M1M1+b2M2M2+bkMkMk(modM) 其中Mi是满足同余式： MiMi1(mod mi) （i = 1，2k） 用孙子定理解同余式组： xi=bi(modmi) （ i = 1，2k ）的算法步骤如下：kiiiiiiiiiiikiiMbaxMM, ., k)(imMMMkimMMmM1i0)(mod a . 31 )(mod1 . 2)., , 1( . 1数解是：，则同余方程组的正整令的同余方程：分别解关于分别计算设2.对半法查找对半法查找(二分法二分法)算法算法对这种算法的实质是在一个有限且有序的对象中，通过每次缩减一半查找范围而达到迅速确定目的一个有效算法。因此有着很广泛的应用。例如，在数学中有很多方程是写不出根的解析表达式的，但是根的存在范围比较容易确定，那么如何才能找到它的根的一个足够准确的近似值呢？这时对半查找算法就可以大显身手了。由初等函数f(x)=0构成的方程，如果有f(a)f(b)0，则可以肯定方程f(x)=0在（a , b）至少有一个实数根。 选择（a , b）的中点c，若f(c)=0，则根就是x=c。若f(c)0，则用c值取代相应的a或b（取代原则是：保证有f(a)f(b) a b c 10，abc=30723，且，且a b+c，试确定，试确定a、b、c的值。的值。分析问题分析问题解决这个问题应当从解决这个问题应当从abc=30723入手。把入手。把30723三个整三个整数相乘的积，只能有有限种情况，我们可以把这些情况一一数相乘的积，只能有有限种情况，我们可以把这些情况一一罗列出来，然后分析哪一种情况是符合条件的。从而找到答罗列出来，然后分析哪一种情况是符合条件的。从而找到答案。案。(在列举所有情况时，注意三个因子都大于在列举所有情况时，注意三个因子都大于10，这可以减，这可以减少列举的工作量少列举的工作量)。把把30723分解为分解为3个大于个大于10的因子的乘积只有的因子的乘积只有5种情况种情况1119147(三个因子的和是三个因子的和是177)1121133(三个因子的和是三个因子的和是165)194957 (三个因子的和是三个因子的和是101)114957 (三个因子的和是三个因子的和是117)192177 (三个因子的和是三个因子的和是117)在这在这5种情况中考察，符合种情况中考察，符合ab+c而且最大的数小于而且最大的数小于100的，的，只有最后一种情况，即只有最后一种情况，即a=77，b=21，c=19。计算算法计算算法设计穷举算法的关键是如何列举所有可能的情况，绝对不能设计穷举算法的关键是如何列举所有可能的情况，绝对不能遗漏，最好不要重复。在列举时注意变量的范围，可以减少遗漏，最好不要重复。在列举时注意变量的范围，可以减少工作量。工作量。我们可以从最小的变量我们可以从最小的变量c入手，让它从入手，让它从10开始变化。但变化开始变化。但变化的范围到哪里为止呢？粗略估算一下，三个数相乘是的范围到哪里为止呢？粗略估算一下，三个数相乘是30723，最小的最小的c不超过它的立方根。我们可以用平方根做近似替代，不超过它的立方根。我们可以用平方根做近似替代，不必作太多推算。不必作太多推算。当当c值产生之后，就可以处理变量值产生之后，就可以处理变量b。因为它不小于。因为它不小于c，让它，让它从从c开始，也让它变化到开始，也让它变化到30723的平方根。的平方根。有了有了c和和b的值之后，就要判断他们是否都是的值之后，就要判断他们是否都是30723的因子。的因子。如果是，计算出第三个因子如果是，计算出第三个因子a，然后进行判断：，然后进行判断：a是否大于是否大于b+c并且并且a100。满足条件就是解答了。满足条件就是解答了。例题例题 (钱币问题钱币问题)在日程生活中常常需要用一些较小面额的钱币去组合出一定的币值。现有面值为1元、2元和5元的钞票(假设每种钞票的数量都足够多)，从这些钞票中取出30张使其总面值为100元，问有多少种取法？每种取法的各种面值的钞票各为多少张？分析问题分析问题显然列出一条算式来解决钱币问题是有困难的。既然解析法很难用上，我们尝试通过列举所有可能的情况(穷举)，从中判断出合符条件的解答。 当钞票数量比较多，总币值比较大时，人工列举所有钞票组合(穷举)就很麻烦，这时需要使用计算机来帮我们穷举。但使用计算机来穷举，必须清楚地说出穷举的每一个步骤，并通过程序设计语言转化为计算机能后执行的过程，才能解决问题。 钱币问题有3种面额的钞票，钞票的总张数是30张，又应当如何穷举呢？经分析可以知道：当有两种面额的钞票数目确定了之后，可以从总张数为30确定第三种钞票的张数，然后由总面额是否100元而判断这个组合是否合乎要求。此外，先确定面额大的钞票可以使穷举的次数少些。设计算法设计算法 用ONE、TWO、FIVE分别记录1元、2元、5元钞票的张数。变量ANSWER记录符合条件的解的数目。穷举的过程如下：让ANSWER=0，FIVE=0；TWO=0让ONE=30 TWO FIVE；检查5FIVE2TWOONE 是否等于100，若是， 则得到一组解，这时让ANSWER增加1。并且输出解答如果TWO30，那么让TWO增加1，转步骤；如果FIVE20，那么让FIVE增加1，转步骤结束可把这些步骤用框图表示如图4-7：Click to display汉诺汉诺(Hanoi)塔问题是一个著名的应用递归算法解决的问题。塔问题是一个著名的应用递归算法解决的问题。 问题问题4-17： 传说在古代印度的贝拿勒斯神庙里安放了一块黄铜板，传说在古代印度的贝拿勒斯神庙里安放了一块黄铜板，板上插了三根宝石柱，在其中一根宝石柱自上而下由小到大板上插了三根宝石柱，在其中一根宝石柱自上而下由小到大地叠放着地叠放着64个大小不等的金盘。一名僧人把这些金盘从一根个大小不等的金盘。一名僧人把这些金盘从一根宝石柱移到另外一根上。僧人在移动金盘时遵守下面宝石柱移到另外一根上。僧人在移动金盘时遵守下面3条规条规则：则：一次只能移动一个金盘。一次只能移动一个金盘。每个金盘只能由一根宝石柱移到另外一根宝石柱。每个金盘只能由一根宝石柱移到另外一根宝石柱。任何时候都不能把大的金盘放在小的金盘上。任何时候都不能把大的金盘放在小的金盘上。神化说，如果僧人把64个金盘完全地从一根宝石柱移到了另外一根上，世界的末日就要到了。当然，神化只能当故事听，世界不可以因为个别人的活动而导致末日。不过，如果能够计算出僧人按规则搬完64个金盘，地球能否继续存在也的确是个问题！因为即使僧人的动作十分敏捷，每秒都能移动一个金盘，那也得要几亿年！分析问题分析问题 要模拟金盘的移动过程是比较困难的，但如果用递归的思想来进行(压缩规模，把问题解决在最简单的情况)，则问题可以解决。 我们把3根宝石柱分别命名为A、B、C。最初有N个金盘放在A，需要把它们全部按规则移动到B。 当N=1时，直接把金盘从A搬到B就可以了，1次成功。 当N2，那么需要利用C柱来过渡。按照递归的思想，我们假设已经找到一种把N1个金盘从一根柱搬到另外一根柱的方法，然后看看如何通过它来实现搬动N个金盘。我们只要把N1个金盘从A搬到C，然后把最大的金盘从A搬到B，最后把C上的N1个金盘搬到B就可以了。靠递归的思想，我们轻而易举地完成了整个搬动。设计算法设计算法我们定义一个过程Hanoi(N，A，B，C)，表示有N个金盘需要从A柱搬到B柱(以C柱为过渡)。那么完成它只需3步：Hanoi(N1，A，C，B)它的意思是把A柱上的N1个金盘搬到C柱，AB它的意思是把一个(最大的)金盘从A柱搬到B柱，Hanoi(N，C，B，A)它的意思是把C柱上的N1个金盘搬到B柱。
展开阅读全文