SA130.doc

Size: px

Start display at page:

Download "SA130.doc"

瞳齐
7 years ago
Views:

1 SA-130

2 Index / / / 18 1 I~II 2 A~C 3 i~iv 4 ~ 9550 ( ) 19 13

3 5 () () () () () Hamilton () Network Path

4 Disconnected Connected () The Hamiltonian Circuit Problem

5 () Pick interior points boundary points b=2 A = b + i 1 A = b/2 + i I II III IV V IIIV IVV

6 atomic or primitive triangles b 1 b 2 i 1 i b 3 b= b 1 + b 2 2b i=i 1 + i 2 + b 3 2 b/2 + i 1 = (b 1 /2 + i 1-1) + (b 2 /2 + i 2 1 ) additivity 1 A = b/2 + i 1 b i

7 () ()

8 (1)(2) (3) () ( 7-3) 7-3 ()

9 k 2k ( ) (9-1) 1. 1 (10-1) (1) x (2) 2k 2k 2. 2 (10-2) () (10-3) ) 6 6 a ( b)

10 6 6 ( 10-7) 4 4 (c) S 1. c (11-1) 2. (0 ) c ,3) 3. S 5 4 ( S () (A) (B) AB

11 B B A BABAB A B B A 3 3 BABABABA A () k2 2k (B ) d B abc B d 90 a 90 b 90 c 90 d=a=b=c 3 6 (14-1)3 7 (14-2)

12 B ABABA A S ()

13 B 2n 2n or 2n+1 2n 2n+12n+1 B () YaBasic (X 1,X 2 ) X 1 X 2 (1,1) ( ) ( ) (1,4) ( )

14 (1,1) (1,2)

15 / = 3 (X1,X2) X1= 1 X2= 1 = 1 1 X= 1 1 Y= 2 = = / =3 (1,1) Another test? (y/n) (Brute force) () Brute force Hamilton circuit Hamilton circuit Hamilton Hamilton

16 Hamilton Hamilton Hamilton Brute force Hamilton circuit Hamilton circuit Hamilton Circuit ( ) Hamilton 15-8 Hamilton

17 Hamilton 15-9 Hamilton Hamilton circuit Pick m n/ /2-1 7 (simple polygon)pick Pick Hamilton Pick C(16,7)

18 Hamilton Log4 16 =9.632 => C(16,7)= / = P(point) V(vertical line) H(horizontal line) C(cubic) Hamilton circuit 3 () B () 2n 2n or 2n+1 2n 2n+12n+1 B () Hamilton circuit Hamilton Circuit

19 3. Hamilton circuit 4. m n/ =>log4 36 =72log2=21.672=> 22 C(36,17)= / = = (n+1) (n+1) C(n 2, n 2 / 2-1) n (1,1) Hamliton C(n 2, n 2 / 2-1) Hamilton Hamilton Hamilton Hamilton Hamilton Hamilton m n n n m n mn

20 Hamilton circuit Pick m n (m-1) (n-1) ( 4) 4 3 2n 2n+1 Pick 4 3/2+1=7 Hamilton circuit Pick 1.A B D 2.C S 3.AD Hamilton circuit Pick Hamilton circuit method

21 Hamilton circuit Hamilton n n (1,1) ( ) Hamilton Hamilton circuit Hamilton 2. Hamilton circuit 3. m n/ Hamilton circuit /2-1 (Pick ) 5 4 (n+1) (n+1) C(n 2, n 2 / 2-1)n Hamilton Hamilton Hamilton ( )

22 ( Donald W. Blackett Elementary Topology: A Combinatorial and Algebraic Approach 3. W.G. Chinn, N.E. Steenrod (59) 4. (75) John Mason, Leone Burton, Kaye Stacey (87) Thinking Mathematically 6. (88) 7. (87) ( Hamilton circuit Hamilton curcuit or Hamilton path Hamilton Hamilton Hamilton

23 Hamilton ( Harry

26 2 2

27 REM LABEL START CLEAR SCREEN 2 Input " / =" DD? " (X1,X2)" Input "X1=" X1 Input "X2=" X2 REM INPUT " = " P IF P>0 THEN FI DIM U(P):DIM V(P) FOR S=1 TO P PRINT "",S,"X=";:INPUT U(S) PRINT "",S,"Y=";:INPUT V(S) NEXT S TS$=TIME$:REM REM D(R) DIM D(DD^2-1-P) FOR R=1 TO DD^2-1-P STEP 1 D(R)=0 NEXT R REM A(X1,X2) DIM A(DD,DD) REM 0 LABEL MM FOR M1=1 TO DD FOR M2=1 TO DD A(M1,M2)=0 NEXT M2 NEXT M1 REM I1=X1:I2=X2

28 REM FOR S=1 TO P STEP 1 A(U(S),V(S))=1 NEXT S REM FOR R=1 to DD^2-1-P step 1 A(I1,I2)=1 IF D(R)=0 THEN I2=I2+1:FI:REM IF D(R)=1 THEN I2=I2-1:FI:REM IF D(R)=2 THEN I1=I1-1:FI:REM IF D(R)=3 THEN I1=I1+1:FI:REM IF (I1<1) or (I1>DD) THEN GOTO QQ:FI:REM (QQ) IF (I2<1) or (I2>DD) THEN GOTO QQ:FI:REM (QQ) IF A(I1,I2)=1 THEN GOTO QQ:FI:REM (QQ) NEXT R REM / LABEL QQ FOR S=R TO 1 STEP -1 D(S)=D(S)+1 IF D(1)=4 THEN GOTO EEND:FI IF D(S)=4 THEN D(S)=0 ELSE S=1:FI NEXT S GOTO MM REM For S=DD^2-1-P to 1 step -1 D(S)=D(S)+1 IF D(1)=4 THEN GOTO EEND:FI IF D(S)<>4 then S=1 ELSE D(S)=0:FI NEXT S GOTO MM REM K K=K+1 REM? "",K,"= "; FOR R=1 TO DD^2-1-P STEP 1? D(R); NEXT R

29 ? REM LABEL EEND TE$=TIME$:REM? " =",TS$? " =",TE$? " / =",DD,? " (",X1,",",X2,")", if K=0 then? " " ELSE? "",K,"":FI REM INPUT "Another test? (y/n)" A$ If (A$="Y") or (A$="y") then FI END K=0 GOTO START

30 REM LABEL BEGINNING CLEAR SCREEN DIM F(3):F(1)=1:F(2)=1:F(3)=1 3Hamilton INPUT " / " N FOR Y=1 TO (N-1)^2 F(1)=F(1)*Y FOR Y=1 TO ((N-2)^2)/2 F(2)=F(2)*Y FOR Y=1 TO ((N^2)/2)-1 F(3)=F(3)*Y G=F(1)/(F(2)*F(3)):? G IF (((N^2)/2)-1)<>INT(((N^2)/2)-1) THEN GOTO NOANS:FI DIM P(N+1,N+1),H(N+1,N+1),V(N+1,N+1),C(N,N),B(((N^2)/2)-1),W$(G) FOR Y=0 TO ((N^2)/2-1) B(Y)=Y FOR Y=1 TO G W$(G)="" REM FOR X=1 TO G FOR Y=0 TO N

31 FOR Z=O TO N P(Y,Z)=0:H(Y,Z)=0:V(Y,Z)=0:C(Y,Z)=0 NEXT Z FOR Y=1 TO ((N^2)/2-1) I=INT((B(Y)-1)/(N-1))+1 R=MOD((B(Y)-1),(N-1))+1 C(R,I)=1 REM Hamilton Circuit REM FOR Y=1 TO N-1 FOR Z=1 TO N H(Y,Z)=C(Y,Z)+C(Y,(Z-1)) V(Z,Y)=C(Z,Y)+C((Z-1),Y) IF H(Y,Z)=2 THEN H(Y,Z)=0:FI IF V(Z,Y)=2 THEN V(Z,Y)=0:FI NEXT Z FOR Y=1 TO N FOR Z=1 TO N P(Y,Z)=H(Y,Z)+H((Y-1),Z)+V(Y,Z)+V(Y,(Z-1)) IF P(Y,Z)<>2 THEN GOTO NEWBLOCKS:FI NEXT Z REM I=INT((B(1)-1)/(N-1))+1 R=MOD((B(1)-1),(N-1))+1 C(R,I)=8:A=1 LABEL COLORING:AA=0 FOR Y=1 TO N-1 FOR Z=1 TO N-1 IF (C(Y,Z)=0) OR (C(Y,Z)=8) THEN GOTO NEXTBLOCK:FI

32 CR=C(Y-1,Z)+C(Y,Z-1)+C(Y+1,Z)+C(Y,Z+1) IF CR>=8 THEN C(Y,Z)=8:A=A+1:AA=AA+1:FI LABEL NEXTBLOCK NEXT Z IF AA<>0 THEN GOTO COLORING:FI REM IF A=((N^2)/2)-1 THEN S=S+1:R=S W$(R)="" FOR Y=1 TO N-1 FOR Z=1 TO N-1 W$(R)=W$(R)+STR$(C(Z,Y)) NEXT Z FI GOSUB PRINTING LABEL NEWBLOCKS Y=((N^2)/2)-1 B(Y)=B(Y)+1 LABEL ROUND IF B(Y)=((N^2)/2)-(2*N)+3+Y THEN FI B(Y-1)=B(Y-1)+1 FOR Z=Y TO ((N^2)/2)-1 STEP 1 B(Z)=B(Z-1)+1 NEXT Z Y=Y-1 IF Y=0 THEN B(Y)=-5:FI GOTO ROUND NEXT X LABEL NOANS REM? " ",S," " LABEL RESULT

33 INPUT "?(0= ) " R IF R<>0 THEN GOSUB PRINTING ELSE GOTO NEWONE:FI GOTO RESULT REM LABEL NEWONE INPUT "? (y/n)" K$ IF K$="Y" OR K$="y" THEN FI S=0 GOTO BEGINNING END LABEL PRINTING FOR Y=1 TO N-1 FOR Z=1 TO N-1 B$=MID$(W$(R),((Y-1)*(N-1)+Z),1) IF B$="0" THEN? " "; ELSE? B$;:FI NEXT Z?? RETURN

34 REM LABEL BEGINNING CLEAR SCREEN DIM F(3):F(1)=1:F(2)=1:F(3)=1 4Hamilton INPUT " = " M INPUT " = " N FOR Y=1 TO (M-1)*(N-1) F(1)=F(1)*Y FOR Y=1 TO ((M-2)*(N-2))/2 F(2)=F(2)*Y FOR Y=1 TO ((N*M)/2)-1 F(3)=F(3)*Y G=F(1)/(F(2)*F(3))? " ",((N*M)/2)-1," "? "",G," " IF (((N*M)/2)-1)<>INT(((N*M)/2)-1) THEN GOTO NOANS:FI H=INT(SQR(G)*1.1) DIM P(M+1,N+1),H(M+1,N+1),V(M+1,N+1),C(M+1,N+1),B(((N*M)/2)-1),W$(H) FOR Y=0 TO ((N*M)/2)-1 B(Y)=Y REM FOR X=1 TO G FOR Y=0 TO M+1 FOR Z=0 TO N+1

35 P(Y,Z)=0:H(Y,Z)=0:V(Y,Z)=0:C(Y,Z)=0 NEXT Z FOR Y=1 TO (((N*M)/2)-1) I=INT((B(Y)-1)/(M-1))+1 R=MOD((B(Y)-1),(M-1))+1 C(R,I)=1 REM Hamilton Circuit REM FOR Y=1 TO M-1 FOR Z=1 TO N H(Y,Z)=C(Y,Z)+C(Y,(Z-1)) IF H(Y,Z)=2 THEN H(Y,Z)=0:FI NEXT Z FOR Y=1 TO N-1 FOR Z=1 TO M V(Z,Y)=C(Z,Y)+C((Z-1),Y) IF V(Z,Y)=2 THEN V(Z,Y)=0:FI NEXT Z FOR Y=1 TO M FOR Z=1 TO N P(Y,Z)=H(Y,Z)+H((Y-1),Z)+V(Y,Z)+V(Y,(Z-1)) IF P(Y,Z)<>2 THEN GOTO NEWBLOCKS:FI NEXT Z REM I=INT((B(1)-1)/(M-1))+1 R=MOD((B(1)-1),(M-1))+1

36 C(R,I)=8:A=1 LABEL COLORING:AA=0 FOR Y=1 TO M-1 FOR Z=1 TO N-1 IF (C(Y,Z)=0) OR (C(Y,Z)=8) THEN GOTO NEXTBLOCK:FI CR=C(Y-1,Z)+C(Y,Z-1)+C(Y+1,Z)+C(Y,Z+1) IF CR>=8 THEN C(Y,Z)=8:A=A+1:AA=AA+1:FI LABEL NEXTBLOCK NEXT Z IF AA<>0 THEN GOTO COLORING:FI REM IF A=((N*M)/2)-1 THEN S=S+1:R=S W$(R)="" FOR Y=1 TO N-1 FOR Z=1 TO M-1 W$(R)=W$(R)+STR$(C(Z,Y)) NEXT Z FI GOSUB PRINTING LABEL NEWBLOCKS Y=((M*N)/2)-1 B(Y)=B(Y)+1 LABEL ROUND IF B(Y)=((N*M)/2)-(M+N)+3+Y THEN B(Y-1)=B(Y-1)+1 FOR Z=Y TO ((N*M)/2)-1 STEP 1 B(Z)=B(Z-1)+1 NEXT Z Y=Y-1 IF Y=0 THEN B(Y)=-5:FI GOTO ROUND FI

37 NEXT X LABEL NOANS REM? " ",((N*M)/2)-1," "? "",G," "? " ",S," " LABEL RESULT INPUT "?(0= ) " R IF R<>0 THEN GOSUB PRINTING ELSE GOTO NEWONE:FI GOTO RESULT REM LABEL NEWONE INPUT "? (y/n)" K$ IF K$="Y" OR K$="y" THEN FI S=0 GOTO BEGINNING END LABEL PRINTING FOR Y=1 TO N-1 FOR Z=1 TO M-1 B$=MID$(W$(R),((Y-1)*(M-1)+Z),1) IF B$="0" THEN? " "; ELSE? B$;:FI NEXT Z?? RETURN

广西师范学院（下）

广西师范学院（下） 3888.00 ( 16.00 ) ...1 ()...1...4... 11...14...15...17...32...43...44...46...47...58...59...60...62 I II...63...64...65...69...72...73...74...76...81...83...84 ( )...85...90 ( )...96... 102... 107...111...