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

计算机算法设计与分析（第3版）,王通 天津工程师范学院计算机系,第3章 迭代和递推算法,教学目标： 理解迭代法及其特点 理解什么是递推法及其特点 用递推法设计算法的基本过程 能够根据具体问题的要求，学会用递推法实现算法编写程序,第3章 迭代和递推算法,给你一张足够大的厚为0.1毫米的纸，你所要做的是重复这样的动作: 对折，不停地对折。 我的问题就是，折叠多少次后超过世界屋脊珠穆朗玛峰的高度8848米？ 当你把这张纸对折了51次的时候，所达到的厚度有多少？,第3章 迭代和递推算法-迭代法,求方程f(x)=x3-x-1=0 在x0=1.5附近的根x*,第3章 迭代和递推算法-迭代法,迭代法 求方程或方程组近似根的一种常用算法。 步骤： 1、选一个方程的近似根，赋给x0 2、将x0保存在变量x1中，然后计算x0=g(x1) 3、当x0 与x1差的绝对值还不小于指定的精度要求时，重复计算。否则结束。,第3章 迭代和递推算法-迭代法, x0=初始近似根； do x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ While(fabs(x0-x1)E) printf(“方程的近似根是%fn“，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. 若只有一个台阶，上山方式只有一种，即al1。 若有两个台阶，可以两小步(每步一个台阶)上去，也可以一大步(上两个台阶)上去，即a22。,第3章 迭代和递推算法-递推法,若有三个台阶，可以全用小步上去，也可一大一小，或一小一大，因此，a33。 若有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章 递推算法,如何建立递推关系？目前尚未总结出一个一般的方法，只能具体问题，具体分析。 建立递推关系，必须对所提出的问题，进行深入细致的分析。 先从最简单的情况分析入手，看n1，n2，时的情况如何，这就是先建立初条件。,第3章 递推算法,而后，从nk - 1(有时用到nk - 2，nk - 3，)时，去推出nk的情况，这种推测就是建立在先验印象的基础上的。因此，便于摸清变化规律，而得出正确的递推关系.,斐波那契兔子问题,公元1202年，商人出身的意大利数学家斐波那契（Fibonacci，11701250），完成了一部伟大的论著算法之书。在书中，提出以下有趣问题： 假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对小兔。一年内没有发生死亡，问一对刚出生的兔子，一年内繁殖成多少对兔子？(假定以上兔子都是雌雄成对)？,第3章 递推算法-斐波那契兔子问题,其中A表示一对大兔子，B表示一对小兔子,第3章 递推算法-斐波那契兔子问题,逐月推算，我们可以得到前面提过的数列： 1，1，2，3，5，8，13，21，34，55，89，144，233。这个数列后来便以斐波那契的名字命名。数列的每一项，则称为斐波那契数。”第十三位的斐波那契数，即为一对刚出生的小兔，一年内所能繁殖成的兔子的对数，这个数字为233。 从斐波那契数的构造明显看出：斐波那契数列从第三项起，每项都等于前面两项的和。假定第n项斐波那契数为fn，于是我们有：,第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. (初始化) a1，b1，c2，k3。 4. (完成？) 若k=n则输出c值，算法终止。 5. (从和计算) ab，bc， ca + b。 6. (记录当前项号) kk + 1。 7. (转去计算下一项) 转到4。,第3章 递推算法-斐波那契兔子问题,第3章 递推算法,Main() scanf(“%d”, printf(“%d”,fi ) ,算法描述： 1、定义初值 2、变量i从3增到n 3、计算fi=fi-1+ fi-2; 4、输出fi,第3章 递推算法- 阶乘计算,问题描述：对给定的n（n100），计算并输出k的阶乘k！（k=1，2，n）的全部有效数字。,用递推法求解阶乘函数的思路是：先求fac(1)，再求fac(2)，,直到求出fac(n),Main() Int n; Int facn=0 Int m=1; for(int i=1;i=n;i+) m=m*i faci=m; for(int i=1;i=n;i+) Cout faciendl; ,棋盘放米问题,第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次方米，于是总厚度就