B133点燃关系与计算程序课件.ppt

1、Copyright by 2010Programming Languages Lab.Copyright by 2010Programming Languages Lab.341 10 v:1.2.3.4.Copyright by 2010Programming Languages Lab.34210 1 v 10.1 (recurrence relation)a0,a1,an an a0,a1,a2,an-1 .,n .1.5.2.3 .5,8,11,14,a1,a2,1.a1=5 2.an=an-1+3,n2 an=an-1+3 .Copyright by 2010Programming

2、Languages Lab.34310 1 n (n-1)an an-1(dependent).an an-1 1(first-order).1 .,.(initial condition).(G.Fibonacci).1202 .Copyright by 2010Programming Languages Lab.34410 1 10.1 .1 .(,.)R(n)n .R(n)=R(n-1)+R(n-2).,R(0)=1(1)R(1)=1(2 )R(2)=2(1;1)R(3)=3(1;2)R(n),1,1,2,3,5,8,13,21,34,55,.Copyright by 2010Progr

3、amming Languages Lab.34510 1 10.2 1883 E.Lucas,(Hanoi Tower Problem).(Vietnam)(Hanoi)(Benares)(Dome).,64 .,.(1).(2).(move).,1.,.Copyright by 2010Programming Languages Lab.34610 1 3.A AB B(1)(1)A AB B(2)(2)B B(3)(3)Copyright by 2010Programming Languages Lab.34710 1 3 3 7 .Copyright by 2010Programming

4、 Languages Lab.34810 1 n .n P(n).,p(1)=1,P(2)=3,P(3)=7 .P(n)P(n-1).,.Copyright by 2010Programming Languages Lab.34910 1 (n-1)(n-1)A An n(n-1)(n-1)B B(1)(1)P(n-1)P(n-1)A AB B(2)(2)Copyright by 2010Programming Languages Lab.35010 1 v vv vvA A(n-1)(n-1)(3)(3)(n-1)(n-1)B BP(n-1)P(n-1)(4)(4)n nB Bn nA AP

5、(n)P(n)P(n)=2p(n-1)+1P(n)=2p(n-1)+1Copyright by 2010Programming Languages Lab.35110 1 ,n P(n)=2 P(n-1)+1 .P(1)=1 P(2)=2 P(1)+1=2+1=3 P(3)=2 P(2)+1=2 x 3+1=4+2+1=7 P(4)=2 P(3)+1=2 x 7+1=8+4+2+1=15 P(n)=1+2+22+2n-1 =(2n-1)/(2-1)=2n-1().n=64 (,.)P(64)=264-1=18,446,744,073,709,551,615 .1844(),1 1 ,5000

6、.Copyright by 2010Programming Languages Lab.35210 1 endif1),1(movebeginthen1if0Begin),(hanoiAlgorithmcctofromnccnbytofromEndendelse),1,(hanoi1),(move),1,(hanoibeginelsecnfromtobycctofromncntobyfromCopyright by 2010Programming Languages Lab.35310.2 v (algorithm).v 10 2 .,5 .(1)(input):.(2)(output):.(

7、3)(finiteness):.(4)(definiteness):(一義的).(5)(effectiveness):.(procedure).Copyright by 2010Programming Languages Lab.35410.2 10.3】,(1).(2)5.(3).(4)6.(5)show.(6).v 10 3 ,(pseudo code),.Copyright by 2010Programming Languages Lab.35510.2 v 7 :(1)IF(condition)THEN S1 ELSE S2 (condition)S1 ,S2 .【10.4】X 1.I

8、F(X13000)THEN a.YX+0.02(X-13000)2.ELSE b.YX+0.3X X 13000 Y X+0.02(X-13000).X 13000 Y X+0.3X.Copyright by 2010Programming Languages Lab.35610.2 (2)WHILE(condition)S WHILE(while-loop)S .【10.5】N 1.X0 2.Y0 3.WHILE(XY)a.XX+1 b.YY+X 4.YY/2 3 a,b (X=N)4 .Y=(1+2+N)/2 Copyright by 2010Programming Languages L

9、ab.35710.2 (3)UNTIL(condition)S WHILE .【10.6】10.5 UNTIL .1.X0 2.Y0 3.UNTIL(XN)a.XX+1 b.YY+1 4.YY/2 3 a,b (X=N)4 .Y=(1+2+N)/2 Copyright by 2010Programming Languages Lab.35810.2 (4)FOR KVAR=M THRU N BY L S FOR (FORTRAN DO ),KVAR=M L KVAR=N S(BY L L=1 ).【10.7】FOR KVAR=2 THRU 10 BY 2 XX+KVAR 3 (KVAR=2,5

10、,8)X 0 X FOR .X=0+2+5+8=15 Copyright by 2010Programming Languages Lab.35910.2 (5):CALL NAME(A,B,;X,Y,):SUBROUTINE NAME(A,B,;X,Y,)RETURN CALL NAME RETURN .A,B,X,Y,.【10.8】:CALL SQR(N;X):SUBROUTINE SQR(N;X)1.XN 2.Y1 3.WHILE(YN)a.XX+N b.YY+1 4.RETURN X=X2 .Copyright by 2010Programming Languages Lab.3601

11、0.2 (6)FUNCTION NAME(A,B,)RETURN(Y)CALL FUNCTION .A,B,Y .【10.9】10.8 FUNCTION .FUNCTION SQR(N)1.XN 2.Y1 3.WHILE(Y N)a.XX+N b.YY+1 4.RETURN(X)SQR(N)(function name)SQR(N)RETURN.Copyright by 2010Programming Languages Lab.36110.2 (7)AN(array A)A .1,N A1,A2,AN .【10.10】X1,XN N .1.MAXX1 2.FOR I=2 THRU N a.I

12、F(MAXXI)THEN b.MAXXI N MAX.Copyright by 2010Programming Languages Lab.36210.3 v :.v :5 (,(),(simplicity),(optimality).v (complexity):n f(n)f(n)(time complexity),f(n)f(n)(space complexity).,.,.v f(n).Copyright by 2010Programming Languages Lab.36310.3 v 10 4 nn0 n|f(n)|c|g(n)|c n0 f(n)=|g(n)|.f(n)=|g(

13、n)|“f(n)g(n)”“f(n)big-Oh of g(n)”.v 10 1 A(n)=amnm+a1n+a0 A(n)=(nm).|A(n)|=|amnm+a1n+a0|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|a0|)nm,n1 c=(|am|+|a0|),n0=1|A(n)|c|nm|A(n)=(nm)Copyright by 2010Programming Languages Lab.36410.3 10.12】.(1)cR (2)=(n2)(3)=(n3)v O(n)O(n2).O(n)1010n O(n2)n2,n1010

14、 .n O(n2)O(n)O(n)O(n2).1()nicn 1nii21niiCopyright by 2010Programming Languages Lab.36510.3 v .(1)O(1):()O(1).(2)O(log n):()n kR+,k log n .(3)O(n):()(4)O(n log n):(n log n)(5)O(n2):(2(quadratic)(6)O(n3):(3(cubic)(7)O(2n):(exponential)Copyright by 2010Programming Languages Lab.36610.3 v O(1)O(log n)O(

15、n)O(n log n)O(n2)O(n3)0 then x1 -b+sqrtb2-4ac/2a;x2 -b-sqrtb2-4ac/2a;x1 x2.else if b2-4ac=0 then x -b/2a;x.else .Copyright by 2010Programming Languages Lab.37110 4 v 10.4.2(Eratosthenes,BC 273?BC 192?),(),().n p .v 10.3 1:1 p 2.2:p n p .3:p p.4:2.Copyright by 2010Programming Languages Lab.37210 4 v

16、10.4.3 :1 1 .,.v 10.4 begin Input N D 1 while D sqrt(N)do if mod(N,D)=0 then(/*mod(N,D)N D .*/)Output D and N/D D D+1 end end Copyright by 2010Programming Languages Lab.37310 4 v .m .m true,m false.v 10.5 :m,:m true,m false procedure is-prim(m)for i:=2 to m-1 do if m mod i=0 then/I divides m return(

17、false)return(true)end is-prime Copyright by 2010Programming Languages Lab.37410 4 v 10.4.4.:(common division).a,b,k k k|a k|b k a b .k k k a b (greatest common division;GCD)k=GCD(a,b).GCD?,Euclidean .Copyright by 2010Programming Languages Lab.37510 4 v 10 6Find the GCD of Two Integers Procedure Find

18、-GCD(a,b;var GCD);(/*.*/)begin 1.while b0 do begin(/*b=0 GCD=a.*/)2.q:=a DIV b;3.r:=a MOD b;(/*a=bq+r q r.,0rb*/)4.a:=b;5.b:=r;(/*b a,r b */)end;6.GCD:=a end;Copyright by 2010Programming Languages Lab.37610 4 v a b 10 6 .a=bq1+r1 b=r1q2+r2.r1=r2q3+r3(0 r3r2)r2=r3q4+r4(0 r4r3).rk-1=rkqk+1+rk+1(0 rk+1

19、2),1,1,2,3,5,8,.FUNCTION FIB(N)1.IF(N=1)THEN a.A1 2.ELSE a.IF(N=2)THEN A1 b.ELSE AFIB(N-1)+FIB(N-2)3.RETURN(A)END OF FUNCTION FIB Copyright by 2010Programming Languages Lab.38610.4 10.21 5 .(main program)5 FIB(5)(call).FUNCTION FUNCTION FIB(5).,N=5 .1 N 1 2 2.b .,FIB(4)+FIB(3).FIB(4)+FIB(3)FIB(4)FUN

20、CTION FIB(N).FIB(5)3 .Copyright by 2010Programming Languages Lab.38710.4 FIB(4).1 N 1 2.b .,FIB(3)+FIB(2).FIB(3)FUNCTION FIB(N).1 N 1 2.b .,FIB(2)+FIB(1).FIB(2)FUNCTION FIB(2).2.a FIB(2)1 FIB(2)+FIB(1)FIB(2).FIB(2)FIB(2).FIB(2)+FIB(1)(return address).FIB(2)FIB(1).FUNCTION FIB(1).1 FIB(1)1 .FIB(2)+FI

21、B(1).Copyright by 2010Programming Languages Lab.38810 4 FIB(2)+FIB(1)FIB(3)+FIB(2).FIB(3)FIB(2)FUNCTION FIB(2).2.a FIB(2)1 .FIB(3)+FIB(2)FIB(4)FIB(4)+FIB(3).FIB(3)FUNCTION FIB(3)2.b 3 FIB(5)5.Copyright by 2010Programming Languages Lab.38910.4 10.22】1 n .End)1(else1then1ifBegin)(sumAlgorithmnsumnsumsumnnCopyright by 2010Programming Languages Lab.39010 4 v (iteration).(Sharp.J.A.),.,.