2004年成人高考政治试题及答案下(专升本)

计算机算法设计与分析（第3版）王通天津工程师范学院计算机系第3章迭代和递推算法教学目标：理解迭代法及其特点理解什么是递推法及其特点用递推法设计算法的基本过程能够根据具体问题的要求，学会用递推法实现算法编写程序第3章迭代和递推算法给你一张足够大的厚为0.1毫米的纸，你所要做的是重复这样的动作:对折，不停地对折。我的问题就是，折叠多少次后超过世界屋脊珠穆朗玛峰的高度8848米？当你把这张纸对折了51次的时候，所达到的厚度有多少？第3章迭代和递推算法-迭代法求方程f(x)=x3-x-1=0在x0=1.5附近的根x*第3章迭代和递推算法-迭代法迭代法求方程或方程组近似根的一种常用算法。步骤：1、选一个方程的近似根，赋给x02、将x0保存在变量x1中，然后计算x0=g(x1)3、当x0与x1差的绝对值还不小于指定的精度要求时，重复计算。否则结束。第3章迭代和递推算法-迭代法{x0=初始近似根；do{x1=x0;x0=g(x1);/*按特定的方程计算新的近似根*/}While(fabs(x0-x1)E)printf(方程的近似根是%f\n，x0)；}第3章迭代和递推算法-迭代法难点：1、方程无解2、方程有解，但迭代公式选择不当，或初始近似根选择不合理，会导致迭代失败。举例求方程f(x)=x5-x-1=0在x0=1.5附近的根x*例第3章迭代和递推算法-迭代法例2用牛顿迭代公式x=x0-f(x0)/f'(x0)求解sqrt(2)设sqrt(2)=x即x2-2=0则令f(x)=x2-2所以f'(x)=2x所以有迭代公式x=1/2*(x0+2/x0)第3章迭代和递推算法-递推法考察一个我们熟知的计算：4*9。这种从头开始一步步递推出问题最终结果的方法，就是递推(recurrence)方法。递推是序列计算中的一种常用方法。它是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。第3章迭代和递推算法-递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。第3章迭代和递推算法-递推法例要爬到一个小山的顶点，需要上100个台阶.可以一步上一个台阶，也可以一步上两个台阶，有多少种不同的上山方式呢？解设爬山的台阶数为n，上到第n个台阶的方式数为an.若只有一个台阶，上山方式只有一种，即al＝1。若有两个台阶，可以两小步(每步一个台阶)上去，也可以一大步(上两个台阶)上去，即a2＝2。第3章迭代和递推算法-递推法若有三个台阶，可以全用小步上去，也可一大一小，或一小一大，因此，a3＝3。若有n个台阶，上到第n个台阶的方式数为an,可分成两类，第一类是从第n一1个台阶迈一小步上去的，共有an-1种；第二类是从第n-2个台阶迈一大步上去的，共有an-2种。由于最后一步的上法不同，所以这两类上法是不同的。所以这样求得的上山方式数为an＝an-1+an-2一直算下去，当然可以得到a100的值，这就是问题的解。第3章递推算法能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。难点：递推法关键是找递推关系，并确定初值。编程时递推向前传递变量值的时序，不能颠倒。第3章递推算法如何建立递推关系？目前尚未总结出一个一般的方法，只能具体问题，具体分析。建立递推关系，必须对所提出的问题，进行深入细致的分析。先从最简单的情况分析入手，看n＝1，n＝2，…时的情况如何，这就是先建立初条件。第3章递推算法而后，从n＝k-1(有时用到n＝k-2，n＝k-3，…)时，去推出n＝k的情况，这种推测就是建立在先验印象的基础上的。因此，便于摸清变化规律，而得出正确的递推关系.斐波那契兔子问题公元1202年，商人出身的意大利数学家斐波那契（Fi－bonacci，1170～1250），完成了一部伟大的论著《算法之书》。在书中，提出以下有趣问题：假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对小兔。一年内没有发生死亡，问一对刚出生的兔子，一年内繁殖成多少对兔子？(假定以上兔子都是雌雄成对)？第3章递推算法-斐波那契兔子问题其中A表示一对大兔子，B表示一对小兔子第3章递推算法-斐波那契兔子问题逐月推算，我们可以得到前面提过的数列：1，1，2，3，5，8，13，21，34，55，89，144，233。这个数列后来便以斐波那契的名字命名。数列的每一项，则称为斐波那契数。”第十三位的斐波那契数，即为一对刚出生的小兔，一年内所能繁殖成的兔子的对数，这个数字为233。从斐波那契数的构造明显看出：斐波那契数列从第三项起，每项都等于前面两项的和。假定第n项斐波那契数为fn，于是我们有：321)2()1(11)(nnnnFnFnF第3章递推算法-斐波那契兔子问题算法描述：按照斐波那契数列中各项的关系，可以使用四个变量a、b、c和k来计算，这四个变量的用途如下：a存贮Fk-2。b存贮Fk-1。c存贮Fk，可以通过a+b，从Fk-2和Fk-1来计算Fk。k记录变量c中存贮的当前项的项号。第3章递推算法-斐波那契兔子问题第3章递推算法-斐波那契兔子问题下面是用自然语言描述的算法：1.(输入项号)输入项号n。2.(是最初二项之一？)若n3则输出1，算法终止。3.(初始化)a←1，b←1，c←2，k←3。4.(完成？)若k=n则输出c值，算法终止。5.(从和计算)a←b，b←c，c←a+b。6.(记录当前项号)k←k+1。7.(转去计算下一项)转到4。第3章递推算法-斐波那契兔子问题第3章递推算法Main(){scanf(“%d”,&n);If(n3)printf(“%d”,1);intf1=1;f2=1;i=3;while(i=n){fi=f1+f2f1=f2;f2=fi;i++;}printf(“%d”,fi)}算法描述：1、定义初值2、变量i从3增到n3、计算f[i]=f[i-1]+f[i-2];4、输出f[i]第3章递推算法-阶乘计算问题描述：对给定的n（n≦100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。00)!1(1!nnnnn用递推法求解阶乘函数的思路是：先求fac(1)，再求fac(2)，…,直到求出fac(n)Main(){Intn;Intfac[n]={0}Intm=1;for(inti=1;i=n;i++){m=m*ifac[i]=m;}for(inti=1;i=n;i++)Coutfac[i]endl;}棋盘放米问题第3章递推算法有个智者和国王下棋，国王答应如果智者胜了可以得到他想要的任何东西。结果智者胜了，他的要求不高，就要国王在64格的棋盘上放米，第一格放一粒，第二格放两粒，第三格放四粒……以此类推，每格放的米粒数都是前一格的平方。国王以为这很容易，就答应了，结果发现他把国库所有的米都放上都不够。第3章递推算法其实懂数学的都知道，第一格的米粒数可以写成数学计算式=2的0次方，那么，第二格的米粒数是2的1次方，第三格的米粒数是2的2次方，第4格的米粒数是2的3次方，那么，第n个格的米粒数就是2的（n-1）次方，第3章递推算法棋盘只有64个格子，算出来的数字竟然是2的63次方等于9,223,372,036,854,780,000粒，那还只是第64格所放米粒的数量,如果全部累计,则总共需要18,446,744,073,709,600,000粒,如果1000粒米有1克重，那么第64格的米就是9,223,372,036吨,全部相加就是18,446,744,073,709吨.从上述图示中，我们可以知道这是一个等比级数20+21+22+23+24+……+263求和的数学问题。棋盘放米问题第3章递推算法问题：给你一张足够大的厚为0.1毫米的纸，你所要做的是重复这样的动作:对折，不停地对折。我的问题就是，折叠多少次后超过世界屋脊珠穆朗玛峰的高度8848米？当你把这张纸对折了51次的时候，所达到的厚度有多少？流程图第3章递推算法如果一张报纸厚度是0.1毫米，连叠51次后就有2的51次方张报纸，大概等于10的15.3次方，0.1毫米等于10的-4次方米，于是总厚度就是10的11.3次方米，也就是不到2亿公里，地球和太阳的距离是1.5亿公里。思考猴子吃桃子小猴在一天摘了若干个桃子，当天吃掉一半多一个；第二天接着吃剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第七天早上要吃时只剩下一个了，问小猴那天共摘下了多少个桃子？提示：采用倒推法，先从最后一天推出倒数第二天的桃子，在从倒数第二天的桃子推出倒数第三天的桃子。