行列式算法归纳总结

第一篇：行列式算法归纳总结

数学与统计学学院

中期报告

学院:

专业:

年级:

题目:

行列式的算法归纳

学生姓名: 学号:

指导教师姓名 职称:

2012年6月20日

目录

引言..................................................................................................................................................2 1 行列式性质...................................................................................................................................2 2 行列式计算方法...........................................................................................................................5

2.1定义法.................................................................................................................................5 2.2递推法.................................................................................................................................6 2.3化三角法.............................................................................................................................9

2.4拆元法...............................................................................................................................11.4加边法..............................................................................................................................12 2.6数学归结法.......................................................................................................................14 2.7降价法...............................................................................................................................15 2.8利用普拉斯定理...............................................................................................................16 2.9利用范德蒙行列式...........................................................................................................17 结论................................................................................................................................................18 参考文献.........................................................................................................................................18

行列式的概念及应用

摘要：本文先列举行列式计算相关性质，然后归纳总结出了行列式的计算方法，包括：定义法，化三角法，递推法，拆元法，加边法，数学归结法，降价法，利用拉普拉斯定理和利用范德蒙行列式的方法。

关键词：行列式；线性方程组；范德蒙行列式

The concept and application of determinant

In this article, it first lists some calculated properties of determinants, and then characterizes some methods to calculate determinant, including: definition, triangulation, recursive method, remove method, bordered，Mathematical induction，reduction，the method using Laplace theorem or the van demon determinant.Keywords: determinant;system of linear equations;Van demon determinant

引言

行列式的概念最初是伴随着方程组的求解而发展起来的。行列式的提出可以追溯到十七世纪，最初的雏形由日本数学家关孝和与德国数学家戈特弗里德·莱布尼茨各自独立得出，时间大致相同。日本数学家关孝和提出来的，他在1683年写了一部名为解伏题之法的著作，意思是“解行列式问题的方法”，书中对行列式的概念和它的展开已经有了清楚的叙述。欧洲第一个提出行列式概念的是德国数学家，微积分学奠基人之一莱布尼茨。十八世纪开始，行列式开始作为独立的数学概念被研究。十九世纪以后，行列式理论进一步得到发展和完善。矩阵概念的引入使得更多有关行列式的性质被发现，行列式在许多领域都逐渐显现出重要的意义和作用，出现了线性自同态和向量组的行列式的定义。行列式的性质

性质1 行列互换，行列式值不变，即

a11a12a1na21a22a2nan1an2anna11[1]

a21a22a2nan1an2 anna12a1n其实，元素aij在上式的右端位于第j行第i列，即此时i是列指标，j为行指标。

在行列式中，行与列的地位是对称的，所以有关行的性质，对列也成立。

性质2 如果行列式中一行为零，那么行列式为零。

的元都是二项式，那么这个行列式等于把这些性质3 如果行列式的某一行或一列二项式各取一项作成相应行或列而其余行或列不变的两个行列式的和。

即

a11b1jc1ja21b2jc2jan1bnjcnja1na11b1ja2na21b2jannan1bnja1na11c1ja2na21c2jannan1cnja1na2n ann这就是说，如果某一行是两组数的和，那么这个行列式就等于两个行列式的和，而这两个行列式除这一行以外全与原来行列式的对应的行一样。

性质4 如果行列式中有两行相同，那么行列式为零，所谓两行相同就是说两行的对应元素都相等。

性质5 如果行列式中两行成比例，那么行列式为零。性质6 把一行的倍数加到另一行，行列式不变。性质7 对换行列式中两行的位置，行列式反号。

2.行列式的计算方法

2.1 定义法

n阶行列式计算的定义[3]：

a11Dna21an1其中，j1j2jna12a1na22a2nan2ann(1)(j1j2jn)a1j1a2j2anjn

j1j2jn表示对所有n级排列求和。j1j2jn是1,2,,n的一个排列，当j1j2jn是(j1j2jn)偶排列时，(1)是正号；当j1j2jn是奇排列时，(1)(j1j2jn)是负的。a1j1a2j2anjn是D中取自不同行不同列的n个元素的乘积。

a11a21例2.1：证明Da31a12a22a32a42a52a13a23000a14a24000a15a2500.00a41a51分析 观察行列式我们会发现有许多零,故直接用定义法.证明： 由行列式的定义知除去符号差别外行列式一般项可表示为a1j1a2j2anjn 则

Dnj1j2j5(1)(j1j2j5)a1j1a2j2anjn.（3）

其中j1,j1,,j5为1,2,3,4,5的任意排列,在D中位于后三行后三列的元素为零,而在前两行前两列中,取不同行不同列的元素只有四个,就是说（3）式中每一项至少有一个来自后三行后三列.故D=0.注意 此方法适用于阶数较低的行列式或行列式中零的个数较多.2.3 递推法

应用行列式的性质，把一个较高阶行列式表示为具有相同结构的较低阶行列式（比如，n-1阶或n-1阶与n-2阶等）的线性关系式，这种关系式称为递推关系式。根据递推关系式及某个低阶初始行列式（比如二阶或一阶行列式）的值，便可递推求得所给n阶行列式的值，这种计算行列式的方法称为递推法。

注意：用此方法一定要看行列式是否具有较低阶的相同结构如果没有的话，即很难 找出递推关系式，从而不能使用此方.[4]

例2.2证如下行列式等式

Dn1001000000

0001n1n1,其中（虽然这是一道证明题，但我们可以直接求 证明： Dn出其值，从而证之）。

分析：此行列式的特点是：除主对角线及其上下两条对角线的元素外，其余的元素

都为零，这种行列式称“三对角”行列式。从行列式的左上方往右下方看，即知Dn1与Dn具有相同的结构。因此可考虑利用递推关系式计算。

证明：Dn按第1列展开，再将展开后的第二项中n-1阶行列式按第一行展开有：

Dn（＋）Dn－1－Dn－2，这是由Dn1 和Dn2表示Dn的递推关系式。若由上面的递推关系式从n阶逐阶往低 阶递推，计算较繁，注意到上面的递推关系式是由n-1阶和n-2阶行列式表示n阶行列式，因此，可考虑将其变形为：

Dn－Dn－1＝Dn－1－Dn－2＝（Dn－1－Dn－2）或 Dn－Dn－1＝Dn－1－Dn－2＝（。Dn－1－Dn－2）现可反复用低阶代替高阶，有：

23Dn－Dn－1＝（Dn－1－Dn－2）＝（Dn－2－Dn－3）＝（Dn－3－Dn－4）＝＝（D2－D1）=同样有 n2n－2[()()](1)2n

23Dn－Dn－1＝（Dn－1－Dn－2）＝（Dn－2－Dn－3）＝（Dn－3－Dn－4）[()()](2)n1n1因此当 时，由（1）（2）式可解得：Dn。

＝＝（D2－D1）=n2n－22n

小结：虽然我们从一个行列式中可以看出有低阶的相同的结构，然后得到一递推关系式，但我们不要盲目乱代，一定要看清这个递推关系式是否可以简化我们的计算，如果不行的话，就要适当地换递 推关系式，如本题。

2.3化三角形法

运用行列式的性质是计算行列式的一个重要途径,大多数行列式的计算都依赖于行列式的性

[7]质,将行列式化成上三角(下三角或反三角)的形式,再根据行列式的定义来计算行列式.行列式的性质告诉了我们该如何求行列式,而一切的行列式都可以根据以上性质来进行初等行变换(列变换),变成阶梯形(上三角)的行列式,再根据定义计算即可.其计算步骤可归纳如下:

(ⅰ)看行列式的行和(列和),如果行列和相等,则均加到某一列(行)（直观上加到第一列(行)）.(ⅱ)有公因子的提出公因子.(ⅲ)进行初等行变换(列变换)化成上三角(下三角或反三角)的行列式.(ⅳ)由行列式的定义进行计算.由以上四步,计算一般行列式都简洁多了.123n1234[6]例2.3 计算行列式Dn345n1n12.n12n2n1分析 直接用化三角形法化简很烦,观察发现对于任意相邻两列中的元素,位于同一行的元素中,后面元素与前面元素相差1,因此先从第n1列乘-1加到第n列,第n2列乘-1加到第n1列, 这样做下去直到第1列乘-1加到第2列,然后再计算就显得容易.123n1234解：Dn345n1n12123111111111n11n1

10001000n12n2n1

n1n112n12n111210011100n10n0nn1n0000000n0

000n0n0

00n0000n1n(n1)000n2n00(n1)(n2)1n(n1)(1)2 n2n(n1)(n1)n1n(1)2.2问题推广

在例2.3中1,2,,n,这n个数我们可以看成有限个等差数列在循环,那么对于一般的等差数列也应该适应.计算行列式 [1]

a1Da1da12da1(n1)da1a1da12da1(n1)da1d2d(n1)da1a1da12da13da1ddda12da1(n1)da13da14da1ddda1nda1a1(n3)dda1nda1a1da1(n2)d

ddd(1n)ddddnd

d(1n)dd d(1n)dddndnd0000000nd0 d(n1)dnnd2d(n1)dndnd00(n1)(n2)d(n1)dn1(a1)(nd)(1)2

nn(n1)(n2)1n(a1a1(n1)d)n1()(nd)(1)2.n2

(n1)(n2)1n(a1a1(n1)dn1)(nd)(1)2结论如果将例2.3中的数a11，d1代入(n2显然成立.2.4．拆元法

由行列式拆项性质知，将已知行列式拆成若干个行列式之积，计算其值，再得原行 列式值，此法称为拆行（列）法。

由行列式的性质知道，若行列式的某行（列）的元素都是两个数之和，则该行列式可拆成两个行列式的和，这两个行列式的某行（列）分别以这两数之一为该行（列）的元素，而其他各行（列）的元素与原行列式的对应行（列）相同，利用行列式的这一性质，有时较容易求得行列式[2]的值。

例2.4求下列行列式的值 设n阶行列式：

a11a21an1a12a1na22a2n1

an2ann且满足aijaji,i,j1,2,,n,对任意数b，求n阶行列式

a11ba12ba1nba21ba22ba2nb?

an1ban2bannb 分析:该行列式的每个元素都是由两个数的和组成，且其中有一个数是b，显然 用拆行（列）法。

解：

a11ba12ba1nba11a12ba1nbba12bDa21ba22ba2nba21a22ba2nbba22bnan1ban2bannban1an2bannbban2ba11a12a1nba11ba1nb1a12a1na21a22a2nb1a22a2na21ba2nbb

an1an2annban1bannb1an2anna11a12a1na111a1n1a12a1na21a22a2nba211a2n1a22a2nb

an1an2annan11ann1an2annnnn1bA2ibA1i1bi1iAij。

i1,j1又令

a11a12a1nA=a21a22a2n,且aijaji,i,j1,2,,n。

an1an2ann

所以 有A1,且A'A。

由A－1＝A＊A得：AA－1A＊即A＊A＝E 所以 A＊＝A－1。7

a1nba2nbannb

又（A＊）(A1)'(A')1(A)1A＊，所以 A*也为反对称矩阵。

*又 Aij(i,j1,2,,n)为A的元素，所以有i1,j1'nAij0。

从而知：Dn1bi1,j1nAij1。

2.5．加边法

计算行列式往往采用降阶的办法，但在一些特殊的行列式的计算上却要采用加边法。行列式的加边法是为了将行列式降阶作准备的。更有利于将行列式化成上三角的形式，其加边的元素，也可根据计算的难易程度来确定。具有随意性。利用行列式按行（列）展开的性质把n阶行列式通过

[3]加行（列）变成与之相等的n1阶行列式,然后计算.添加行列式的四种方法[18]:设Dna11a21an1a12a1na22a2nan2ann.（1）首行首列Dna11a21an1a11a21an1a11a21an1a11a21an1a12a1na22a2nan2anna12a1na22a2nan2anna12a1na22a2nan2anna12a1na22a2nan2ann1a1a2an0a110a210a11a21an1a1a2a31a11a21a3100a12a22an2a11a21a310a12a22a320a12a1na22a2n.an2ann01a13a1a23a2.an3ana12a1na22a2na32a3n.00a13a1a23a2a33a3.010an1（2）首行末列Dn（3）末行首列Dn（4）末行末列Dn例2.5 计算n 阶行列式： [4]

x121Dnx1x2x1x2x1x2x221x1x2x1x2x1x2xn21

分析 我们先把主对角线的数都减1，这样我们就可明显地看出第一行为x1与x1,x2,,xn相乘，第二行为x2与x1,x2,,xn相乘，„„，第n行为xn与x1,x2,,xn相乘。这样就知道了该行列式每行有相同的因子x1,x2,,xn，从而就可考虑此法。解：

1x1x20x121x1x22Dn0x2x1x210xnx1nxn1x1x2x1(i1,,n)x2xnx2ri1xir1x1100x2xn001001xnx22i12xn1x1100xnn1

1xic1xici1(i1,,n)x2xn0100011xi2。i1n000n1注意:加边法最在的特点就是要找出每行或每列相同的因子，那么升阶之后，就可利用行列式的性质把绝大部分元素化为零，然后再化为三角形行列式，这样就达到了简化计算的效果。

2.6数学归结法

数学归纳法有两种一种是不完全归纳法,另一种是完全归纳法,通常用不完全归纳法寻找行列式

[5]的猜想,再用数学归纳法证明猜想的正确性.基本方法

1)先计算n1,2,3时行列式的值.2)观察D1,D2,D3的值猜想出Dn的值.3)用数学归纳法证明.例2.6 证明： [6]2cos1 Dn12cos100010000000012cossin(n1)sin(sin0)0002cos2cos1证：当n1,2时，有

sin(11)sin

2cos1sin(21)D24cos2112cossinD12cos结论显然成立。

现假定结论对小于等于n1时成立。即有

Dn2将Dn按第1列展开，得

sin(n21),sinDn1

sin(n11)。

sin2cos1Dn0012cos00000012cos2cos10002cos00000012cos2cos1(n1)2cos1(n1)2cosDn1Dn2sin(n11)sin(n21)sinsin2cossinnsin(n1)sin2cossinnsinncoscosnsinsinsinncoscosnsinsinsin(n1)sin2cos

故当对n时，等式也成立。得证。

2.7降阶法

n阶行列式等于它的任意一行(列)各元素与其对应的代数余子式乘积的和.即

DaijAij(i1,2,,n)或DaijAij(j1,2,,n).j1i1nn行列式按一行（列）展开将高阶转化为若干低阶行列式计算方法称为降阶法.这是一种计算[9]行列式的常用方法.1301例2.7 计算D30141121011001.1解 D30911022001109111220110214.21注意 对于一般的n阶行列式若直接用降阶法计算量会大大加重.因此必须先利用行列式的性质将行列式的某一行（列）化为只含有一个非零元素,然后再按此行（列）展开,如此进行下去,直到二阶.2.8 利用拉普拉斯定理

在利用行列式的一行(列)展开式时,我们可以发现计算行列式可以按某一行(列)展开,进行计算行列式.试想,我们可以根据行列式的某一个K级字式展开吗? 拉普拉斯经过对行列式的研究.终于发现此种方法可行,并给出了严密的证明,为了使行列式的计算更为简洁,现引入拉普拉斯定理.拉普拉斯定理[12]:设在行列式D中任意取定了k1kn1个行,由这k行元素所组成的一切K级字式与它们的代数余子式的乘积的和等于行列式D.拉普拉斯定理的四种特殊情形：

1）AnnCmn00BmmAnnCmnAnnBmm

Ann2）

0CnmAnnBmm Bmm3）Bmm(1)mnAnnBmm 4）

CnmBmmAnn0(1)mnAnnBmm

例2.8计算n阶行列式

aaaabDnbb



解

Dn(i2，n1)aaaabi1200(n1)a000000aa0a

0C2Ci0b(n2)(i3,n)00000000利用拉普拉斯定理(n1)ab(n2)2200n20000(n2)(n2)[(n2)ab(n1)]()2.9 利用范德蒙行列式

范德蒙行列式[14]

：

1x1x12x1n11x2x22n1x21x3x32n1x31xn2xn1jinn1xn(xixj)

(an1)n1(an1)n2例2.9[16]

(an2)n1(a1)n1(an2)n2(a1)n2an21a11an1an2 a1：计算n阶行列式 Dnan11解 ： 显然该题与范德蒙行列式很相似，但还是有所不同，所以先利用行列式的性质把它化为范德蒙行列式的类型。

先将的第n行依次与第n-1行，n-2行，„,2行，1行对换，再将得到到的新的行列式的第n行与第n-1行，n-2行，„,2行对换，继续仿此作法，直到最后将第n行与第n-1行对换，这样，共经过（n-1）+（n-2）+„+2+1=n（n-1）/2次行对换后，得到

1Dn(1)n(n1)21an21a11a an2an1an1(an1)n2(an1)n1(an2)n2(a1)n2(an2)n1(a1)n1上式右端的行列式已是范德蒙行列式，故利用范德蒙行列式的结果得

EnABnmEmBA

Dn(1)n(n1)21jin[(ani)(anj)](1)n(n1)21jin(ij)

结论：

综上所述，针对行列式结构特点而采用与之相适应的计算技巧，从而总结出了多种类型题目所适用的计算方法，因此，对于计算行列式的方法，我们首先要熟练掌握并懂得如何选择、运用，不管是哪一种行列式的计算，选取恰当的方法，才能较快地解出其值。

参考文献

［1］李师正等.高等代数复习解题方法与技巧.高等教育出版社, 2005 ［2］张贤科 许甫华.高等代数学.清华大学出版社, 2000 ［3］刘学鹏等.高等代数复习与研究.南海出版公司, 1995 ［4］许甫华 张贤科.高等代数解题方法.清华大学出版社, 2001 ［5］李永乐.研究生入学考试线性代数.北京大学出版社, 2000 ［6］王萼芳 石生明.高等代数学.高等教育出版社, 2003 ［7］吕林根.许子道.解析几何.高等教育出版社 2006 ［8］贾冠军.菏泽师专学报, Journal of Heze Teachers College, 1999年 02期

［9］吴晓庆，关丰宇.行列式的相关性质与应用.数学学习与研究 2011年第3期

[10] 张子杰.行列式计算中的一些方法.河北工程技术高等专科学院学报.[11] 北京大学数学系几何与代数教研室代数小组，高等代数（第二版）.北京：高等教育出版社，1994 [12] 王品超著，高等代数新方法.济南：山东教育出版社，1989 [13] 李师正,高等代数复习解题方法与技巧.高等教育出版社,2005

[14] 刘洪星,高等代数选讲.机械工业出版社,2009 [15] 姚慕生,高等代数.上海：复旦大学出版社，2002 [16] 许甫华，张贤科.高等代数解题方法.北京：清华大学出版社，2001 [17] 期刊论文 ,一个n阶行列式的若干种计算方法.科技信息，2009，（3）：18-23 [18] 张禾瑞 郝鈵新 《高等代数》 高等教育出版社 1999 [19] 徐仲 陆全 张凯院 吕全义 安晓虹 《高等代数》 西北工业大学出版社 2006

第二篇：算法总结

算法分析与设计总结报告

71110415 钱玉明

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

下面我将谈谈我对这门课程的心得与体会。

一、数学是算法的基础

经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。

①主定理

本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。

②随机算法中的许多定理的运用

在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。

这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。

二、算法的核心是思想

我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。

①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。

动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。

贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。

周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。

回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。

分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。

②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。

这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。

三、算法与应用紧密相关

我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。

这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。

四、对计算模型和NP问题的理解

由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。

首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。

NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。

最后谈谈对这门课程的建议

①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。

②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。

③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。

第三篇：算法总结

算法分块总结

为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用

分层图思想的应用：

用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：

最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：

容量有上下界的最大流的应用：

欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：

求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：

抽象成数学模型就是：

设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k

首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树；

2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：

加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法：

首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：

Dijkstra 算法应用： Folyed 算法应用：

Bellman-Ford 算法的应用：

差分约束系统的应用：

搜索算法

搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用：

IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索：

可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划

动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP：

状态划分比较困难的题目： 树形DP：

四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)

高档数据结构的应用

并查集的应用：

巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用：

总结用线段树解题的方法

根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等

树的每个节点根据题目所需，设置变量记录要求的值

用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；

Trie图的应用探索： 后缀数组的应用研究：

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；

计算几何

掌握基本算法的实现。凸包的应用：；

半平面交算法的应用：；

几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：；

转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：；

经典算法：找平面上的最近点对。

贪心

矩形切割

二分思想应用

活用经典算法

利用归并排序算法思想求数列的逆序对数：

利用快速排序算法思想，查询N个数中的第K小数：

博弈问题

博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。

第一类：推结论。典型题目： 第二类：递推。典型题目：

比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质：

1． 所有的结束位置都是P位置。

2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：

1． 将所有的结束位置标为P位置。

2． 将所有能一步到达P位置的点标为N位置。

3． 找出所有只能到达N位置的点，将它们标为P位置。

4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为

g(x)min{n0,ng(y)对于所有yF(x)}

1． 对于所有的结束位置x，g(x)= 0。

2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。

3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。

定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四类：极大极小法。

典型题目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩阵妙用

矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目：

数学模型举例

向量思想的应用：

UVA 10089：注意降维和向量的规范化 ；

利用复数思想进行向量旋转。

UVA 10253：

递推

数代集合

数代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广

第四篇：算法总结材料

源程序代码：

}

一、自然数拆分（递归）

} #include

二、快速排序（递归）int a[100];void spilt(int t)#include { int k,j,l,i;main()for(k=1;k<=t;k++){int i,a[11]={0,14,12,5,6,32,8,9,15,7,10};{ printf(“%d+”,a[k]);} for(i=0;i<11;printf(“%4d”,a[i]),++i);printf(“n”);printf(“n”);j=t;l=a[j];quicksort(a,10);for(i=a[j-1];i<=l/2;i++)for(i=0;i<11;printf(“%4d”,a[i]),++i);{ a[j]=i;a[j+1]=l-i;printf(“n”);}

spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i;

int value=a[from];printf(“please enter the number:”);

while(from

a[from]=a[to];

while(from

++from;

a[to]=a[from];

}

a[from]=value;

return from;

}

void qsort(int a[],int from,int to){ int pivottag;if(from

{pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to);

} scanf(“%d”,&n);

for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2);

三、删数字（贪心）

#include #include void main(){

int a[11]={3,0,0,0,9,8,1,4,7,5,1};

int k=0,i=0,j;

int m;

while(i<11)

{

printf(“%d ”,a[i]);

i++;}

printf(“n please input delete number:”);

四、全排列（递归）#include A(char a[],int k,int n){

int i;char temp;if(k==n)

for(i=0;i<=3;i++)

{printf(“%c ”,a[i]);} else {

for(i=k;i<=n;i++)

{ temp=a[i];

a[i]=a[k];

a[k]=temp;

A(a,k+1,n);

} } } main(){

int n;

char a[4]={'a','b','c','d'},temp;

A(a,0,3);

getch();

return 0;}

五、多段图（动态规划）#include “stdio.h”

#define n 12 //图的顶点数

{ while(from=value)--to;

scanf(“%d”,&m);for(k=0;k

{

for(i=0;i<=11-k;i++)

{

if(a[i]>a[i+1])

{

for(j=i;j<10;j++)

{a[j]=a[j+1];}

break;//满足条件就跳转

}

} }

int quicksort(int a[],int n){

qsort(a,0,n);}

}

printf(“the change numbers:”);

for(i=0;i<11-m;i++)

{

if(a[i]!=0)

{ printf(“%d ”,a[i]);}

}

}

#define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组

int path[k];//存储最短路径的数组

void creatgraph()//创建图的(成本)邻接矩阵 { int i,j;

for(i=0;i

for(j=0;j

scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 }

void printgraph()//输出图的成本矩阵 { int i,j;

printf(“成本矩阵:n”);

for(i=0;i

{ for(j=0;j

printf(“%d ”,cost[i][j]);

printf(“n”);

} }

//使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n];

for(i=0;i

v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++)

if(cost[i][j]>0 &&(cost[i][j])+v[j]

{length=cost[i][j]+v[j];temp=j;}

v[i]=length;

d[i]=temp;

}

path[0]=0;//起点

path[k-1]=n-1;//最后的目标

for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//将最短路径存入数组中 }

//使用向后递推算法求多段图的最短路径

void BackPath(){ int i,j,length,temp,v[n],d[n];

for(i=0;i

for(i=1;i<=n-1;i++)

{ for(length=MAX,j=i-1;j>=0;j--)

if(cost[j][i]>0 &&(cost[j][i])+v[j]

{length=cost[j][i]+v[j];temp=j;}

v[i]=length;

d[i]=temp;

}

path[0]=0;

path[k-1]=n-1;

for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];}

//输出最短路径序列 void printpath(){ int i;

for(i=0;i

printf(“%d ”,path[i]);}

main(){ freopen(“E:1input.txt”,“r”,stdin);

creatgraph();

printgraph();

FrontPath();

printf(“输出使用向前递推算法所得的最短路径:n”);

printpath();

printf(“n输出使用向后递推算法所得的最短路径:n”);

BackPath();

printpath();printf(“n”);}

六、背包问题（递归）int knap(int m, int n){

int x;

x=m-mn;

if x>0

sign=1;

else if x==0

sign=0;

else

sign=-1;

switch(sign){

case 0: knap=1;break;

case 1: if(n>1)

if knap(m-mn,n-1)

knap=1;

else

knap= knap(m,n-1);

else

knap=0;

case-1: if(n>1)

knap= knap(m,n-1);

else

knap=0;

} }

七、8皇后（回溯）#include #include #define N 4 int place(int k, int X[N+1]){

int i;

i=1;

while(i

if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))

return 0;

i++;

}

return 1;}

void Nqueens(int X[N+1]){

int k, i;

X[1]=0;k=1;

while(k>0){

X[k]=X[k]+1;

while((X[k]<=N)&&(!place(k,X)))

X[k]=X[k]+1;

if(X[k]<=N)

if(k==N){ for(i=1;i<=N;i++)

printf(“%3d”,X[i]);printf(“n”);

}

else{ k=k+1;

X[k]=0;

}

else k=k-1;

} }

void main(){

int n, i;

int X[N+1]={0};

clrscr();

Nqueens(X);

printf(“The end!”);}

八、图着色（回溯）#include #define N 5 int X[N]={0,0,0,0,0};int GRAPH[N][N]={ {0,1,1,1,0}，{1,0,1,1,1}，{1,1,0,1,0}，{1,1,1,0,1}，{0,1,0,1,0} };int M=4;int count=0;int mcoloring(int k){

int j,t;

while(1){

nextValue(k);

if(X[k]==0)

return 0;

if(k==(N-1)){

for(t=0;t

printf(“%3d”,X[t]);

printf(“n”);

count++;

}

else

mcoloring(k+1);

} } int nextValue(int k){

int j;

while(1){

X[k]=(X[k]+1)%(M+1);

if(X[k]==0)

return 0;

for(j=0;j

if((GRAPH[k][j]==1)&&(X[k]==X[j]))

break;

}

if(j==N){

return 0;

}

} } void main(){

int k;

clrscr();

k=0;

mcoloring(k);

printf(“ncount=%dn”,count);}

矩阵链乘法（动态规划） 符号S[i, j]的意义：

符号S(i, j)表示，使得下列公式右边取最小值的那个k值

public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s)

{

int n=p.length-1;

for(int i = 1;i <= n;i++)m[i][i] = 0;

for(int r = 2;r <= n;r++)

for(int i = 1;i <= n-r+1;i++){

int j=i+r-1;

m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];

s[i][j] = i;

for(int k = i+1;k < j;k++){

int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if(t < m[i][j]){

m[i][j] = t;

s[i][j] = k;}

}

}

}

O的定义：

如果存在两个正常数c和n0，对于所有的n≥n0时，有：

|f(n)|≤c|g(n)|，称函数f(n)当n充分大时的阶比g(n)低，记为

f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义：

如果存在正常数c和n0，对于所有n≥n0时，有：

|f(n)|≥c|g(n)|，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，即f(n)的阶不低于g(n)的阶。记为：

f(n)=Ω(g(n))。Θ的定义：

如果存在正常数c1，c2和n0，对于所有的n>n0，有：

c1|g(n)|≤f(n)≤c2|g(n)|，则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法：

O(1)

(2)指数时间算法：

O(2n)

Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1)

贪心方法基本思想：

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择

所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

多段图：

COST[j]=c(j,r)+COST[r];

回溯法：

(假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。约束条件：

(1)显式约束：限定每一个xi只能从给定的集合Si上取值。

(2)解

空

间：对于问题的一个实例，解向量满足显式

约束条件的所有多元组，构成了该实例

的一个解空间。

(3)隐式约束：规定解空间中实际上满足规范函数的元

组，描述了xi必须彼此相关的情况。基本做法：

在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

8皇后问题

约束条件

限界函数：

子集和数问题：

约束条件

限界函数：

回溯法－－术语：

活结点：已生成一个结点而它的所有儿子结点还没有

全部生成的结点称为活结点。

E-结点：当前正在生成其儿子结点的活结点叫E-结点。

死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。

使用限界函数的深度优先节点生成的方法成为回溯法；E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法

且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别：

分支限界法本质上就是含有剪枝的回溯法，根据递归的条件不同，是有不同的时间复杂度的。

回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解

分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解

一般如果只考虑时间复杂度二者都是指数级别的

可是因为分支限界法存在着各种剪枝，用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){

int j;

X[k]=1;

if(s+W[k]==M){

for(j=1;j<=k;j++)

printf(“%d ”,X[j]);

printf(“n”);

}

else

if((s+W[k]+W[k+1])<=M){

sumofsub(s+W[k],k+1,r-W[k]);

}

if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){

X[k]=0;

sumofsub(s,k+1,r-W[k]);

} } void main(){

M=30;

W[1]=15;

W[2]=9;

W[3]=8;

W[4]=7;

W[5]=6;

W[6]=5;

W[7]=4;

W[8]=3;

W[9]=2;

W[10]=1;

sumofsub(0,1,60);}

P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L，则此问题L是NP-难度的。如果L是NP难度的且L NP，则此问题是NP-完全的

第五篇：F2 算法总结

算法！

 High low method

p62  Inventory control level p123  Formal of EOQ

p125  Formal of EBQ

p127  Efficiency，capacity and production volume ratios

p140  Remuneration method

p141—p146  Apportioning general overheads

p165  Calculation of overhead absorption rates p171  Over and under absorption of overheads p176(over=budget>actual

under=budget

and

absorption

costing

p188-p189(important) Reconciling profits p191  Process costing p199  Losses in process costing e.g.p200-p201 (FIFO

P215-p217and

Weighted

average

cost p220-p221) Losses with scrap value e.g.p205-p207  Losses with a disposal cost e.g.p210(三个相对比) Equivalent units e.g.p211-p212  Joint products in process accounts p230-p231  By products in process accounts(4ways)p233-p234  Batch costing p246-p247  Flexible budgets and budgetary controlp274-p276  Breakeven point p324

注意

 EOQ=order quantity which min inventory costs(Important e.g.) Absorption costing

p160

 Apportion service department cost

p165  The reciprocal method of apportionment

p167  The reciprocal（algebraic）method of apportionment

p168  Blanket absorption rates and department absorption rates

p174  Contribution and fixed cost (contribution>fixed cost ===profit) Job costing e.g.p242-p244  The production budget and direct labor budget e.g.p268.p270