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

1、.计算机算法设计与分析（第计算机算法设计与分析（第3版）版）王通王通天津工程师范学院计算机系天津工程师范学院计算机系.第第3章章 迭代和递推算法迭代和递推算法教学目标：理解迭代法及其特点理解什么是递推法及其特点用递推法设计算法的基本过程能够根据具体问题的要求，学会用递推法实现算法编写程序.第第3章章 迭代和递推算法迭代和递推算法 给你一张足够大的厚为给你一张足够大的厚为0.1毫米的纸，你所要做毫米的纸，你所要做的是重复这样的动作的是重复这样的动作: 对折，不停地对折。对折，不停地对折。我的问题就是，折叠多少次后超过世界屋脊珠穆我的问题就是，折叠多少次后超过世界屋脊珠穆朗玛峰的高度朗玛峰的高度8

2、848米？米？当你把这张纸对折了当你把这张纸对折了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、小于指定的精度要求时，重复计算。否则结束。要求时，重复计算。否则结束。 .第第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 所以有迭代公式所以有迭代公式 x=1/2x=1/2* *(x0+2/x0) (x0+2/x0) .第第3章章 迭代和递推算法迭代和递推算法-递推法递推法考察一个我们熟知的计算：考察一个我们熟知的计

5、算：4 * 9。这种从头开始一步步递推出问题最终结果这种从头开始一步步递推出问题最终结果的方法，就是递推的方法，就是递推(recurrence)(recurrence)方法。方法。递推是序列计算中的一种常用方法。它是递推是序列计算中的一种常用方法。它是按照一定的规律来计算序列中的每个项，按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列通常是通过计算前面的一些项来得出序列中的指定项的值。中的指定项的值。 .第第3章章 迭代和递推算法迭代和递推算法-递推法递推法递推法是利用问题本身所具有的一种递推关递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。系求问题解的一种

6、方法。 设要求问题规模为设要求问题规模为N N的解，当的解，当N=1N=1时，解时，解或为已知，或能非常方便地得到解。或为已知，或能非常方便地得到解。.第第3章章 迭代和递推算法迭代和递推算法-递推法递推法 例例 要爬到一个小山的顶点，需要上要爬到一个小山的顶点，需要上100个台阶个台阶. 可以一可以一步上一个台阶，也可以一步上两个台阶，有多少种不步上一个台阶，也可以一步上两个台阶，有多少种不同的上山方式呢？同的上山方式呢？解解 设爬山的台阶数为设爬山的台阶数为n，上到第，上到第n个台阶的方式数为个台阶的方式数为an. 若只有一个台阶，上山方式只有一种，即若只有一个台阶，上山方式只有一种，即a

7、l1。 若有两个台阶，可以两小步若有两个台阶，可以两小步(每步一个台阶每步一个台阶)上去，也可上去，也可以一大步以一大步(上两个台阶上两个台阶)上去，即上去，即a22。.第第3章章 迭代和递推算法迭代和递推算法-递推法递推法若有三个台阶，可以全用小步上去，也可一大一小，若有三个台阶，可以全用小步上去，也可一大一小，或一小一大，因此，或一小一大，因此，a33。若有若有n个台阶，上到第个台阶，上到第n个台阶的方式数为个台阶的方式数为an, 可分成可分成两类，第一类是从第两类，第一类是从第n一一1个台阶迈一小步上去的，个台阶迈一小步上去的，共有共有an-1种；第二类是从第种；第二类是从第n-2个台阶

8、迈一大步上个台阶迈一大步上去的，共有去的，共有an-2种。由于最后一步的上法不同，所种。由于最后一步的上法不同，所以这两类上法是不同的。所以这样求得的上山方式以这两类上法是不同的。所以这样求得的上山方式数为数为 an an-1 + an-2 一直算下去，当然可以得到一直算下去，当然可以得到a100a100的值，这就是问题的的值，这就是问题的解。解。.第第3章章 递推算法递推算法能采用递推法构造算法的问题有重要的能采用递推法构造算法的问题有重要的递推性质递推性质，即，即当得到问题规模为当得到问题规模为i-1i-1的解后，由问题的递推性质，的解后，由问题的递推性质，能从已求得的规模为能从已求得的规

9、模为1 1，2 2，i-1i-1的一系列解，的一系列解，构造出问题规模为构造出问题规模为I I的解。这样，程序可从的解。这样，程序可从i=0i=0或或i=1i=1出发，重复地，由已知至出发，重复地，由已知至i-1i-1规模的解，通过递规模的解，通过递推，获得规模为推，获得规模为i i的解，直至得到规模为的解，直至得到规模为N N的解。的解。难点：递推法关键是找递推关系，并确定初值。难点：递推法关键是找递推关系，并确定初值。 编程时递推向前传递变量值的时序，不能颠倒。编程时递推向前传递变量值的时序，不能颠倒。.第第3章章 递推算法递推算法 如何建立递推关系？目前尚未总结出一个一般如何建立递推关系

10、？目前尚未总结出一个一般的方法，只能具体问题，具体分析。的方法，只能具体问题，具体分析。建立递推关系，必须对所提出的问题，进行深建立递推关系，必须对所提出的问题，进行深入细致的分析。入细致的分析。 先从最简单的情况分析入手，看先从最简单的情况分析入手，看n1，n2，时的情况如何，这就是先建立初条件。时的情况如何，这就是先建立初条件。 .第第3章章 递推算法递推算法而后，从而后，从nk - 1(有时用到有时用到nk - 2，nk - 3，)时，去推出时，去推出nk的情况，这种推测就的情况，这种推测就是建立在先验印象的基础上的。因此，便于是建立在先验印象的基础上的。因此，便于摸清变化规律，而得出正

11、确的递推关系摸清变化规律，而得出正确的递推关系. 斐波那契兔子问题.公元公元12021202年，商人出身的意大利数学家斐波那契（年，商人出身的意大利数学家斐波那契（FiFibonaccibonacci，1170117012501250），完成了一部伟大的论著），完成了一部伟大的论著算法之书算法之书。在书中，提出以下有趣问题：。在书中，提出以下有趣问题：假定一对刚出生的小兔一个月后就能长成大兔，再过假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对一个月便能生下一对小兔，并且此后每个月都生一对小兔。一年内没有发生死亡，问一对刚出生的兔子，小兔。一年内没有

12、发生死亡，问一对刚出生的兔子，一年内繁殖成多少对兔子？一年内繁殖成多少对兔子？(假定以上兔子都是雌雄成假定以上兔子都是雌雄成对对)？ 第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题.其中其中A表示一对大兔子，表示一对大兔子，B表示一对小兔子表示一对小兔子第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题.逐月推算，我们可以得到前面提过的数列：逐月推算，我们可以得到前面提过的数列：1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，8989，144144，233233。这个数。这个数列后来便以斐波那契的名字命名。数列的每一项，则称为

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

14、.算法描述：算法描述：按照斐波那契数列中各项的关系，可以使用四按照斐波那契数列中各项的关系，可以使用四个变量个变量a、b、c和和k来计算，这四个变量的用途来计算，这四个变量的用途如下：如下：a 存贮存贮Fk-2。 b 存贮存贮Fk-1。c 存贮存贮Fk ，可以通过，可以通过a+b，从，从Fk-2和和Fk-1来计算来计算Fk 。k 记录变量记录变量c中存贮的当前项的项号。中存贮的当前项的项号。第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题.第第3章章 递推算法递推算法-斐波那契兔子问题斐波那契兔子问题.下面是用自然语言描述的算法：下面是用自然语言描述的算法：1. (输入项号输入项

15、号)输入项号输入项号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”,&n ) ; If (n3) printf(“%d”,1 ) ; in

16、t f1=1;f2=1;i=3;while(i=n) fi=f1+f2 f1=f2; f2=fi; i+; printf(“%d”,fi ) 算法描述：1、定义初值2、变量i从3增到n3、计算fi=fi-1+ fi-2;4、输出fi.第第3章章 递推算法递推算法- 阶乘计算阶乘计算问题描述：对给定的n（n100），计算并输出k的阶乘k！（k=1，2，n）的全部有效数字。00)!1(1!nnnnn.用递推法求解阶乘函数的思路是：先求fac(1)，再求fac(2)，,直到求出fac(n)Main() Int n; Int facn=0 Int m=1; for(int i=1;i=n;i+) m=

17、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

18、次方，那么，第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的-