中科大算法導(dǎo)論第一二次和第四次作業(yè)答案PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1中科大算法導(dǎo)論第一二次和第四次作業(yè)中科大算法導(dǎo)論第一二次和第四次作業(yè)答案答案2.3-2改寫(xiě)MERGE過(guò)程，使之不使用哨兵元素，而是在一旦數(shù)組L或R中的所有元素都被復(fù)制回?cái)?shù)組A后，就立即停止，再將另一個(gè)數(shù)組中余下的元素復(fù)制回?cái)?shù)組A中。MERGE(A,p,q,r)1.n1q-p+12.n2 r-q3.create arrays L1.n1 and R1.n24.for i 1 to n15. do Li Ap+i-16.for j 1 to n27. do Rj Aq+j8.i 19.j 110.k p11.while(i=n1) and (j=n2)12. do if Li=Rj13.

2、do Ak=Li14. i+15. else do Ak=Rj16. j+17. k+18.while(i=n1)19. do Ak+=Li+20.while(j=n2)21. do Ak+=Rj+第1頁(yè)/共18頁(yè))lg()!(lg,!)2(2nnnnnnnn兩邊取對(duì)數(shù)可知：證明：由于第2頁(yè)/共18頁(yè)第3頁(yè)/共18頁(yè)).lg(2/(2)(nnOnnTnT的解為證明)lg()(),lg()()1c(lg) 1c ( -lg)2/lg()2/lg(2/2)2/(2)(2/lgT(n), 01lg1lg)(1)(T1nnnTnnOnTncnnncnnncnnnncnnTnTnncncncnnTnn下

3、面證所以，時(shí)當(dāng)成立對(duì)假設(shè)是唯一的邊界條件，時(shí)，證明：假設(shè)當(dāng)?shù)?頁(yè)/共18頁(yè)).lg()()lg()(,lg)(23/1c0 1) 1lg() 1lg()21 (, 3/1c) 1lg()21 () 1lg()1 (1lg1)1(lg, 2)11lg()1lg(0) 1lg()1 (1lg0lg21lg) 1(lg21lg) 1(21lg) 1(21lg212)2/lg(2/2)2/(2)()2/lg()2/()2/(TnnnTnnnTncnnTnnnccncnccncnccncncnncnnnnnnncncncnncnncnnnncncnnnncnnncnnncnnncnnTnTnncn所以時(shí)

4、，有，取則取則是遞增函數(shù)，取則成立。設(shè)第5頁(yè)/共18頁(yè)1)()2/()2/(1n)1 ()(nnnTnTnT如果如果第6頁(yè)/共18頁(yè)ncnnTccnnncnnncncnncnncncncnnTnnnnnncncnnncncnnncnncncncnnncnncncnncnnncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnOlg)(0)1(4),1(4,012)1lg(3)1(4(4)12)1(lg(2lg)(212)1lg(22lg)(1)11lg(1n)11lg(lg)1lg()()12(2)1lg(2)lg)1(lg(2lg)()12(2)lg(2)1lg(2)1

5、lg(2)(2lg2)lg(221)1lg(21)()2lg(2)21lg(21)()2lg(2)21lg(21)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)()lg(即有取，有取則有，有是遞增函數(shù)，取則成立設(shè)，即要證證明：先證第7頁(yè)/共18頁(yè)ncnnTccnnncnncncnnncncncnnTnnnnnnncncnnncncnnncncnncnncncnnncnncncnncnncnncncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnlg)(0)2) 1 () 1 (21, 0) 1lg(1, 3n)2)

6、1 ()1lg(1(2lg)() 1lg(2) 13(2lg)(1)11lg(, 2)11lg(lg) 1lg()() 1lg(2) 12(2)lg) 1(lg(2lg0)() 1lg(2) 12(2) 1lg(2lg2lg)() 1lg(2) 1lg(2) 12(2lg2)(2lg21) 1lg(212lg2lg2)()21lg(21)2lg(2)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)(),lg(，有取有取有是遞增函數(shù)，取則成立，設(shè)即要證再證第8頁(yè)/共18頁(yè)ncnnTncnnnncnncccnnncnnnccnnncncnncnn

7、cnnncnncnncncnnnncnncncnnnncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnOlg)(lg)()2lg(2)21lg(210)1(4),1(4,02)1lg(23)1(4(4)2)1lg(2(421)()1lg(2)(212)1lg(2)11lg(21)11lg(1n)11lg(0)(212)1lg(2)11lg(20lg)()2lg(2)21lg(21lg)()2lg(2)21lg(21)()2lg(2)21lg(21)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)()lg(即有取，有取

8、，有是遞增函數(shù)，取則成立設(shè)，即要證證明方法二：先證第9頁(yè)/共18頁(yè)ncnnTncnnnncnncccnnncnnccnncnncnncnncnnnncnncnncncnnnncnncncnnnncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnlg)(lg)()21lg(21)2lg(20)2) 1 () 1 (21, 0) 1lg(1, 3n)2) 1 ()1lg(1(2213) 1lg(2)()(212) 1lg(2)11lg(21)11lg(, 2)11lg(0)(212) 1lg(2)11lg(20lg)()21lg(21)2lg(2lg)()21lg(21)2lg(2)()21lg(21)2lg(2)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)(),lg(即，有取有取有是遞增函數(shù)，取則成立，設(shè)即要證再證第10頁(yè)/共18頁(yè)2/)(rpq第11頁(yè)/共18頁(yè)int Partition(int A, int p, int r) int x = Ar,i=p-1; int flag = 1; for (int j = p;j=Ai&flag0)/x=Ai時(shí)，flag大于0和小于0的數(shù)量約