2004年成人高考政治试题和答案下〔专升本〕.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(方程的近似根是%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) 第3章 迭代和递推算法-递推法 考察一个我们熟知的计算：4 * 9。 第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），完成了一部伟大的论著《算法之书》。在书中，提出以下有趣问题： 假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对小兔。一年内没有发生死亡，问一对刚出生的兔子，一年内繁殖成多少对兔子？(假定以上兔子都是雌雄成对)？ 逐月推算，我们可以得到前面提过的数列： 1，1，2，3，5，8，13，21，34，55，89，144，233。这个数列后来便以斐波那契的名字命名。数列的