算法分析与设计大作业
实验题目：0-1背包问题求解方法综述组员：
班级：
指导老师：
0-1背包问题求解方法综述
【摘要】：0-1背包问题是一个经典的NP-hard组合优化问题，现实
生活中的很多问题都可以以它为模型。本文首先对背包问题做了阐
述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问
题进行求解，分析了0-1背包问题的数学模型,刻划了最优解的结构
特征,建立了求最优值的递归关系式。最后对四种算法从不同角度进
行了对比和总结。
【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。
0.引言
0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量
wi(i=1,2,…,n),再给定一个背包,其容量为W。要求从n个物品中选出一部分物
品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。单个物
品要么装入,要么不装入。很多问题都可以抽象成该问题模型,如配载问题、物资
调运[1]问题等,因此研究该问题具有较高的实际应用价值。目前,解决0-1背包
问题的方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子
群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。
其中动态规划、回溯法、分支限界法时间复杂性比较高,计算智能算法可能出现
局部收敛,不一定能找出问题的最优解。文中在动态规划法的基础上进行了改进,
提出一种求解0-1背包问题的算法,该算法每一次执行总能得到问题的最优解,
是确定性算法,算法的时间复杂性最坏可能为O(2n)。
1.0-1背包问题描述
0-1背包问题(KP01)是一个著名的组合优化问题。它应用在许多实际领域,
如项目选择、资源分布、投资决策等。背包问题得名于如何选择最合适的物品放
置于给定背包中。本文主要研究背包问题中最基础的0/1背包问题的一些解决方
法。
为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。解决背
包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、
分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子
算法等一些智能算法。
0-1背包问题一般描述为：给定n 种物品和一个背包。物品i 的重量是w(i)，其价值为v(i)，背包的容量为c 。问应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
在选择装入背包的物品时，对每种物品i 只有两种选择，即装入背包或不装入背包。不能将物品i 装入背包多次，也不能只装入部分的物品i 。因此，该问题称为0-1背包问题。
此问题的形式化描述是，给定n i v w c i i ≤≤>>>1000，，，，要求找出一个n
元0-1向量n i x x x x i n ≤≤∈1}1,0{21，），，，，（ ，使得c
x w i i i ≤∑=n
1
，而且i
n
i i x v ∑=1
达到最大。
数学模型：∑=n
i i i x v 1max
约束条件：
c x w i i i ≤∑=n
1
， n i x i
≤≤∈1},1,0{
2.0-1背包问题的求解算法
2.1蛮力算法（brute force method ） 2.1.1基本思想：
对于有n 种可选物品的0/1背包问题，其解空间由长度为n 的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。 2.1.2代码实现: #include
#define N 100 //最多可能物体数 struct goods //物品结构体 {
int sign; //物品序号 int w; //物品重量 int p; //物品价值 }a[N];
bool m(goods a,goods b)
return (a.p/a.w)>(b.p/b.w);
}
int max(int a,int b)
{
return a } int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N]; /*蛮力法求解0/1背包问题*/ int Force(int i) { if(i>n-1){ if(bestP for (int k=0;k } return bestP; } cw=cw+a[i].w; cp=cp+a[i].p; cx[i]=1; //装入背包 Force(i+1); cw=cw-a[i].w; cp=cp-a[i].p; cx[i]=0; //不装入背包 Force(i+1); return bestP; } int KnapSack1(int n,goodsa[],int C,int x[]) { Force(0); return bestP; } int main() goods b[N]; printf("物品种数n: "); scanf("%d",&n); //输入物品种数 printf("背包容量C: "); scanf("%d",&C); //输入背包容量 for (int i=0;i { printf("物品%d的重量w[%d]及其价值v[%d]: ",i+1,i+1,i+1); scanf("%d%d",&a[i].w,&a[i].p); b[i]=a[i]; } int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题 printf("蛮力法求解0/1背包问题:\nX=[ "); for(i=0;i cout< printf("] 装入总价值%d\n",sum1); bestP=0,cp=0,cw=0;//恢复初始化 } 2.1.3复杂度分析： 蛮力法求解0/1背包问题的时间复杂度为：2^n 2.2贪心算法（Greedy algorithm） 贪心算法通过一系列的选择来得到问题的解。贪心选择即它总是做出当前最好的选择[4]。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优选择，这是贪心算法与动态规划算法的主要区别。 贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件。在枚举剩下数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个数据，加入结果数据中，直到剩下的数据不能再加入为止[6]。贪心算法不能保证得到的最后解是最佳的，也不能用来求最大或最小解问题，只能求满足某些约束条件的可行解范围。 2.2.1算法设计 用贪心算法解决0-1背包问题一般有以下三种策略： 价值最大者优先：在剩余物品中，选出可以装入背包的价值最大的物品，若背包有足够的容量，以此策略，然后是下一个价值最大的物品。但这种策略背包的承重量不能够得到有效利用，即得不到最优解。例如： n=3,w=[50,20,20],v=[10,7,7]c=55,得到的解是x=[1,0,0],这种方案的总价值为10，而最优解为[0,1,1],总价值为14。 ②重量最小者优先：在剩余物品中，选择可以装入背包的重量最小的物品。但这种策略，不能保证重量小的是最有价值的，也不能得到最优解。例如：n=2,w=[10,20],v=[5,100],c=25，得到的解为x=[1,0],而最优解是[0,1]。 ③单位价值最大者优先：根据价值与重量的比值i v /i w ，即单位价值，在剩下的物品中依次选取比值最大的物品装入背包。这种策略也不能得到最优解。例如：n=3,w=[20,15,15],v=[40,25,25],i v /i w =[2,5/3,5/3],c=30,得到的解x=[1,0,0],而最优解是[0,1,1]。但它是直觉上的一个近似解。本文讨论该策略。 策略3的具体步骤为： 第一步：计算每个物品的价值比i r =i v /i w ，i=1,2,…,n 。 第二步：对物品的价值比非递增排序。 第三步：重复下面操作，直到有序列表中留下物品。如果列表中的当前物品能够装入背包，就将它放入背包中，否则，处理下一个物品。 2.2.2 编程实现 #include"stdafx.h" #include #define max 100 //自定义物品最大数 void package(int v[],int w[],int n,int c) //定义包函数 { doublea[max]; inti,totalv=0,totalw=0,index[max]; for(i=0;i a[i]=(double)v[i]/w[i]; //单位价值计算 index[i]=i; } for(i=1;i for(int j=0;j if(a[j] double b=a[j]; a[j]=a[j+1]; a[j+1]=b; int c=v[j]; v[j]=v[j+1]; v[j+1]=c; int d=w[j]; w[j]=w[j+1]; w[j+1]=d; int e=index[j]; index[j]=index[j+1]; index[j+1]=e; } } } cout<<"单位价值："; //输出单位价值 for(i=0;i { cout< } cout< for(i=0;i { cout< } cout< for(i=0;i { cout< } cout< doublex[max]={0}; i=0; while(w[i]<=c) { x[i]=1; c=c-w[i]; i++; } cout<<"所选择的商品如下:"< cout<<"序号i:\t重量w:\t价格v:\t"< { if(x[i]==1){ totalw=totalw+w[i]; totalv=totalv+v[i]; cout< } } cout<<"背包的总重量为："< cout<<"背包的总价值为："< } int main(void) //主函数定义 { LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0)); int n,i,x[max]; int v[max],w[max],W; //变量的定义 cout<<"请输入物品种数n和背包容量W:"; cin>>n>>W; for(i=0;i x[i]=0; //物品选择情况表初始化为0 for(i=0;i { v[i]=rand()%1000; w[i]=rand()%1000;} cout<<"商品的重量和价值如下："< for(int i=0;i { cout< cout< } QueryPerformanceCounter(&begin); package(v,w,n,W); //函数的调用 QueryPerformanceCounter(&end); cout<<"时间:" <<(double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart <<"s"< } 2.2.2运行结果 贪心算法求解0/1背包问题的时间复杂度为：(nlogn) 2.3 动态规划算法（Dynamic Programming） 20世纪50年代，美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用个阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划[3]。动态规划是基于递归的，通常不是一个解决KP有效的方式,因为空间消耗非常大,和最坏的和最好的计算工作通常是相同的[7]。动态规划算法与分治法类似，其基本思想也是将带求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法解决这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保证已解决的子问题的答案，而在需要时找出已求出的答案，这样就可以避免大量的重复计算，从而达到多项式时间算法。为了达到此目的可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思想。具体的动态规划算法多种多样，但它们有相同的填表格式。 动态规划算法适用于解最优化问题。通常可按以下4个步骤设计： （1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造最优解。 步骤（1）~（3）是动态规划算法的基本步奏。在需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的最优解，则必须执行步骤（4）.此时，在步骤（3）中计算最优解时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。 使用动态规划求解问题，最重要的就是确定动态规划3要素：（1）问题的阶段；（2）每个阶段的状态；（3）从前一个阶段转化后一个阶段之间的递推关系[4]。 2.3.1分析最优解的性质，刻画最优解的结构特征——最优子结构性质分析 设），，，（n x x x 21所给0-1背包问题的一个最优解，则），，（n x x x 32是下面相应子问题的一个最优解： 目标函数：i n i i x v ∑=2 max 约束条件： )2}(1,0{,112 n i x x w c x w i n i i i ≤≤∈-≤∑= 证明：若），，（n x x x 32不是上述子问题的一个最优解，而），，，（n 32y y y 是他的最优解。由此可知，i i i n i i x v y v ∑∑>=n 2 且c y w x w i n i i ≤+∑=2 11。因此 c y w x w x v y v x v i n i i i n i i n i i ≤+>+∑∑∑===2 111 1211 这说明），，，（n y y x 21是原问题的一个更优解，从而），，，（n y y y 21不是所给原问题的最优解，产生矛盾。 所以），，（n x x x 32是上述子问题的一个最优解。 2.3.2递归关系 由于0-1背包问题的解是用向量），，，（n x x x 21来描述的。因此，该问题可以看做是决策一个n 元0-1向量），，，（n x x x 21。对于任意一个分量i x 的决策是“决定i x =1或i x =0，i=1,2,…,n 。对1-i x 决策后，序列)(121-i x x x ，，， 已被确定，在决策i x 时，问题处于下列两个状态之一： （1）背包容量不足以装下物品i ，则=0，装入背包的价值不增加； （2）背包容量足以装入物品i,则=1，装入背包的价值增加i v 。 在这种情况下，装入背包的价值最大化应该是对决策后的价值。 设所给0-1背包问题的子问题 n k i x j x w x v k k n i k k n i k k k ≤≤∈≤∑∑==，，)1,0(max 的最优值为m(i,j),即m(i,j)是背包容量为j ，可选择的物品为i,i+1,…,n 时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m （i,j ）的递归式为： n n n i i i i w j v w j w j v w j i m j i m w j j i m j n m j i m ≥<≤≥+-++<≤+==，，00)}(),1(),,1(max{)0)(,1({ ),({ ),( 2.3.3算法设计 基于上面的讨论，求解0-1背包的动态规划算法步骤如下： 步骤1：当)1(n i w i ≤≤为正整数时，用数组w[n]来存放n 个物品的重量；数组v[n]来存放n 个物品的价值，背包容量为c ，数组M[n+1][c+1]来存放每一次迭代的执行结果；数组x[n]用来存储所装入背包的物品状态； 步骤2：初始化。数组M 的第0行第0列全部设置为0； 步骤3：循环阶段。按式（5）确定前i 个物品能够装入背包的情况下得到的最优值； 步骤3-1：i=1时，求出M[1][j],1≤j ≤c ； 步骤3-2：i=2时，求出M[2][j],1≤j ≤c ； …… 步骤3-n:i=n 时，求出M[n][c]。此时，M[n][c]便是最优值； 步骤4：确定装入背包的具体物品。从M[n][c]的值向前推，如果M[n][c]>M[n-1][c]，表明第n 个物品被装入背包，则n x =1，前n-1个物品没有被装入背包，则n x =0，前n-1个物品被装入容量为c 的背包中。以此类推，知道确定第1个物品是否被装入背包为止。由此，得到下面的关系式： 如果M[i][j]=M[i-1][j],说明第i 个物品没有被装入背包，则i x =0； 如果M[i][j]>M[i-1][j],说明第i 个物品被装入背包，则i x =1，j=j-i w 。 按照上述关系式，从M[n][c]的值向前倒推，即j 初始为c ，i 初始为n,即可确定装入背包的具体物品。 上述算法需要O （nc ）时间计算时间。不过上述算法有2个明显的确点。一是算法要求所给物品的重量i w （1≤i ≤n ）是整数；二是当背包容量c 很大时，算法需要的计算时间较多。 2.2.2运行结果 贪心算法求解0/1背包问题的时间复杂度为：O （nm ） 2.4 回溯法（Backtracking ） 2.4.1回溯法0-1背包问题的实现 回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。 左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r 为还未遍历的对象的收益之和，将r 加到cp(当前节点所获收益)之上，若( r+cp) <=bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi 对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量。 2.4.2 编程实现如下 #include"stdafx.h" #include #include #include #include using namespace std; #defineN 100 //最多可能物体数 structgoods //物品结构体 { int sign; //物品序号 int w; //物品重量 int p; //物品价值 }a[N],b[N]; bool m(goods a,goods b) { return (a.p/a.w)>(b.p/b.w); } int max1(int a,intb) //最大函数定义 { return a } int n,W,bestP=0,cp=0,cw=0; int X[N],cx[N]; //变量定义 int BackTrack(int i) { if(i>n-1){ if(bestP for (int k=0;k bestP=cp; } returnbestP; } if(cw+a[i].w<=W){ //进入左子树 cw=cw+a[i].w; cp=cp+a[i].p; cx[a[i].sign]=1; //装入背包 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].p; //回溯，进入右子树} cx[a[i].sign]=0; //不装入背包 BackTrack(i+1); return bestP; } void KnapSack3(intn,goods a[],int C,intx[]) { int totalW=0; for(inti=0;i { x[i]=0; a[i].sign=i; } sort(a,a+n,m); //将各物品按单位重量价值降序排列BackTrack(0); cout<<"所选择的商品如下:"< cout<<"序号i:\t重量w:\t价格v:\t"< for(int i=0;i { if(X[i]==1){ cout< cout< cout< } } cout<<"放入背包的物品总重量为："< cout< cout<<"放入背包的物品总价值为："< } int main() //主函数的定义 { LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0)); cout<<"请输入物品种数n和背包容量W:"; cin>>n>>W; for (inti=0;i a[i].w=rand()%1000; a[i].p=rand()%1000; b[i]=a[i]; } cout<<"物品的重量和价值分别如下："< for (inti=0;i cout< cout<<"\t"; cout< } QueryPerformanceCounter(&begin); KnapSack3(n,a,W,X); //调用回溯法求0/1背包问题 QueryPerformanceCounter(&end); cout<<"时间:" <<(double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart <<"s"< } 2.4. 3 运行结果 回溯法法的时间复杂度为 2.5分枝-限界法（Branch - threshold method） 2.5.1 分枝-限界法的基本原理与分析 分枝限界法是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点 的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成 从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出最优解的 结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中 取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。 2.5.2 分枝限界0-1背包问题的实现 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最 大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 2.5.3 编程实现如下 #include #include using namespace std; #define N 100 //最多可能物体数 struct goods //物品结构体 { int sign; //物品序号 int w; //物品重量 int p; //物品价值 }a[N]; bool m(goods a,goods b) { return (a.p/a.w)>(b.p/b.w); } int max(int a,int b) { return a } int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N]; struct KNAPNODE //状态结构体 { bool s1[N]; //当前放入物体 int k; //搜索深度 int b; //价值上界 int w; //物体重量 int p; //物体价值 }; struct HEAP //堆元素结构体 { KNAPNODE *p; //结点数据 int b; //所指结点的上界}; void swap(HEAP &a, HEAP&b) //交换两个堆元素{ HEAP temp = a; a = b; b = temp; } //堆中元素上移 void mov_up(HEAP H[], int i) { bool done = false; if(i!=1){ while(!done && i!=1){ if(H[i].b>H[i/2].b){ swap(H[i], H[i/2]); }else{ done = true; } i = i/2; } } } //堆中元素下移 void mov_down(HEAP H[], intn, int i) { bool done = false; if((2*i)<=n){ while(!done && ((i = 2*i) <= n)){ if(i+1<=n && H[i+1].b > H[i].b){ i++; } if(H[i/2].b swap(H[i/2], H[i]); }else{ done = true; } } } } //往堆中插入结点 void insert(HEAP H[], HEAPx, int &n) { n++; H[n] = x; mov_up(H,n); } //删除堆中结点 void del(HEAP H[], int&n, int i) { HEAP x, y; x = H[i]; y = H[n]; n --; if(i<=n){ H[i] = y; if(y.b>=x.b){ mov_up(H,i); }else{ mov_down(H, n, i); } } } //获得堆顶元素并删除 HEAP del_top(HEAP H[], int&n) { HEAP x = H[1]; del(H, n, 1); return x; } //计算分支节点的上界 void bound( KNAPNODE* node,int M, goods a[], int n) { int i = node->k; float w = node->w; float p = node->p; if(node->w>M){ // 物体重量超过背包载重量node->b = 0; // 上界置为0 }else{ while((w+a[i].w<=M)&&(i w += a[i].w; // 计算背包已装入载重 p += a[i++].p; // 计算背包已装入价值} if(i node->b = p + (M - w)*a[i].p/a[i].w; }else{ node -> b = p; } } } //用分支限界法实现0/1背包问题 int KnapSack4(int n,goodsa[],int C, int X[]) { int i, k = 0; // 堆中元素个数的计数器初始化为0 int v; KNAPNODE *xnode, *ynode, *znode; HEAP x, y, z, *heap; heap = new HEAP[n*n]; // 分配堆的存储空间 for( i=0; i a[i].sign=i; //记录物体的初始编号 } sort(a,a+n,m); // 对物体按照价值重量比排序 xnode = new KNAPNODE; // 建立父亲结点 for( i=0; i xnode->s1[i] = false; } xnode->k = xnode->w = xnode->p = 0; while(xnode->k ynode = new KNAPNODE; // 建立结点y *ynode = *xnode; //结点x的数据复制到结点y ynode->s1[ynode->k] = true; // 装入第k个物体 ynode->w += a[ynode->k].w; // 背包中物体重量累计 ynode->p += a[ynode->k].p; // 背包中物体价值累计 ynode->k ++; // 搜索深度++ bound(ynode, C, a, n); // 计算结点y的上界 y.b = ynode->b; y.p = ynode; insert(heap, y, k); //结点y按上界的值插入堆中znode = new KNAPNODE; // 建立结点z *znode = *xnode; //结点x的数据复制到结点z znode->k++; // 搜索深度++ bound(znode, C, a, n); //计算节点z的上界 z.b = znode->b; z.p = znode; insert(heap, z, k); //结点z按上界的值插入堆中 delete xnode; x = del_top(heap, k); //获得堆顶元素作为新的父亲结点 xnode = x.p; } v = xnode->p; for( i=0; i X[a[i].sign] =1 ; }else{ X[a[i].sign] = 0; } } delete xnode; delete heap; return v; //返回背包中物体的价值 利用递归思想解决计数问题 福建省永定第一中学 简绍煌 我们常会遇到一些看似排列组合应用题的计数问题，但其复杂的情形有时令人无从下手，若是利用递归思想建立递归方程加以求解，则往往能够迎刃而解． 【例1】有一楼梯共10级，如果规定每步只能跨上一级或二级，要上10级，共有多少种走法？ 解 设上n 级楼梯共有n a 种走法，当1n =时，11a =；当2n =时，22a =． 当有(2)n n >级楼梯时，其走法分两类． 第一类：走完前面1n -级楼梯有1n a -种走法，走第n 级只有1种走法； 第二类：走完前面2n -级楼梯有2n a -种走法，走第1n -级与第n 级楼梯时一步走，也是1种走法． 由分类计数原理，知n 级楼梯的走法为21(2)n n n a a a n N n --=+∈>且，． 由此可以算出1089a =． 点评 其通项公式可用换元法转化为一阶线性递归数列求解． 令11n n n c a x a +=-，使数列{}n c 是以2x 为公比的等比数列(12x x 、待定)． 即211211()n n n n a x a x a x a +++-=-，∴212112()n n n a x x a x x a ++=+-．对照已给递归式， 有12121 1x x x x +==-，，即12x x 、是方程210x x --=的两个根． 从而121211112222x x x x += === ∴211111(222n n n n a a a a +++-=-) ① 或211111(222n n n n a a a +++-=-) ② 由式①得1 1131(222n n n a a -++-=； 由式②得1 1131(222 n n n a a -++--=． 消去 1n a +，得11n n n a --? =?? ． 【例2】将数字123n ，，，，填入标号为123n ，，，，的n 个方格内，每格一个数字，则 标号与所填数字均不同的填法共有多少种？ 解 设这n 个自然数的错排数为n a ． 当1n =时，10a =；当2n =时，21a =． 当3n ≥时，n 个自然数的错排数可以分两类情况计算． 第一类：自然数(11)k k n ≤≤-与n 互换，这时错排数为2n a -； 第二类：自然数n 在第k 位上，但自然数不在第n 位上．这时就把第n 位看做第k 位，相当于将n 以外的1n -个自然数进行错排，错排数为1n a -． 所以，自然数n 在第k 位上的错排数共有21n n a a --+种，由于k 可以是121n - ，，，共 1n -种可能，故n 个自然数的错排数为21(1)()(3)n n n a n a a n --=-+≥．① 由①式得，112[(1)]n n n n a a a n a ----=---，∴112 (1)[]!!!! n n n n a na a n a n n n n -----=--， 递归方程解的渐近阶的求法 递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。 递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法。 1.代入法这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这 一推测的正确性。那么，显式解的渐近阶即为所求。 2.迭代法这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数， 然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。 3.套用公式法这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况 下方程解的渐近阶的三个相应估计公式供套用。 4.差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问 题)的方法来解递归方程。然后对得到的解作渐近阶的估计。 5.母函数法这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次 和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。 本章将逐一地介绍上述五种方法，并分别举例加以说明。 本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。 递归方程组解的渐进阶的求法——代入法 用这个办法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答作出推测，然后用数学归纳法证明推测的正确性。 例如，我们要估计T(n)的上界，T(n)满足递归方程： 其中是地板(floors)函数的记号，表示不大于n的最大整数。 我们推测T(n)=O(n log n)，即推测存在正的常数C和自然数n0，使得当n≥n0 时有： 特征方程特征根法求解数列通项公式 一：A(n+1)=pAn+q, p,q为常数. （1）通常设：A(n+1)-λ＝p(An-λ), 则λ=q／(1-p). （2）此处如果用特征根法： 特征方程为：x=px+q，其根为x=q/（1-p） 注意：若用特征根法，λ的系数要是-1 例一：A（n+1)=2An+1 , 其中q=2,p=1,则 λ=1/（1-2）= -1那么 A（n+1）+1=2（An+1） 二：再来个有点意思的,三项之间的关系： A(n+2)=pA(n+1)+qAn，p,q为常数 （1）通常设：A(n+2)-mA(n+1)=k[pA(n+1)-mAn], 则m+k=p, mk=q （2）此处如果用特征根法： 特征方程是y×y=py+q（※） 注意： ①m n为（※）两根。 ②m n可以交换位置，但其结果或出现两种截然不同的数列形式，但同样都可以计算An，而且还会有意想不到的惊喜， ③m n交换位置后可以分别构造出两组An和A(n+1)的递推公式，这个时侯你会发现，这是一个关于An和A(n+1)的二元一次方程组，那么不就可以消去A（n+1），留下An，得了，An求出来了。 例二：A1=1,A2=1,A(n+2)= - 5A（n+1）+6An， 特征方程为：y×y= - 5y+6 那么，m=3,n=2,或者m=2，n=3 于是，A（n+2）-3A（n+1）=2[A（n+1）-3A] (1) A（n+2）-2A（n+1）=3[A（n+1）-2A] (2) 所以，A（n+1）-3A（n）= - 2 ^ n (3) A（n+1）-2A（n）= - 3 ^ (n-1) (4) you see 消元消去A（n+1），就是An勒 例三： 【斐波那挈数列通项公式的推导】斐波那契数列：0，1，1，2，3，5，8，13，21…… 如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式： F(0) = 0，F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3) 显然这是一个线性递推数列。 通项公式的推导方法一：利用特征方程 线性递推数列的特征方程为： X^2=X+1 解得 X1=(1+√5)/2, X2=(1-√5)/2. 则F(n)=C1*X1^n + C2*X2^n ∵F(1)=F(2)=1 ∴C1*X1 + C2*X2 C1*X1^2 + C2*X2^2 递归方程求解方法综述 摘要：随着计算机科学的逐步发展，各种各样的算法相继出现，我们需要对算法进行分析，以选择性能更好的解决方案。算法分析中计算复杂度常用递归方程来表达，因此递归方程的求解有助于分析算法设计的好坏。阐述了常用的3种求解递归方程的方法：递推法、特征方程法和生成函数法。这3种方法基本上可以解决一般规模递归方程的求解问题。 关键词：递归；递推法；特征方程；生成函数 0引言 寻求好的解决方案是算法分析的主要目的，问题的解决方案可能不只一个，好的方案应该执行时间最短，同时占有存储空间最小，故算法分析一般考虑时间复杂性、空间复杂性两方面的参数。在算法分析时我们采用时间耗费函数来表示时间参数，用当问题规模充分大时的时间耗费函数的极限表示时间复杂度。 一般算法对应的时间耗费函数常用递归方程表示，找出递归方程的解，就可以表示其对应算法复杂度的渐进阶，从而比较算法的优劣。因此研究递归方程的解法意义重大。下文将分析并给出常用递归方程的3种解法。 1递归方程的解法 递归方程是对实际问题求解的一种数学抽象,递归的本质在于将原始问题逐步划分成具有相同解题规律的子问题来解决,原始问题与子问题仅在规模上有大小区别,并且子问题的规模比原始问题的 规模要小。对于规模为n的原始问题,我们通常会寻找规模n的问题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推导出具有递归特性的运算模型。 根据递归方程的一般形式，常用的解法有三种，分别是递推法、公式法及生成函数法。下面就分别来分析其求解过程。 1.1递推法 当递归方程形式简单且阶数较低时，一般可以采用递推法求解，根据一步一步递推找到方程的递推规律，得到方程的解。下面举例说明： t(1)=0 t(n)=2t(n/2)+n2(n≥2) t(n)=2t(n/2)+n2=2(2t(n/22)+(n/2)2)+n2 =22t(n/2)2+2n2/22+n2 =22(2t(n/23)+(n/22)2)+2n2/22+n2 =23(2t(n/23)+22n2/(22)2)+2n2/(22)1+n2… =2kt(n/2k)+∑k-1i=02in2(22)i递推到这里我们就可以发现递 归规律，找到递归出口， t(1)=0，令n=2k 则可以得到如下结果：t(n) =2kt(1) +∑k-1i=0n2(1/2)i)= n2(1-(1/2)k1-1/2)=2n2-2n 上面得到方程的解，我们来分析其对应算法复杂性的渐进阶，根据渐进阶定理有：设有函数f(n)，g(n）均是规模n的函数，则o(f(n))+o(g(n))=o(max(f(n), g(n)))。故有t(n)=o(n2)。 1.2公式法 特征方程法求解递推关系中的数列通项 考虑一个简单的线性递推问题. 设已知数列}{n a 的项满足 其中,1,0≠≠c c 求这个数列的通项公式. 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出一个方程,d cx x +=称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1.设上述递推关系式的特征方程的根为0x ，则当10a x =时，n a 为常数列，即0101,;x b a a x a a n n n +===时当， 其中}{n b 是以c 为公比的等比数列，即01111,x a b c b b n n -==-. 证明：因为,1,0≠c 由特征方程得.10c d x -=作换元,0x a b n n -= 则.)(110011 n n n n n n cb x a c c cd ca c d d ca x a b =-=--=--+=-=-- 当10a x ≠时，01≠b ，数列}{n b 是以c 为公比的等比数列，故;11-=n n c b b 当10a x =时，01=b ，}{n b 为0数列，故.N ,1∈=n a a n （证毕） 下面列举两例，说明定理1的应用. 例1．已知数列}{n a 满足：,4,N ,23 111=∈--=+a n a a n n 求.n a 解：作方程.2 3,23 10-=--=x x x 则 当41=a 时，.2112 3 ,1101= +=≠a b x a 数列}{n b 是以3 1 -为公比的等比数列.于是.N ,)3 1 (2112323,)31(211)3 1 (111 1∈-+-=+-=-=-=---n b a b b n n n n n n 例2．已知数列}{n a 满足递推关系：,N ,)32(1∈+=+n i a a n n 其中i 为虚数单位. 当1a 取何值时，数列}{n a 是常数数列？ 解：作方程,)32(i x x +=则.5 360i x +-= a 1= b a n+1=ca n +d 第四章 方程求解 1 代数方程(组)求解 1.1 常用求解工具—solve 求解代数方程或代数方程组, 使用Maple 中的solve 函数. 求解关于x 的方程eqn=0的命令格式为： solve(eqn, x); 求解关于变量组vars 的方程组eqns 的命令为： solve(eqns, vars); > eqn:=(x^2+x+2)*(x-1); := eqn () + + x 2x 2() ? x 1 > solve(eqn,x); ,,1? + 1212I 7? ? 1212 I 7 当然, solve 也可以求解含有未知参数的方程： > eqn:=2*x^2-5*a*x=1; := eqn = ? 2x 25a x 1 > solve(eqn,x); , + 54a 14 + 25a 28 ? 54a 14 + 25a 28 solve 函数的第一个参数是有待求解的方程或方程的集合, 当然也可以是单个表达式或者表达式的集合, 如下例： > solve(a+ln(x-3)-ln(x),x); 3e a ? + 1e a 对于第二个参数, Maple 的标准形式是未知变量或者变量集合, 当其被省略时, 函数indets 自动获取未知变量. 但当方程中含有参数时, 则会出现一些意想不到的情况： > solve(a+ln(x-3)-ln(x)); {}, = x x = a ? + ()ln ? x 3()ln x 很多情况下, 我们知道一类方程或方程组有解, 但却没有解决这类方程的一般解法, 或者说没有解析解. 比如, 一般的五次或五次以上的多项式, 其解不能写成解析表达式. Maple 具备用所有一般算法尝试所遇到的问题, 在找不到解的时候, Maple 会用RootOf 给出形式解. > x^7-2*x^6-4*x^5-x^3+x^2+6*x+4; ? ? ? + + + x 72x 64x 5x 3x 26x 4 > solve(%); + 15 ? 15()RootOf , ? ? _Z 5_Z 1 = index 1()RootOf , ? ? _Z 5_Z 1 = index 2(RootOf ,) ? ? _Z 5_Z 1 = index 3,,,,()RootOf , ? ? _Z 5_Z 1 = index 4()RootOf , ? ? _Z 5_Z 1 = index 5,, > solve(cos(x)=x,x); ()RootOf ? _Z ()cos _Z 对于方程组解的个数可用nops 命令获得, 如： > eqns:={seq(x[i]^2=x[i],i=1..7)}; := eqns {,,,,,, = x 12x 1 = x 22x 2 = x 32x 3 = x 42x 4 = x 52x 5 = x 62x 6 = x 72 x 7} > nops({solve(eqns)});128 但是, 有时候, Maple 甚至对一些“显而易见”的结果置之不理, 如： > solve(sin(x)=3*x/Pi,x); ()RootOf ? 3_Z ()sin _Z π 此方程的解为0 ,6π ±, 但Maple 却对这个超越方程无能为力, 即便使用allvalues 求解也只有下述结果： > allvalues(%); ()RootOf , ? 3_Z ()sin _Z π0. 另外一个问题是, Maple 在求解方程之前,会对所有的方程或表达式进行化简, 而不管表达式的类型, 由此而产生一些低级的错误： > (x-1)^2/(x^2-1); () ? x 12 ? x 21 > solve(%); 1 特征方程法求解递推关系中的数列通项 一、（一阶线性递推式）设已知数列}{n a 的项满足d ca a b a n n +==+11,,其中,1,0≠≠c c 求这个数列的通项公式。 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出一个方程,d cx x +=称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1：设上述递推关系式的特征方程的根为0x ，则当10a x =时，n a 为常数列，即0101,;x b a a x a a n n n +===时当，其中}{n b 是以c 为公比的等比数列，即01111,x a b c b b n n -==-. 证明：因为,1,0≠c 由特征方程得.10c d x -= 作换元,0x a b n n -=则.)(110011 n n n n n n cb x a c c cd ca c d d ca x a b =-=--=--+=-=-- 当10a x ≠时，01≠b ，数列}{n b 是以c 为公比的等比数列，故;11-=n n c b b 当10a x =时，01=b ，}{n b 为0数列，故.N ,1∈=n a a n （证毕） 下面列举两例，说明定理1的应用. 例1．已知数列}{n a 满足：,4,N ,23 1 11=∈--=+a n a a n n 求.n a 解：作方程.2 3 ,2310-=--=x x x 则 当41=a 时，.211 23,1101=+=≠a b x a 数列}{n b 是以3 1 -为公比的等比数列.于是 .N ,)3 1 (2112323,)31(211)31(1111∈-+-=+-=-=-=---n b a b b n n n n n n 例2．已知数列}{n a 满足递推关系：,N ,)32(1∈+=+n i a a n n 其中i 为虚数 特征根法求解二阶常系数线性微分方程 关于二阶常系数线性微分方程的解法： 1．线性齐次方程0=+'+''cy y b y a 的通解 解法 先解特征方程02=++c br ar 的根．设特征根为a ac b b r 2422 ,1-±-=，分以下三种情况： （1） 当042>-ac b 时，特征方程有两个相异的实根() ac b b a r 42122,1-±-=，则方程的通解为 x r x r C C y 21e e 21+=． （2）当042=-ac b 时，特征方程有重根a b r 2-=，则方程的通解为 ()x r x C C y e 21+=． （3）当042 <-ac b 时，特征方程有一对共轭的复根 a b ac a b r 2i 42i 22,1?-±- =±=βα， 则方程的通解为 ()x C x C y x ββαsin cos e 21+=． 定理 若21,y y 为齐次方程0=+'+''cy y b y a 的两个解，则 2211y C y C y += 亦是齐次方程的解，其中21,C C 是任意常数．又若21,y y 为线性无关时，则2211y C y C y +=是齐次方程的通解． 2．线性非齐次方程)(x f cy y b y a =+'+''的通解 定理 设* y 是非齐次线性方程的一个特解，而y 是相应的线性齐次方程的通解，则其和 *y y y += 为线性非齐次方程的通解． 具体解法： （1）先求)(x f cy y b y a =+'+''的特解*y （2）再求对应线性齐次方程的通解y ，根据定理相加即可* y y y += 例题1用特征根法求微分方程044=+'+''y y y 的通解 解：特征方程为r 2+4r+4=0 所以，（r+2）2=0 得重根r 1=r 2=-2，所以，方程的一般解为y=(c 1+c 2x)e -2x 例题2用特征根法求微分方程y``+3y`+2y=0的一般解 解：特征方程的解r 1=-1，r 2=-2一般解 x x e C e C y --+=221 例题3 用特征根法求微分方程02520422=+-x dt dx dt x d ;的一般解 解 微分方程的特征方程为 4r 2-20r +25=0, 即(2x -5)2=0, 其根为2 521==r r , 故微分方程的通解为 t t xe C e C x 252251+=, 即t e t C C x 2521)(+= 例题4求下列微分方程满足所给初始条件的特解y ''-3y '-4y =0, y |x =0=0, y '|x =0=-5; 解：微分方程的特征方程为 r 2 -3r -4=0, 即(r -4)(r +1)=0, 其根为r 1=-1, r 2=4, 故微分方程的通解为 y =C 1e -x +C 2e 4x . 由y |x =0=0, y '|x =0=-5, 得 ???-=+-=+54021 21C C C C , 解之得C 1=1, C 2=-1. 因此所求特解为 y =e -x -e 4x . 例题5求微分方程的通解2y ''+y '-y =2e x 解 微分方程的特征方程为 2r 2+r -1=0, 其根为211= r , r 2=-1, 故对应的齐次方程的通解为 x x e C e C Y -+=2211. 因为f (x )=2e x , λ=1不是特征方程的根, 故原方程的特解设为 y *=Ae x , 代入原方程得 当一个算法(如二分查找)中包含对自己的递归调用时，关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题，而这样的算法不在少数。实际上这是数学领域的问题，但是计算机科学又怎么能脱离数学而存在呢？^_^ 数学是好东西呀，可惜自己在这方面造诣颇浅，今生之遗憾亚。^_^ 还好，解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法，我们这里就说说这三种方法！这些是基础，如果以后要深入研究算法的话，这些知识是必须要精通的；如果并不想在算法方面有所深入的话，多学些知识也没错。我本身也是在学习，像这类的知识一般都比较死性，有些记住了，就可以掌握了。 1、Substitution Method 这是一种使用数学归纳法推导证明的方法，其步骤为先假设一个解，然后带入到递归方程中，利用数学归纳法推导，以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧，比较保险^_^。 [Ex1.] T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。 解：(这里我们只来找上界) 我们假设T(1) = θ(1)，猜测一个解T(n) = O(n^3)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^3，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出： T(n) = 4T(n/2) + n <= 4c((n/2)^3) + n = (c/2)n^3 + n = cn^3 - ((c/2)n^3 - n) 当c >= 2, n >= 1时，((c/2)n^3 - n) >= 0，这时T(n) <= cn^3，即T(n) = O(n^3)； 我们再回过头来看看当n = 1时这个解是否成立，即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大)，即该推导出的解也满足初始条件，所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢，我们不妨缩小上界范围再推导一次，这次我们猜测解为T(n) = O(n^2)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^2，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出： T(n) = 4T(n/2) + n <= 4c((n/2)^2) + n = cn^2 + n = cn^2 - (-n) 不能严格符合T(n) <= cn^2的定义，所以推导失败。但是失败是不是说明，T(n) = O(n^2)一定不成立呢？我们再做一次最后的努力，当出现上面的这种情况时，我们假设解仍为：T(n) = O(n^2)，只是我们选择对k < n, 有T(k) <= ak^2 - bk，我们选择减去一个低阶的项，这不会影响到n足够大时的渐进性的，这里是一个常用的技巧。 T(n) = 4T(n/2) + n <= 4(a(n/2)^2 - b(n/2)) + n = an^2 - bn - (bn - n) <= an^2 - bn (当b >= 1时) 这样我们找到了严紧解T(n) = O(n^2)。 附：递归关系求解 江超群 2016.10 代入法 例：求解递归关系 a n =a n?1+n ?1,a 1=0 应用：求一个递归关系为T (n )=T (n ?1)+简单表达式 类问题的时间复杂度 特征方程法 齐次递推关系方程求解 递归方程T (n )=r 1T (n ?1)+r 2T (n ?2)+?+r k T (n ?k ) 它对应的齐次关系的特征方程：x k =r 1x k?1+r 2x k?2+?+r k 特别的：二阶齐次方程求解 递归方程为：T (n )=r 1T (n ?1)+r 2T (n ?2) 它的递归方程为x 2?r 1x ?r 2=0 求解： 如果特征方程有两个不同实根x 1,x 2 ，则T (n )的通解是T (n )=u 1x 1n +u 2x 2n ，根据初值条件确定u 1,u 2后，得到方程的特解。 如果特征方程有一个根x 0，则T (n )的通解是T (n )=u 1x 0n +nu 2x 0n ，根据初值条件确定u 1,u 2得到方程的特解。 非齐次递推关系方程求解 非齐次特征方程解的形式为T (n )=r 1T (n ?1)+r 2T (n ?2)+?+r k T (n ?k )+f (n ) ()()()()()()123111 (2)1 ((3)2)2 ((...()...3)2)1.(1...321) 1,1211,0212n n n n n k n k n k a a n a n n a n n n a n k n n n a k n k k k k a kn k n n n a n n a n n ------=+-=+-+-=+-+-+-=+-++-+-+-=+-+-+++++=+-=--=+--=- =令， 目录 递归方程组解的渐进阶的求法——代入法 (11) 递归方程组解的渐进阶的求法——迭代法 (14) 递归方程组解的渐进阶的求法——套用公式法 (17) 递归方程组解的渐进阶的求法——差分方程法 (3) 递归方程组解的渐进阶的求法——母函数法 (7) 递归方程解的渐近阶的求法 递归方程组解的渐进阶的求法——套用公式法 这个方法为估计形如： T(n)=aT(n/b)+f(n) (6.17) 的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f (n)是一个确定的正函数。 (6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。 这个方法依据的是如下的定理：设a≥1和b≥1是常数f (n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式： 1. 若对于某常数ε>0，有 ， 则 ； 2. 若 ， 则 ； 3. 若对其常数ε>0，有 且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。 这里省略定理的证明。 在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个定理。读者可能已经注意到，这里涉及的三类情况，都是拿f(n)与作比较。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数较大，则T(n)=θ()；在第三类情况下，函数f(n)较大，则T(n)=θ(f (n))；在第二类情况下，两个函数一样大，则T(n)=θ()，即以n的对数作为因子乘上f(n)与T(n)的同阶。 此外，定理中的一些细节不能忽视。在第一类情况下f(n)不仅必须比小，而且必须是多项式地比小，即f(n)必须渐近地小于与的积，ε是一个正的常 数；在第三类情况下f(n)不仅必须比大，而且必须是多项式地比大，还要满足附加的“正规性”条件：af(n/b)≤cf(n)。这个附加的“正规性”条件的直观含义是a个子间题的再分解和再综合所需要的时间最多与原问题的分解和综合所需要的时间同阶。我们在一般情况下将碰到的以多项式为界的函数基本上都满足这个正规性条件。 还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的f(n)。在第一类情况和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于；类似地，在第二类情况和第三类情况之间也有一个间隙：f(n)大于但不是多项式地大于。如果函数f(n)落 在这两个间隙之一中，或者虽有，但正规性条件不满足，那么，本定理无能为力。 下面是几个应用例子。 例1考虑 T(n)=9T(n/3)+n0 特征方程法求解递推关系中的数列通项 湖北省竹溪县第一高级中学徐鸿 考虑一个简单的线性递推问题. 设已知数列的项满足 其中求这个数列的通项公式. 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出一个方程称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1设上述递推关系式的特征方程的根为，则当时，为常数列，即 ，其中是以为公比的等比数列，即. 证明：因为由特征方程得作换元 则 当时，，数列是以为公比的等比数列，故 当时，，为0数列，故（证毕） 下面列举两例，说明定理1的应用. 例1已知数列满足：求 解：作方程 当时，数列是以为公比的等比数列.于是 例2已知数列满足递推关系：其中为虚数单位. 当取何值时，数列是常数数列？ 解：作方程则 要使为常数，即则必须 现在考虑一个分式递推问题（*）. 例3已知数列满足性质：对于且求的通项公式. 将这问题一般化，应用特征方程法求解，有下述结果. 定理2如果数列满足下列条件：已知的值且对于，都有（其中p、q、r、h均为常数，且），那么，可作特征方程. （1）当特征方程有两个相同的根（称作特征根）时， 若则 若，则其中特别地，当存在使 时，无穷数列不存在. （2）当特征方程有两个相异的根、（称作特征根）时，则，其中 证明：先证明定理的第（1）部分. 作交换 则 ① ∵是特征方程的根，∴ 将该式代入①式得② 将代入特征方程可整理得这与已知条件矛盾.故特征方程的根于是 ③ 当，即=时，由②式得故 当即时，由②、③两式可得此时可对②式作如下变化： ④ 由是方程的两个相同的根可以求得 ∴ 将此式代入④式得 令则故数列是以为公差的等差数列. ∴ 其中 当时， 当存在使时，无意义.故此时，无穷数列是不存在的. 再证明定理的第（2）部分如下： ∵特征方程有两个相异的根、，∴其中必有一个特征根不等于，不妨令于是可作变换 故，将代入再整理得 特征方程法求解递推关系中的数列通项（二） 三、(分式递推式)定理3：如果数列}{n a 满足下列条件：已知1a 的值且对于N ∈n ，都有h ra q pa a n n n ++=+1（其中p 、q 、r 、h 均为常数，且r h a r qr ph -≠≠≠1,0,），那么，可作特征方程h rx q px x ++=. （1）当特征方程有两个相同的根λ（称作特征根）时， 若,1λ=a 则;N ,∈=n a n λ 若λ≠1a ，则,N ,1∈+=n b a n n λ其中.N ,)1(11∈--+-=n r p r n a b n λλ特别地，当存在,N 0∈n 使00=n b 时，无穷数列}{n a 不存在. （2）当特征方程有两个相异的根1λ、2λ（称作特征根）时，则11 2--=n n n c c a λλ，,N ∈n 其中).(,N ,)(211212111λλλλλ≠∈----= -a n r p r p a a c n n 其中 例3、已知数列}{n a 满足性质：对于,324,N 1++= ∈-n n n a a a n 且,31=a 求}{n a 的通项公式. 解:依定理作特征方程,3 24++=x x x 变形得,04222=-+x x 其根为.2,121-==λλ故特征方程有两个相异的根，使用定理2的第（2）部分，则有 .N ,)2 21211(2313)(11212111∈?-?-?+-=--?--=--n r p r p a a c n n n λλλλ ∴.N ,)5 1(521∈-= -n c n n ∴.N ,1)51(521)51(52211112∈----?-=--=--n c c a n n n n n λλ 即.N ,) 5(24)5(∈-+--=n a n n n 递归数列通项公式的求法 确定数列的通项公式，对于研究数列的性质起着至关重要的作用。求递归数列的通项 公式是解决数学竞赛中有关数列问题的关键，本文着重对递归数列通项公式加以研究。 基础知识 定义：对于任意的* N n ∈，由递推关系),,,(21k n n n n a a a f a ---= 确定的关系称为k 阶递归关系或称为k 阶递归方程，由k 阶递归关系及给定的前k 项k a a a ,,,21 的值(称为初始值)所确定的数列称为k 阶递归数列。若f 是线性的，则称为线性递归数列，否则称为非线性递归数列，在数学竞赛中的数列问题常常是非线性递归数列问题。 求递归数列的常用方法： 一．公式法 (1)设}{n a 是等差数列，首项为1a ，公差为d ，则其通项为d m n a a m n )(-+=； (2)设}{n a 是等比数列，首项为1a ，公比为q ，则其通项为m n m n q a a -=； (3)已知数列的前n 项和为n S ，则) 2() 1(11 ≥=??? -=-n n S S S a n n n 。 二．迭代法 迭代恒等式：112211)()()(a a a a a a a a n n n n n +-++-+-=--- ； 迭乘恒等式： 11 2211a a a a a a a a n n n n n ????= --- ，(0≠n a ) 迭代法能够解决以下类型一和类型二所给出的递推数列的通项问题： 类型一：已知)(,11n f a a b a n n +==+，求通项n a ； 类型二：已知n n a n f a b a )(,11==+，求通项n a ； 三．待定系数法 类型三：已知)1(,11≠+==+p q pa a b a n n ，求通项n a ； 四．特征根法 类型四：设二阶常系数线性齐次递推式为n n n qx px x +=++12（0,,1≠≥，q q p n 为常数），其特征方程为q px x +=2 ，其根为特征根。 （1）若特征方程有两个不相等的实根βα,，则其通项公式为n n n B A x βα+=（1≥n ），其中A 、B 由初始值确定； （2）若特征方程有两个相等的实根α，则其通项公式为1 )1([--+=n n n B A x αα（1≥n ）， 其中A 、B 由初始值确定。 解递归方程 下面的求解方法，其正确性可阅读组合数学中的相关内容。 1、 递推法 例：Hanoi 塔问题递归算法的时间复杂性，由以下递归方程给出： ()2(1) 1 2(1)1T n T n n T =-+≥??=? 递推求解如下： 232122122()2(1)1 2(2(2)1)1 2(2)21 2(3)221 ...... 2(1)2 (221) 22 (221) 21 n n n n n T n T n T n T n T n T ----=-+=-++=-++=-++++=+++++=+++++=- 所以，Hanoi 塔问题递归算法的时间复杂性为：()(2)n T n O = 例：分治法实例。设n 表示问题的尺寸，n/b 表示将问题分成a 个子问题后的每个子问题的尺寸，其中a,b 为常数。d(n)表示在分解或合成子问题而得到整个问题解决时的时间耗费。则整个问题的时间耗费由下面的递归方程给出： ()(/)() 2(1)1T n aT n b d n n T =+≥??=? 递推求解如下： 22223233221 0()((/)(/))() (/)(/)() ((/)(/))(/)() (/)(/)(/)() ...... (/)(/)k k k i i i T n a aT n b d n b d n a T n b ad n b d n a aT n b d n b ad n b d n a T n b a d n b ad n b d n a T n b a d n b -==++=++=+++=+++=+∑ 设：k n b =，则log b k n =，有： 1 0()(1)(/)k k i i i T n a T a d n b -==+∑ 当()d n 为常数时，有： 用特征方程与特征根解数列线性递推关系式的通项公式 一.特征方程类型与解题方法 类型一 递推公式为An+2＝aAn+1＋bAn 特征方程为 X 2 =aX+b 解得两根X 1 X 2 (1)若 X 1≠X 2 则A n =pX 1n +qX 2 n (2)若X 1=X 2=X 则A n =(pn+q)X n (其中p.q 为待定系数，由A 1.A 2联立方程求得) (3)若为虚数根，则为周期数列 类型二 递推公式为 特征方程为X = d c b a X X ++ 解得两根X 1 X 2 (1)若X 1≠X 2 则计算2111x A x A n n --++=2 1 x d cA b aA x d cA b aA n n n n -++-++=k 2 1x A x A n n -- 接着做代换B n =2 1 x A x A n n -- 即成等比数列 （2）若X 1=X 2=X 则计算x A n -+11=x d cA b aA n n -++1 =k+x A n -1 接着做代换B n =x A n -1 即成等差数列 (3)若为虚数根，则为周期数列 类型三 递推公式为 特征方程为X =d c b ax X ++2 解得两根X 1 X 2 。然后参照类型二的方法进行整理 类型四 k 阶常系数齐次线性递归式 A n+k =c 1A n+k-1+c 2A n+k-2+…+c k A n 特征方程为 X k = c 1X k-1+c 2X k-2+…+c k (1) 若X 1≠X 2≠…≠X k 则A n =X k n 11+X k n 22+…+X k k n k (2) 若所有特征根X 1,X 2,…,X s.其中X i 是特征方程的t i 次重根,有t 1+t 2+…+t s =k 则A n=X n Q n )(11+X n Q n )(22+…+X n Q s n s )( ， 其中)(n Q i =B 1+n B 2+…+n B ti ti 1 -（B 1,B 2，…，B ti 为待定系数） 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出 一个方程称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1设上述递推关系式的特征方程的根为，则当时，为常数列，即 ，其中是以为公比的等比数列，即 . 证明：因为由特征方程得作换元 则 当时，，数列是以为公比的等比数列，故 当时，，为0数列，故（证毕） 定理2如果数列满足下列条件：已知的值且对于，都有 （其中p、q、r、h均为常数，且），那么，可作特征方程. （1）当特征方程有两个相同的根（称作特征根）时， 若则 若，则其中特别地，当存在使时，无穷数列不存在. （2）当特征方程有两个相异的根、（称作特征根）时，则， 其中 证明：先证明定理的第（1）部分. 作交换 则 ① ∵是特征方程的根，∴ 将该式代入①式得② 将代入特征方程可整理得这与已知条件矛盾.故特征方程的根于是③ 当，即=时，由②式得故 当即时，由②、③两式可得此时可对②式作如下变化： ④ 由是方程的两个相同的根可以求得 ∴ 将此式代入④式得 令则故数列是以为公差的等差数列. ∴ 其中 当时， 当存在使时，无意义.故此时，无穷数列 是不存在的. 再证明定理的第（2）部分如下： ∵特征方程有两个相异的根、，∴其中必有一个特征根不等于，不妨令 于是可作变换 故，将代入再整理得 ⑤ 由第（1）部分的证明过程知不是特征方程的根，故 故所以由⑤式可得： ⑥ ∵特征方程有两个相异根、方程有两个相异根、，而方程与方程又是同解方程. ∴ 将上两式代入⑥式得 当即时，数列是等比数列，公比为.此时对于都有 当即时，上式也成立. 由且可知 所以(证毕) 注：当时,会退化为常数;当时,可化归为较易解的递推关系,在此不再赘述. 1、将方程x5 +5x3– 2x + 1 = 0 改写成各种等价的形式进行迭代，观察迭代是否收敛，并给 出解释。 （1）画图： x1=-6:0.01:6; x2=-3:0.01:3; x3=-1:0.01:1; x4=-0.8:0.01:-0.75; y1=x1.^5 +5*x1.^3-2*x1+1; y2=x2.^5 +5*x2.^3-2*x2+1; y3=x3.^5 +5*x3.^3-2*x3+1; y4=x4.^5 +5*x4.^3-2*x4+1; subplot(2,2,1),plot(x1,y1) ,title('子图(1)') ,grid on, subplot(2,2,2),plot(x2,y2) ,title('子图(2)'),grid on, subplot(2,2,3),plot(x3,y3) ,title('子图(3)'),grid on, subplot(2,2,4),plot(x4,y4) ,title('子图(4)') ,grid on, 由图可知x 的初值应在（-0.78，0.76）之间。 （2）解：第一步构造迭代函数 x f x () 53512 x x x ++= 1()x f x = 32121555x x x x =-+- 2()x f x = 32521x x x x =-+- 3()x f x = 第二步 利用加速迭代收敛法变形后： 5342 41012515x x x x x --+=-- 1()x f x = 62352435322 x x x x x x x --=++- 2()x f x = 2 5328561 x x x x x x -+=++- 3()x f x = 第三步 迭代 设定初值 00.75x =- 1()n n x f x +=n=0,1,2,3……… 用 MA TLAB 编程 x=-077;y=-0.77;z=-0.77; for k=1:30 x=(-4*x^5-10*x^3+1)/(2-5*x^4-15*x^2); y=(2*y^6+4*y^2-3*y)/(5*y^3+3*y^5+2*y-2); z=(8*z^2-2*z)/(z^5+5*z^3+6*z-1); x,y,z; end 迭代结果为： x = -61.5948 y = -0.7685利用递归思想解决计数问题
递归方程解的渐近阶的求法
特征方程特征根法求解数列通项公式
递归方程求解方法综述
不动点(特征方程)法求数列通项
第4章-方程求解（Maple 中文教程）
(第45讲)特征方程法求递推数列的通项公式
特征根法求解二次微分方程
递归分析方法
附：递归关系式求解
第1章递归方程解的渐近阶的求法
特征方程法求解数列通项的依据
特征方程法求解递推关系中的数列通项(二)
递归数列通项公式的求法
递归方程求解
特征方程解数列递推关系
特征方程法
迭代方法求解方程
相关主题
文本预览