算法设计与分析变治法学习教案

1、会计学1算法算法(sun f)设计与分析变治法设计与分析变治法第一页，共60页。2第2页/共60页第二页，共60页。3n for i=0 to n-2 don if Ai=Ai+1 return falsen return true整个过程整个过程时间时间(shjin)效效率是多少率是多少？第3页/共60页第三页，共60页。4第4页/共60页第四页，共60页。5第5页/共60页第五页，共60页。6第6页/共60页第六页，共60页。7第7页/共60页第七页，共60页。811 112 21121 122 2221 12 2n nn nmmmn nma xa xa xba xa xa xba xa

2、xa xb 第8页/共60页第八页，共60页。911121111212122222212000nnnnnnnnnnaaaaaaaaaaaaaaa 分消元过程和回代过程。消元过程将原方程组变为上三分消元过程和回代过程。消元过程将原方程组变为上三角角(snjio)方程组，回代过程得到方程组的解。方程组，回代过程得到方程组的解。第9页/共60页第九页，共60页。1005412321321321xxxxxxxxx 2200333011120333011120111511411122/ 232121232/ 13122rrrrrr1 0 1 123xxx，回代后得第10页/共60页第十页，共60页。11

3、第11页/共60页第十一页，共60页。12第12页/共60页第十二页，共60页。13第13页/共60页第十三页，共60页。1405412321321321xxxxxxxxx111114112A12121012001L200330112U系数系数(xsh)矩阵为矩阵为下三角下三角(snjio)矩阵矩阵L，由主对角线上的，由主对角线上的1以及在高斯消去过程中行的乘数构成以及在高斯消去过程中行的乘数构成上三角矩阵上三角矩阵(j zhn)U是消去的结果是消去的结果可观察出两可观察出两个矩阵的乘个矩阵的乘积积LU等于等于A第14页/共60页第十四页，共60页。15第15页/共60页第十五页，共60页。1

4、605 21 3221121211yyyyyy22 333 1 2332321xxxxxx与与LY=b, UX=Y对应对应(duyng)的方程组如下的方程组如下：易得：易得： (y1,y2,y3)=(1,3,-2), (x1,x2,x3)=(1,0,-1)第16页/共60页第十六页，共60页。17第17页/共60页第十七页，共60页。18111211112121222212221212100010001nnnnnnnnnnnnaaaxxxaaaxxxaaaxxx 逆矩阵(j zhn)的定义：求矩阵求矩阵(j zhn) A 的逆矩阵的逆矩阵(j zhn)，如何转换，如何转换第18页/共60页第十

5、八页，共60页。19100010001第19页/共60页第十九页，共60页。2011121322232123212221222311121332333133313231323311 22 3312 23 3121 32 1331 22 1321 12 3332 23 11aaaaaaaaaaaaaaaaaaaaaaaaaa aa a aa a aa a aa a aa a anjjjAsA1detdet第20页/共60页第二十页，共60页。21200330112111114112第21页/共60页第二十一页，共60页。22第22页/共60页第二十二页，共60页。23第23页/共60页第二十三页

6、，共60页。24第24页/共60页第二十四页，共60页。25第25页/共60页第二十五页，共60页。26第26页/共60页第二十六页，共60页。273277. 1)2(log4405. 1log22nhn第27页/共60页第二十七页，共60页。28第28页/共60页第二十八页，共60页。29第29页/共60页第二十九页，共60页。30第30页/共60页第三十页，共60页。31第31页/共60页第三十一页，共60页。321=124221hhn1) 1(log1) 1(log23nhn1=2 12 3 .2 32(1 3 .3 )31hhhn 第32页/共60页第三十二页，共60页。33第33页/

7、共60页第三十三页，共60页。34第34页/共60页第三十四页，共60页。35第35页/共60页第三十五页，共60页。36 10210i)1(log(22)(2)(2)(hiihiworstnnihihnC层的键第第36页/共60页第三十六页，共60页。37nN个规模问题的比较次数第37页/共60页第三十七页，共60页。38的。第38页/共60页第三十八页，共60页。39第39页/共60页第三十九页，共60页。40第40页/共60页第四十页，共60页。41第41页/共60页第四十一页，共60页。42第42页/共60页第四十二页，共60页。43第43页/共60页第四十三页，共60页。445) 1

8、) 3) 12( 532)(234xxxxxxxxxp第44页/共60页第四十四页，共60页。455) 1)3) 12( 532)(234xxxxxxxxxp当当x=3时，计算时，计算(j sun)p(x)系数系数2-131-5X=3223+(-1)=553+3=18518+1=55553+(-5)=160霍纳法则的有趣特性霍纳法则的有趣特性该算法在计算该算法在计算p(x)在某些点在某些点x0上的值所产生的中间数字恰好可以上的值所产生的中间数字恰好可以作为作为p(x)除以除以x-x0的商的系数，而算法的最后结果，除了等于的商的系数，而算法的最后结果，除了等于p(x0)以外，还等于这个以外，还等

9、于这个(zh ge)除法的余数。除法的余数。即，当即，当x0=3时时 p(x)=2x4-x3-3x2+x-5 除以除以x-3为为2x3+5x2+18x+55 和和 160第45页/共60页第四十五页，共60页。46第46页/共60页第四十六页，共60页。47第47页/共60页第四十七页，共60页。48第48页/共60页第四十八页，共60页。49第49页/共60页第四十九页，共60页。50第50页/共60页第五十页，共60页。51第51页/共60页第五十一页，共60页。52第52页/共60页第五十二页，共60页。53第53页/共60页第五十三页，共60页。54第54页/共60页第五十四页，共60

10、页。55第55页/共60页第五十五页，共60页。56第56页/共60页第五十六页，共60页。57第57页/共60页第五十七页，共60页。58(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1)(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)河西(h x)=(人,狼,羊,菜) 河东=(人,狼,羊,菜) 将将1010个顶点分别记为个顶点分别记为A1, A2, , A10 ,A1, A2, , A10 ,则渡河则渡河问题问题(wnt)(wnt)化为在该图中求一条从化为在该图中求一条从A1A1到到A10A10的路的路. . 从图中易得到两条路：从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A1 A6 A3 A7 A2 A8 A5 A10;A10; A1 A6 A3 A9 A4 A8 A5 A1 A6 A3 A9 A4 A8 A5 A10.A10.第58页/共60页第五十八页，共60页。59 （1）实例化简