, . , , .. , . . , .
, - . , . ( ).1
( )
. , 0() , . , S , . S , , . , , v S. v , S.
. G== (V, ), , . , ,
: , . , .
, S, . , , ( v) S.
. ||S|| = 1. 0, , ( ) S, . , 2 3 D.
. w , 5. D[w] v0 w, . , w S. v - . D[w], ( ) S. , w, . , w. ( , ) 8.
|
|
"" . , 25, 10, 5 1 63 . , 25 , 10 . , , , .
, . . "" . "" , . , . 1 , 5 11 15 , "" 11 , , .. . 5 .
"" , . "" , , , , .
, "" . , " " , . , , , . .
. , . ( , ). , , , . , . , .
|
|
, - .
"" , , . , , . , ; . " " , ( )
';
( ,
).
, , ; , , .
, , , . , , , - , .
. n , : v[1],v[2],... v[n]. , .
. ... , .
- n 3 .
.
: :=$xÎ (x - ).
( ):
:=;
:=false; :=false;
WHILE NOT AND NOT DO
IF
THEN :=true
ELSE IF
THEN :=
ELSE :=true
.
Ø :
¨ - , ;
¨ := , := .
Ø :
¨ ;
¨ , , ... ..
. - a,b,c. n n {a,b,c}, i- - , i- . - , .
, , . - , .. .
.
Ø , .
|
|
. a b , , - . , , ... .
- ( ) .
Ø , ( ) , - , . .
(BackTracking).
Ø :
r1<r2, r1<r3, r2 r3 - .
Ø - , .
Ø - .
Ø , , , .
.
Ø . , 3 . - 1- n-. i (i<=n) i {a,b,c}.
Ø i , , .. > (v[1]+v[2]+... v[n])/3.
Ø <=n , : - , 3 - a, b c.
:
(1 2) =
(1 2).
, , .. - ( <=n).
Ø - i , .
Ø . . , .
, :
a | a (c ; a). | a b ( ; a b). | ||
b | a (c ; a). | b c ( ; b c). | ||
c | a (c ; a). | : [a/b][c...]Þ[b/c] ( , , ). |
: c , c. , , - a b, b c.
|
|
, . , ... .
( ), :
a | a. | : [a/b][c...]Þ[b/c], c. | ||
b | ||||
c |
PROGRAM pp{PROGRAM\Prj6\Prj6.dpr}; CONST n=20;
VAR v: ARRAY[1..n] OF REAL; Yes{}: BOOLEAN;
Stek: ARRAY[1..n] OF a..c; iStek:0..n;
BEGIN {(v[1..n])};
{:=: 1- a}
Stek[1]:=a;iStek:=1; {}Yes:=false;
WHILE { }
NOT Yes AND (iStek>0)
DO { }
IF { }
THEN IF { } iStek=n
THEN {}Yes:=true
ELSE {:=, ,
.. a}
BEGIN iStek:=iStek+1; Stek[iStek]:=a END
ELSE BEGIN { }
WHILE (iStek>0) AND (Stek[iStek]=c)
DO iStek:=iStek-1;
IF { }(iStek>0)
THEN {:=, }
IF Stek[iStek]=a THEN Stek[iStek]:=b
ELSE {Stek[iStek]=b} Stek[iStek]:=c
END;
IF {} Yes THEN { }
ELSE WRITELN( ) END.
{ } , :
FUNCTION Dopustim: BOOLEAN;
VAR { }Sa,Sb,Sc: REAL; i: INTEGER;
{: REAL }
BEGIN Sa:=0;Sb:=0;Sc:=0; FOR i:=1 TO iStek DO BEGIN
IF Stek[iStek]=a THEN Sa:=Sa+v[i] ELSE
IF Stek[iStek]=b THEN Sb:=Sb+v[i] ELSE Sc:=Sc+v[i];
Dopustim:=(Sa<=C)AND(Sb<=C)AND(Sc<=C) END END
{ } Sa,Sb,Sc. : Sa,Sb,Sc .
, , , .
, . " ", , , . , . , , , . , , , , .