递归方程的求解

算法设计与分析知到章节测试答案智慧树2023年最新天津大学第一章测试1.下列关于效率的说法正确的是（）。

参考答案:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法;效率主要指处理机时间和存储器容量两个方面;效率是一个性能要求，其目标应该在需求分析时给出2.算法的时间复杂度取决于（）。

参考答案:问题的规模;待处理数据的初态3.计算机算法指的是（）。

参考答案:解决问题的有限运算序列4.归并排序法的时间复杂度和空间复杂度分别是（）。

参考答案:O(nlog2n);O(n)5.将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。

（）参考答案:错6.用渐进表示法分析算法复杂度的增长趋势。

（）参考答案:对7.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。

（）参考答案:对8.某算法所需时间由以下方程表示，求出该算法时间复杂度（）。

参考答案:O(nlog2n)9.下列代码的时间复杂度是（）。

参考答案:O(log2N)10.下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（）。

参考答案:3n/2-3/2第二章测试1.可用Master方法求解的递归方程的形式为（）。

参考答案:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.2.参考答案:对3.假定，, 递归方程的解是. ( )参考答案:对4.假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。

针对该问题的任何算法需要的时间复杂度的下限必为。

( )参考答案:错5.使用Master方法求解递归方程的解为（）.参考答案:6.考虑包含n个二维坐标点的集合S，其中n为偶数，且所有坐标点中的均不相同。

一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。

若给定集合S，则可在时间内找到这条分界线L。

数列求通项的十种方法
数列是数学中的一个重要概念，对于求数列通项的问题，有许多不
同的解法。

下面将介绍十种求解数列通项的方法。

1. 暴力求解法：将数列中的前几项写出来，然后根据已知项之间的规
律来推出通项公式。

2. 公式推导法：利用一些已知的数列通项公式，结合这个数列的特点，在此基础上推导出此数列的通项公式。

3. 通项公式分解法：将数列的通项公式分解为元素之和的形式，从而
得到每一项的通项公式。

4. 递推公式求解法：根据数列中一些指定的通项公式，推导出递推公式，并使用递推公式依次求出数列中每一项的通项公式。

5. 差分法：通过对数列求差（即相邻项之差），得到一个新数列，然
后对新数列再次求差，直到差分后的数列为常数列，最后通过累加得
到原数列的通项公式。

6. 微积分法：对数列进行微积分操作，得到导数，然后再对导数积分，通过积分得到原数列的通项公式。

7. 特征方程法：将递推公式转化为特征方程，并求解特征根，然后根
据特征根求得通项公式。

8. 奇怪公式法：有些数列的通项公式看起来十分奇怪，但通过反复验证，发现确实有效。

9. 递归法：通过一个递归的函数，根据某一项的值递归计算其他项的值，最终得到整个数列的通项公式。

10. 牛顿插值法：利用牛顿插值法，通过已知的数列中一部分数值，反
推出整个数列的通项公式。

以上是十种求解数列通项的方法，每种方法都有其适用范围和局限性。

对于不同的数列，选择不同的方法求解，可以得到更加准确和简便的
结果。

递归算法得优缺点：3优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法得正确性，因此它为设计算法、调试程序带来很大方便。

3缺点：递归算法得运行效率较低，无论就是耗费得计算时间还就是占用得存储空间都比非递归算法要多。

边界条件与递归方程就是递归函数得二个要素应用分治法得两个前提就是问题得可分性与解得可归并性以比较为基础得排序算法得最坏倩况时间复杂性下界为0(n I o g2n)。

回溯法以深度优先得方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先得方式搜索解空间树T。

舍伍德算法设计得基本思想：设A就是一个确定性算法，当它得输入实例为x时所需得计算时间记为tA(x)。

设Xn就是算法A得输入规模为n得实例得全体，则当问题得输入规模为n时，算法A所需得平均时间为这显然不能排除存在x€Xn使得得可能性。

希望获得一个随机化算法B，使得对问题得输入规模为n得每一个实例均有拉斯维加斯(Las Vegas )算法得基本思想：设p(x)就是对输入x调用拉斯维加斯算法获得问题得一个解得概率。

一个正确得拉斯维加斯算法应该对所有输入x均有p(x)>0。

设t(x)就是算法obst in ate找到具体实例x得一个解所需得平均时间，s(x)与e(x)分别就是算法对于具体实例x求解成功或求解失败所需得平均时间，则有：解此方程可得：蒙特卡罗(Monte Carlo)算法得基本思想：设p就是一个实数，且1/2<p<1。

如果一个蒙特卡罗算法对于问题得任一实例得到正确解得概率不小于p,则称该蒙特卡罗算法就是p正确得，且称p1/2就是该算法得优势。

如果对于同一实例，蒙特卡罗算法不会给出2个不同得正确解答，则称该蒙特卡罗算法就是一致得。

线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。

单纯形算法得特点就是：(1) 只对约束条件得若干组合进行测试，测试得每一步都使目标函数得值增加；(2) 一般经过不大于m或n次迭代就可求得最优解。

《算法设计与分析》习题第一章引论习题1-1 写一个通用方法用于判定给定数组是否已排好序。

解答：Algorithm compare(a,n)BeginJ=1;While (j<n and a[j]<=a[j+1]) do j=j+1;If j=n then return trueElseWhile (j<n and a[j]>=a[j+1]) do j=j+1;If j=n then return true else return false end ifEnd ifend习题1-2 写一个算法交换两个变量的值不使用第三个变量。

解答：x=x+y; y=x-y; x=x-y;习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。

解答：m:=k; flag:=0;repeatn:=m;repeatl:=n*n-m*n-m*n;if (l*l=1) then flag:=1 else n:=n-1;until (flag=1) or (n=0)if n=0 then m:=m-1until (flag=1) or (m=0);第二章基础知识习题2-1 求下列函数的渐进表达式：3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。

解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。

习题2-2 说明O (1)和 O (2)的区别。

习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ，3/22,2,20,3,log ,4n n n n n 。

解答：照渐进阶从低到高的顺序为：!n 、 3n、 24n 、23n 、20n 、log n 、2习题2-4（1） 假设某算法在输入规模为n 时的计算时间为n n T 23)(⨯=。

§6.4一种特殊的联立方程模型—递归系统模型在介绍联立方程计量经济学模型的估计方法之前，首先介绍一种在形式是属于联立方程模型但仍然可以采用单方程模型的估计方法估计每个方程的特殊情况，即递归系统模型。

一、递归系统模型联立方程模型BΓNY X+=如果B=------⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥1000100101 213132123ββββββg g gΓ=---------⎡⎣⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥γγγγγγγγγ111212122212kkg g gk即在第1个方程中被解释变量为Y1，解释变量全部为先决变量；在第2个方程中被解释变量为Y2，解释变量中除了作为第1个方程被解释变量的内生变量Y1外，全部为先决变量；第3个方程…，依次类推。

这类模型称为递归系统模型。

递推系统模型在实际经济系统中是确实存在的。

递归系统的倡导者Wold Jureen于1953年指出，经济理论通常定义经济关系中最重要的解释变量，在这种情况下，经济关系式可以用递归系统模型充分地表达。

例如，在供给导向的宏观经济系统中，总产值由前期资本存量和劳动力数量决定，它们是先决变量；国民收入由总产值决定；居民收入、财政收入由国民收入决定；消费与投资又由居民收入、财政收入决定；…如果将这些关系用一个宏观经济模型来描述，这个模型就是典型的递归系统模型。

大多数情况下，模型并不是严格递归的，而是一种近似递归系统。

但可以采用递归系统模型的方法去研究。

二、递归系统模型的估计由于递归系统模型中的第1个方程的解释变量全部为先决变量，那么可以用单方程模型的估计方法直接估计第1个方程的参数，并得到关于被解释变量的估计值 ( , , )Y y y yn111121= 。

在第2个方程的解释变量中，除了在第1个方程中作为被解释变量的Y1之外，全部为先决变量。

于是有两种可以用于该方程参数估计的方法，一是以 Y1取代方程中的Y1作为解释变量，然后用普通最小二乘法等方法估计其参数；二是以 Y1作为方程中Y1的工具变量，采用工具变量方法估计方程参数。

参考答案第1章一、选择题1. C2. A3. C4. C A D B5. B6. B7. D 8. B 9. B 10. B 11. D 12. B二、填空题1. 输入；输出；确定性；可行性；有穷性2. 程序；有穷性3. 算法复杂度4. 时间复杂度；空间复杂度5. 正确性；简明性；高效性；最优性6. 精确算法；启发式算法7. 复杂性尽可能低的算法；其中复杂性最低者8. 最好性态；最坏性态；平均性态9. 基本运算10. 原地工作三、简答题1. 高级程序设计语言的主要好处是：（l）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可移植性好、重用率高；（4）把复杂琐碎的事务交给编译程序，所以自动化程度高，发用周期短，程序员可以集中集中时间和精力从事更重要的创造性劳动，提高程序质量。

2. 使用抽象数据类型带给算法设计的好处主要有：（1）算法顶层设计与底层实现分离，使得在进行顶层设计时不考虑它所用到的数据，运算表示和实现；反过来，在表示数据和实现底层运算时，只要定义清楚抽象数据类型而不必考虑在什么场合引用它。

这样做使算法设计的复杂性降低了，条理性增强了，既有助于迅速开发出程序原型，又使开发过程少出差错，程序可靠性高。

（2）算法设计与数据结构设计隔开，允许数据结构自由选择，从中比较，优化算法效率。

（3）数据模型和该模型上的运算统一在抽象数据类型中，反映它们之间内在的互相依赖和互相制约的关系，便于空间和时间耗费的折衷，灵活地满足用户要求。

（4）由于顶层设计和底层实现局部化，在设计中出现的差错也是局部的，因而容易查找也容易纠正，在设计中常常要做的增、删、改也都是局部的，因而也都容易进行。