成人高考政治试题与答案下专升本

1、成人高考政治试题与答案下 专升本 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法 教学目标： 理解迭代法及其特点 理解什么是递推法及其特点 用递推法设计算法的基本过程 能够根据具体问题的要求，学会用递推法实现算 法编写程序 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法 给你一张足够大的厚为给你一张足够大的厚为0.1毫米的纸，你所要做毫米的纸，你所要做 的是重复这样的动作的是重复这样的动作: 对折，不停地对折。对折，不停地对折。 我的问题就是，折叠多少次后超过世界屋脊珠穆我的问题就是，折叠多少次后超过世界屋脊珠穆 朗玛峰的高度朗玛峰的高度88

2、48米？米？ 当你把这张纸对折了当你把这张纸对折了51次的时候，所达到的厚度次的时候，所达到的厚度 有多少？有多少？ 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-迭代法 求方程求方程f(x)=x3-x-1=0 在在x0=1.5附近的根附近的根x* 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-迭代法 迭代法迭代法 求方程或方程组近似根的一种常用算法。求方程或方程组近似根的一种常用算法。 步骤：步骤： 1、选一个方程的近似根，赋给、选一个方程的近似根，赋给x0 2、将、将x0保存在变量保存在变量x1中，然后计算中，然后计算x0=g(x1)

3、 3、当、当x0 与与x1差的绝对值还不小于指定的精度差的绝对值还不小于指定的精度 要求时，重复计算。否则结束。要求时，重复计算。否则结束。 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-迭代法 x0=初始近似根；初始近似根； do x1=x0; x0=g(x1); /*按特定的方程计算新的近似根按特定的方程计算新的近似根 */ While(fabs(x0-x1)E) printf(方程的近似根是方程的近似根是%fn，x0)； 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-迭代法 难点：难点： 1、方程无解、方程无解 2、方程有解，但迭代

4、公式选择不当，或初、方程有解，但迭代公式选择不当，或初 始近似根选择不合理，会导致迭代失败。始近似根选择不合理，会导致迭代失败。 举例举例 求方程求方程f(x)=x5-x-1=0 在在x0=1.5附近的根附近的根x* 例 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-迭代法 例例2 用牛顿迭代公式用牛顿迭代公式 x=x0-f(x0)/f(x0)求解求解 sqrt(2) 设设sqrt(2)=x sqrt(2)=x 即即 x x2 2-2=0 -2=0 则令则令 f(x)=xf(x)=x2 2-2 -2 所所 以以 f(x)=2x f(x)=2x 所以有迭代公式所以有迭

5、代公式 x=1/2x=1/2* *(x0+2/x0) (x0+2/x0) 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-递推法递推法 考察一个我们熟知的计算：考察一个我们熟知的计算：4 * 9。 这种从头开始一步步递推出问题最终结果这种从头开始一步步递推出问题最终结果 的方法，就是递推的方法，就是递推(recurrence)(recurrence)方法。方法。 递推是序列计算中的一种常用方法。它是递推是序列计算中的一种常用方法。它是 按照一定的规律来计算序列中的每个项，按照一定的规律来计算序列中的每个项， 通常是通过计算前面的一些项来得出序列通常是通过计算前面的一些

6、项来得出序列 中的指定项的值。中的指定项的值。 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-递推法递推法 递推法是利用问题本身所具有的一种递推关递推法是利用问题本身所具有的一种递推关 系求问题解的一种方法。系求问题解的一种方法。 设要求问题规模为设要求问题规模为N N的解，当的解，当N=1N=1时，解时，解 或为已知，或能非常方便地得到解。或为已知，或能非常方便地得到解。 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-递推法递推法 例例 要爬到一个小山的顶点，需要上要爬到一个小山的顶点，需要上100个台阶个台阶. 可以一可以一 步上一个

7、台阶，也可以一步上两个台阶，有多少种不步上一个台阶，也可以一步上两个台阶，有多少种不 同的上山方式呢？同的上山方式呢？ 解解 设爬山的台阶数为设爬山的台阶数为n，上到第，上到第n个台阶的方式数为个台阶的方式数为an. 若只有一个台阶，上山方式只有一种，即若只有一个台阶，上山方式只有一种，即al1。 若有两个台阶，可以两小步若有两个台阶，可以两小步(每步一个台阶每步一个台阶)上去，也可上去，也可 以一大步以一大步(上两个台阶上两个台阶)上去，即上去，即a22。 成人高考政治试题与答案下专升本 第第3章章 迭代和递推算法迭代和递推算法-递推法递推法 若有三个台阶，可以全用小步上去，也可一大一小，若

8、有三个台阶，可以全用小步上去，也可一大一小， 或一小一大，因此，或一小一大，因此，a33。 若有若有n个台阶，上到第个台阶，上到第n个台阶的方式数为个台阶的方式数为an, 可分成可分成 两类，第一类是从第两类，第一类是从第n一一1个台阶迈一小步上去的，个台阶迈一小步上去的， 共有共有an-1种；第二类是从第种；第二类是从第n-2个台阶迈一大步上个台阶迈一大步上 去的，共有去的，共有an-2种。由于最后一步的上法不同，所种。由于最后一步的上法不同，所 以这两类上法是不同的。所以这样求得的上山方式以这两类上法是不同的。所以这样求得的上山方式 数为数为 an an-1 + an-2 一直算下去，当然

9、可以得到一直算下去，当然可以得到a100a100的值，这就是问题的的值，这就是问题的 解。解。 成人高考政治试题与答案下专升本 第第3章章 递推算法递推算法 能采用递推法构造算法的问题有重要的递推性质，即能采用递推法构造算法的问题有重要的递推性质，即 当得到问题规模为当得到问题规模为i-1i-1的解后，由问题的递推性质，的解后，由问题的递推性质， 能从已求得的规模为能从已求得的规模为1 1，2 2，i-1i-1的一系列解，的一系列解， 构造出问题规模为构造出问题规模为I I的解。这样，程序可从的解。这样，程序可从i=0i=0或或 i=1i=1出发，重复地，由已知至出发，重复地，由已知至i-1i

10、-1规模的解，通过递规模的解，通过递 推，获得规模为推，获得规模为i i的解，直至得到规模为的解，直至得到规模为N N的解。的解。 难点：递推法关键是找递推关系，并确定初值。难点：递推法关键是找递推关系，并确定初值。 编程时递推向前传递变量值的时序，不能颠倒。编程时递推向前传递变量值的时序，不能颠倒。 成人高考政治试题与答案下专升本 第第3章章 递推算法递推算法 如何建立递推关系？目前尚未总结出一个一般如何建立递推关系？目前尚未总结出一个一般 的方法，只能具体问题，具体分析。的方法，只能具体问题，具体分析。 建立递推关系，必须对所提出的问题，进行深建立递推关系，必须对所提出的问题，进行深 入细

11、致的分析。入细致的分析。 先从最简单的情况分析入手，看先从最简单的情况分析入手，看n1，n 2，时的情况如何，这就是先建立初条件。时的情况如何，这就是先建立初条件。 成人高考政治试题与答案下专升本 第第3章章 递推算法递推算法 而后，从而后，从nk - 1(有时用到有时用到nk - 2，nk - 3，)时，去推出时，去推出nk的情况，这种推测就的情况，这种推测就 是建立在先验印象的基础上的。因此，便于是建立在先验印象的基础上的。因此，便于 摸清变化规律，而得出正确的递推关系摸清变化规律，而得出正确的递推关系. 成人高考政治试题与答案下专升本 斐波那契兔子问题 成人高考政治试题与答案下专升本 公

12、元公元12021202年，商人出身的意大利数学家斐波那契（年，商人出身的意大利数学家斐波那契（FiFi bonaccibonacci，1170117012501250），完成了一部伟大的论著），完成了一部伟大的论著 算法之书算法之书。在书中，提出以下有趣问题：。在书中，提出以下有趣问题： 假定一对刚出生的小兔一个月后就能长成大兔，再过假定一对刚出生的小兔一个月后就能长成大兔，再过 一个月便能生下一对小兔，并且此后每个月都生一对一个月便能生下一对小兔，并且此后每个月都生一对 小兔。一年内没有发生死亡，问一对刚出生的兔子，小兔。一年内没有发生死亡，问一对刚出生的兔子， 一年内繁殖成多少对兔子？一年

13、内繁殖成多少对兔子？(假定以上兔子都是雌雄假定以上兔子都是雌雄 成对成对)？ 第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题 成人高考政治试题与答案下专升本 其中其中A表示一对大兔子，表示一对大兔子，B表示一对小兔子表示一对小兔子 第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题 成人高考政治试题与答案下专升本 逐月推算，我们可以得到前面提过的数列：逐月推算，我们可以得到前面提过的数列： 1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，8989，144144，233233。这个数。这个数 列后来便以斐波那契的名字命名。数列的

14、每一项，则称为斐波列后来便以斐波那契的名字命名。数列的每一项，则称为斐波 那契数。那契数。”第十三位的斐波那契数，即为一对刚出生的小兔，第十三位的斐波那契数，即为一对刚出生的小兔， 一年内所能繁殖成的兔子的对数，这个数字为一年内所能繁殖成的兔子的对数，这个数字为233233。 从斐波那契数的构造明显看出：斐波那契数列从第三项起，每从斐波那契数的构造明显看出：斐波那契数列从第三项起，每 项都等于前面两项的和。假定第项都等于前面两项的和。假定第n n项斐波那契数为项斐波那契数为fnfn，于是我，于是我 们有：们有： 3 2 1 )2() 1( 1 1 )( n n n nFnF nF 第第3章章

15、递推算法递推算法-斐波那契兔子问题斐波那契兔子问题 成人高考政治试题与答案下专升本 算法描述：算法描述： 按照斐波那契数列中各项的关系，可以使用四按照斐波那契数列中各项的关系，可以使用四 个变量个变量a、b、c和和k来计算，这四个变量的用途来计算，这四个变量的用途 如下：如下： a 存贮存贮Fk-2。 b 存贮存贮Fk-1。 c 存贮存贮Fk ，可以通过，可以通过a+b，从，从Fk-2和和Fk-1来计算来计算Fk 。 k 记录变量记录变量c中存贮的当前项的项号。中存贮的当前项的项号。 第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题 成人高考政治试题与答案下专升本 第第3章章 递

16、推算法递推算法-斐波那契兔子问题斐波那契兔子问题 成人高考政治试题与答案下专升本 下面是用自然语言描述的算法：下面是用自然语言描述的算法： 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章章 递推算法递推算法-

17、斐波那契兔子问题斐波那契兔子问题 成人高考政治试题与答案下专升本 第第3章章 递推算法递推算法 Main() scanf(“%d”, If (n3) printf(“%d”,1 ) ; int f1=1;f2=1;i=3; while(i=n) fi=f1+f2 f1=f2; f2=fi; i+; 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）的全部

18、有效数字。 0 0 )!1( 1 ! n n nn 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章章 递推算法递推算法 有个智者和国王下棋，国王答应如果智者胜了 可以得到他想要的任何东西。结果智者胜了， 他的要求不高，就要

19、国王在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 克重，那么