//JOB(ERCC07,STEPHENS,T=200,L=10000) //OPTIONS(QUOTES,OPT) //ALGOL 'COMMENT' *************** * * * ALGG054 * * * *************** ; 'BEGIN' 'COMMENT' !***BG4621B***BEN4ASUE**** ; 'BEGIN' 'INTEGER' I,J,M,N,I2,J2,I1,J1,P,H,H1,H2,X1,B,C1,R,D,E,ALPHA,BE TA, GAMMA,A,SIGMA,NETA,Q,S,T,TOR,VV,W,PI; I1:=0;J1:=0; H1:=1; 'COMMENT' FIX UP; M := READ; N := READ; 'BEGIN' 'INTEGER' 'ARRAY' V,EE,DD[0:N],U,SS[0:M],C[0:M*N], AA,F[1:2*M+N-2],BB,G,XXX[1:M-1],X,K,LL,JJ,II[1:M+N-1]; 'COMMENT' READING IN THE DATA; 'FOR' I := 1 'STEP' 1 'UNTIL' M 'DO' SS[I] := READ; 'FOR' J := 1 'STEP' 1 'UNTIL' N 'DO' DD[J] := READ; 'FOR' I := 1 'STEP' 1 'UNTIL' M*N 'DO' C[I] := READ; 'COMMENT' FORMING I.B.F.S.; P := N; VV := N-1; W :=M+N-1; TOR := E := 1; A := U[E] := U[0] := 0; 'FOR' TOR:=1 'STEP' 1 'UNTIL' N 'DO' EE[TOR]:=0; L1: NETA := (E-1)*N+1; TOR:=1; C[0]:=10000; L2: 'IF' C[NETA]N 'THEN' T:=R-N 'ELSE' T:=0; R:=P; 'IF' E=M 'THEN' 'GOTO' L6; 'IF' SS[E] <= DD[D] 'THEN' 'BEGIN' GAMMA:=P; 'GOTO' L7; 'END'; L6: LL[Q]:=P-N; GAMMA:=Q:=P; 'GOTO' L8; 'COMMENT' SEARCH FOR NEXT ELEMENT TO ENTER BASIS; L13: I2 := C1 := A := 0; 'FOR' R := 1 'STEP' 1 'UNTIL' M 'DO' 'BEGIN' I2 := I2+1; 'IF' I2>M 'THEN' I2 := 1 'ELSE' E := I2; 'FOR' D := 1 'STEP' 1 'UNTIL' N 'DO' 'IF' U[E]+V[D]-C[D]>C1 'THEN' 'BEGIN' C1 := U[E]+V[D]-C[D]; A := 1; J2 := D; 'END'; 'IF' A = 1 'THEN' 'GOTO' L15; 'END'; NEWLINES(1); WRITETEXT('('OPTIMUM SOLN IS ')'); 'COMMENT' PRINTING OF INTERMEDIATE RESULTS; L15: NEWLINES(1); WRITETEXT('('BASIS%TABLE%IS%')'); 'FOR' GAMMA := 1 'STEP' 1 'UNTIL' M+N-1 'DO' 'BEGIN' NEWLINES(1); PRINT(II[GAMMA],4,0); PRINT(K[GAMMA],4,0); PRINT(JJ[GAMMA],4,0); PRINT(X[GAMMA],4,0); PRINT(LL[GAMMA],4,0); 'END'; 'IF' A =0 'THEN' 'GOTO' FINISH; NEWLINES(1); WRITETEXT('('U,S')'); SPACES(1); WRITETEXT('('*AND*V,S*ARE')'); 'FOR' I := 1 'STEP' 1 'UNTIL' M 'DO' 'BEGIN' PRINT(U[I],4,0); NEWLINES(1); 'END'; 'FOR' J := 1 'STEP' 1 'UNTIL' N 'DO' 'BEGIN' PRINT(V[J],4,0); NEWLINES(1); 'END'; NEWLINES(1); WRITETEXT('('NEW%ELEMENT%IS')'); NEWLINES(1); PRINT(I2,4,0); PRINT(J2,4,0); 'COMMENT' FINDING LOOP INCLUDING NEW ELEMENT; ALPHA := BETA := 1; X1 := 10000; A := 0; H := GAMMA := J2; L16: 'IF' LL[GAMMA] # 0 'THEN' 'GOTO' L22; L17: 'IF' GAMMA=K[GAMMA] 'THEN' 'GOTO' L19; L18: X1 := 'IF' X[GAMMA]N 'THEN' 'GOTO' L25; 'IF' LL[GAMMA]=0 'THEN' 'GOTO' L24; L25: XXX[BETA] := X1; BB[BETA] := 0; G[BETA] := F[ALPHA] := GAMMA; AA[ALPHA] := 1; BETA := BETA+1; ALPHA := ALPHA+1; 'GOTO' L24; 'END'; 'IF' H>N 'THEN' 'GOTO' L26; 'IF' LL[GAMMA]=0 'THEN' 'GOTO' L19; L26: AA[ALPHA] := 0; F[ALPHA] := GAMMA; ALPHA := ALPHA+1; 'GOTO' L20; 'COMMENT' CHANGING VALUE OF LOOP ELEMENTS; L27: A := B := 0; L28: ALPHA := ALPHA-1; 'IF' ALPHA = 0 'THEN' 'GOTO' L32; GAMMA := F[ALPHA]; 'IF' AA[ALPHA] # 0 'THEN' 'GOTO' L30; L29: 'IF' B=0 'THEN' 'BEGIN' B := 1; X[GAMMA] := X[GAMMA]-X1; 'IF' A=1 'THEN' 'GOTO' L28; 'IF' X[GAMMA]=0 'THEN' 'BEGIN' I1 := II[GAMMA]; J1 := JJ[GAMMA]; H1 := GAMMA; A := 1; 'END'; 'GOTO' L28; 'END'; B := 0; X[GAMMA] := X[GAMMA]+X1; 'GOTO' L28; L30: 'IF' AA[ALPHA] # 2 'THEN' 'GOTO' L28; L31: ALPHA := ALPHA-1; 'IF' AA[ALPHA]=1 'THEN' 'BEGIN' 'IF' F[ALPHA]=GAMMA 'THEN' 'GOTO' L29; 'END'; 'GOTO' L31; 'COMMENT' MODIFYING BASIS TABLE; L32: H2 := SIGMA := GAMMA := H1 ; 'IF' J1=J2 'THEN' 'BEGIN' A:= 0; 'GOTO' L40; 'END'; 'IF' H1 <= N 'THEN' 'BEGIN' A := 1; 'GOTO' L40; 'END'; PI := H1; L33: 'IF' LL[PI]=0 'THEN' 'BEGIN' PI := J1; 'GOTO' L33 ; 'END'; PI := LL[PI]+N; 'IF' P # H1 'THEN' 'GOTO' L33; LL[PI] := LL[GAMMA]; B := 0; L34: PI := J2 ;LL[SIGMA] := LL[PI]; JJ[SIGMA] := J2; LL[PI] := SIGMA-N; 'IF' B=1 'THEN' 'GOTO' L36; 'IF' I1 # I2 'THEN' 'BEGIN' A:=0; 'GOTO' L40; 'END'; L35: X[SIGMA] := X1; 'GOTO' L43; L36: 'IF' II[SIGMA]=I2 'THEN' 'BEGIN' PI := H1; 'GOTO' L39; 'END'; 'IF' I1=I2 'THEN' 'BEGIN' 'IF' P=GAMMA 'THEN' PI := H2 'ELSE' PI :=P; 'GOTO' L39; 'END'; L37: PI := 1; L38: 'IF' II[PI]=I2 'THEN' 'GOTO' L39; PI := PI+1; 'GOTO' L38; L39: II[SIGMA] := I2; K[SIGMA] := K[PI]; K[PI] := SIGMA; 'GOTO' L35; L40: PI := H1; L41: 'IF' K[PI] # H1 'THEN' 'BEGIN' PI:=K[PI]; 'GOTO' L41; 'END'; K[PI] := K[GAMMA]; 'IF' A=0 'THEN' 'GOTO' L37; PI := H2 :=SIGMA := LL[GAMMA]+N; L42: 'IF' K[PI] # H2 'THEN' 'BEGIN' PI:= K[PI]; 'GOTO' L42; 'END'; K[PI] := GAMMA; P := K[GAMMA]; II[GAMMA] := II[SIGMA]; K[GAMMA] := K[SIGMA]; LL[GAMMA] := LL[SIGMA]; X[GAMMA] := X[SIGMA]; B := 1; 'GOTO' L34; 'COMMENT' COMPUTING DUAL VARIABLES; L43: BETA := 1; GAMMA := H2; E := I2; U[E] := U[E]-C1; 'IF' K[GAMMA]=GAMMA 'THEN' 'GOTO' L13; L44: H := GAMMA; L45: GAMMA := K[GAMMA]; D := JJ[GAMMA]; V[D] := V[D]+C1; 'IF' K[GAMMA] # H 'THEN' 'GOTO' L52; 'IF' GAMMA <= N 'THEN' 'BEGIN' 'IF' LL[GAMMA] # 0 'THEN' 'GOTO' L51; 'END'; L46: H := GAMMA; L47: GAMMA := 'IF' LL[GAMMA]=0 'THEN' LL[GAMMA]+H 'ELSE' JJ[GAMMA] ; E := II[GAMMA]; U[E] := U[E]-C1; 'IF' H <= N 'THEN' 'GOTO' L49; 'IF' LL[GAMMA] # H-N 'THEN' 'GOTO' L50; L48: 'IF' GAMMA # K[GAMMA] 'THEN' 'GOTO' L44; 'GOTO' L51; L49: 'IF' LL[GAMMA]=0 'THEN' 'GOTO' L48; L50: 'IF' GAMMA=K[GAMMA] 'THEN' 'BEGIN' BB[BETA] := 1; G[BETA] := GAMMA; BETA := BETA+1; 'END'; 'GOTO' L47; L51: BETA := BETA-1; 'IF' B=0 'THEN' 'GOTO' L13; 'IF' BETA < 1 'THEN' 'BEGIN' A:=0; 'GOTO' L15 'END'; GAMMA := G[BETA]; 'IF' BB[BETA]=1 'THEN' 'GOTO' L44; 'GOTO' L46; L52: 'IF' GAMMA>N 'THEN' 'GOTO' L53; 'IF' LL[GAMMA]=0 'THEN' 'GOTO' L45; L53: BB[BETA] := 0; G[BETA] := GAMMA; BETA := BETA+1; 'GOTO' L45; FINISH: 'END'; 'END'; 'END' //RUN 3; 4; 20;60;40; 30;20;40;30; 5;8;3;6; 4;9;8;11; 6;2;4;5;