算法题__计算机算法设计与分析期末试题4套(含答案)[精品].pdf

（1）用计算机求解问题的步骤： 1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实 7、 程序调试8、结果整理文档编制 （2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理 过程 （3）算法的三要素 1、操作2、控制结构3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出 口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有 限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产 生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要 的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 也称 “辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方 法。 利用迭代算法解决问题，需要做好以下三个方面的工作： 一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或 间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下 一个值的公式 （或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以 使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必 须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可 分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是 所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实 现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的 条件。 Fibonacci n fib n 编写计算斐波那契（ ）数列的第 项函数 （）。 斐波那契数列为：0、1、1、2、3、……，即： fib(0)=0; fib(1)=1; 1 fib(n)=fib(n-1)+fib(n-2) （当n1时）。 写成递归函数有： int fib(int n) { if (n==0)return 0; if (n==1)return 1; if (n1)return fib(n-1)+fib(n-2); } 一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始， 每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到 第 12 个月时，该饲养场共有兔子多少只？ 分析：这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ，第 2 个月时兔子的只数为 u 2 ，第 3 个月时兔子的只数为 u 3 ，…… 根据题意， “这种兔子从出生的下一个月开始，每月新生一只兔子”，则有 u 1 ＝ 1 ， u 2 ＝ u 1 ＋ u 1 ×1 ＝ 2 ， u 3 ＝ u 2 ＋ u 2 ×1 ＝ 4 ，…… 根据这个规律，可以归纳出下面的递 cls 推公式： x=1 u n ＝ u n － 1 × 2 (n ≥ 2) for i=2 to 12 对应 u n 和 u n － 1 ，定义两 y=x*2 个迭代变量 y 和 x ，可将上面的递