Yeaiaiou oai?ee a?aoia.
A?ao – niaieoiiinoue oi/ae e eeiee, a eioi?ie eaaeaeay eeiey niaaeeiyao
aeaa oi/ee. Oi/ee iacuaathony aa?oeiaie, eee oceaie, a?aoa, eeiee –
?aa?aie a?aoa. Anee ?aa?i niaaeeiyo aeaa aa?oeiu, oi aiai?yo, /oi iii ei
eioeeaeaioii; aa?oeiu, niaaeeiaiiua ?aa?ii iacuaathony niaaeiuie. Aeaa
aa?oeiu, niaaeeiaiiua ?aa?ii, iiaoo niaiaaeaoue; oaeia ?aa?i
iacuaaaony iaoeae. *enei ?aaa?, eioeeaeaioiuo aa?oeia, iacuaaaony
noaiaiueth aa?oeiu. Anee aeaa ?aa?a eioeeaeaioiu iaeiie e oie aea
ia?a aa?oei, iie iacuaathony e?aoiuie; a?ao, niaea?aeauee e?aoiua
?aa?a, iacuaaaony ioeueoea?aoii.
?aa?i, niaaeeiythuaa aeaa aa?oeiu, iiaeao eiaoue iai?aaeaiea io iaeiie
aa?oeiu e ae?oaie; a yoii neo/aa iii iacuaaaony iai?aaeaiiui, eee
i?eaioe?iaaiiui, e ecia?aaeaaony no?aeeie. A?ao, a eioi?ii ana ?aa?a
i?eaioe?iaaiiua, iacuaaaony i?eaioe?iaaiiui a?aoii (i?a?aoii); ?aa?a
i?a?aoa /anoi iacuaatho aeoaaie. Aeoae eiaiothony e?aoiuie, anee iie
ia oieueei eiatho iauea aa?oeiu, ii e niaiaaeatho ii iai?aaeaieth.
Eiiaaea ioaeii ?anniao?eaaoue ia aanue a?ao, a aai /anoue (/anoue aa?oei
e /anoue ?aaa?). *anoue aa?oei e ana eioeeaeaioiua ei ?aa?a iacuaathony
iiaea?aoii; ana aa?oeiu e /anoue eioeeaeaioiuo ei ?aaa? iacuaathony
noa?aoii. Oeeeeii iacuaaaony caieiooay oeaiue aa?oei. Aea?aaii
iacuaaaony a?ao aac oeeeeia. Inoiaiui aea?aaii iacuaaaony naycaiiue
noa?ao a?aoa, ia eiathuee oeeeeia.
A?ao iaeiicia/ii caaeai, anee caaeaiu iiiaeanoai aai aa?oei,
iiiaeanoai ?aaa? e oeacaiu ana eioeeaeaioiinoe (o.a. oeacaii, eaeea
aa?oeiu eaeeie ?aa?aie niaaeeiaiu). Iaeaieaa iaaeyaeii a?ao caaeaaony
?enoieii; iaeiaei ia ana aeaoaee ?enoiea iaeeiaeiai aaaeiu; a
/anoiinoe, ianouanoaaiiu aaiiao?e/aneea naienoaa ?aaa? (aeeeiia,
e?eaecia e o.ae.) e acaeiiia ?aniieiaeaiea aa?oei ia ieineinoe.
Aeey iai?eaioe?iaaiiiai ?aa?a ii?yaeie, a eioi?ii oeacaiiu
niaaeeiyaiua ei aa?oeiu, ia aaaeai. Aeey i?eaioe?iaaiiiai ?aa?a
aaaeii: ia?aie oeacuaaaony aa?oeia, ec eioi?ie auoiaeeo ?aa?i.
Ia?o?oo, eee iooue – yoi iineaaeiaaoaeueiinoue ?aaa? a
iai?eaioe?iaaiiii a?aoa, a eioi?ii eiiaoe eaaeaeiai ?aa?a niaiaaeaao n
ia/aeii neaaeothuaai ?aa?a. *enei ?aaa? ia?o?ooa iacuaaaony aai
aeeeiiie.
A?aou oe?iei eniieuecothony eae a naiie iaoaiaoeea, oae e a aa
i?eeiaeaieyo. Iie i?eiaiythony i?e iino?iaiee ?acee/iuo iaoaiaoe/aneeo
iiaeaeae: eeiee yeaeo?iia?aaea/e, naoae aaoiaei?ia, eeiee aicaeooiuo
niiauaiee e i?.
Caaea/a ninoieo a oii, iaeoe iooue ec aa?oeiu A a aa?oeio B. Aoaeai
caaeaaaoue a?ao iao?eoeae niaaeiinoe, o.a. eaaae?aoiie oaaeeoeae NxN,
a eioi?ie ia ia?ana/aiee i-e no?iee e j-ai noieaoea cia/aiea TRUE, anee
i e j niaaeeiaiu ?aa?ii, e FALSE a i?ioeaiii neo/aa.
Iiene a oe?eio.
Iiaeiaii oiio eae, niaeanii i?eioeeio Atheaaina, eaaeaeay oi/ea
aieiiaiai o?iioa yaeyaony enoi/ieeii aoi?e/iie aieiu, iu, ioi?aaeyynue
ec caaeaiiie aa?oeiu A, iinauaai ana niaaeiua n iae aa?oeiu (o.a.
aa?oeiu, a eioi?ua aaaeoo no?aeee ec A). Eaaeaeay iinauaiiay aa?oeia
noaiiaeony enoi/ieeii iiaie aieiu e o.ae. I?e yoii iaiaoiaeeii
iicaaioeoueny i oii, /oiau ia aa?ioony a oo aa?oeio, a eioi?ie oaea
auee.
Aeey ?aaeecaoeee aeai?eoia iiiaaeiayony:
iao?eoea m[1..n, 1..n] – iao?eoea niaaeiinoe a?aoa;
aniiiiaaoaeueiue iannea queue[1..n], a eioi?ii aoaeao
oi?ie?iaaoueny i/a?aaeue, o.a. oei aeaiiuo ia?aue aioae – ia?aue auoae
(FIFO). ?acia? aai aeinoaoi/ai, oae eae iu ia iinauaai aa?oeiu
aeaaaeaeu. N ianneaii queue naycaiu aeaa ia?aiaiiua – head e tail. A
ia?aiaiiie head aoaeao iaoiaeeoueny iiia? oaeouae aa?oeiu, ec eioi?ie
eaeao aieia, a i?e iiiiue ia?aiaiiie tail iiaua aa?oeiu iiiauathony
a “oaino” i/a?aaee queue;
aniiiiaaoaeueiue iannea visited[1..n], eioi?ue ioaeai aeey oiai,
/oiau ioia/aoue oaea i?ieaeaiiua aa?oeiu (visited[i]=TRUE aa?oeia i
i?ieaeaia);
aniiiiaaoaeueiue iannea prev[1..n] aeey o?aiaiey i?ieaeaiiuo aa?oei.
A yoii ianneaa e aoaeao noi?ie?iaai eneiiue iooue;
ia?aiaiiay f, eioi?ay i?eiao cia/aiea TRUE, eiaaea iooue aoaeao
iaeaeai.
E?iia oiai, iu aaaaeai ianeieueei aniiiiaaoaeueiuo ia?aiaiiuo, eioi?ua
iiiaaeiayony i?e i?aaiecaoeee oeeeeia.
Program breadth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =
(
(False, True, True, False, False, False, False, False,
False),
(True, False, True, False, False, False, True, True,
False),
(True, True, False, True, True, False, False, False,
False),
(False, False, True, False, True, False, False, False,
False),
(False, False, True, True, False, True, False, True,
False),
(False, False, False, False, True, False, True, True, True
),
(False, True, False, False, False, True, False, True, True
),
(False, True, False, False, True, True, True, False,
False),
(False, False, False, False, False, True, True, False,
False)
);
Var A, B: integer;
Procedure A_to_B(A, B: integer);
Var
Visited: array[1..n] of boolean;
Prev: array[1..n] of integer;
path: array[1..n] of integer;
head, tail: integer;
f: boolean;
i, v, k: integer;
Begin
head:=1;
tail:=1;
f:=False;
For i:=1 to n do
Begin
Visited[i]:=False;
Prev[i]:=0
End;
Path[tail]:=A;
Visited[A]:=True;
While (head0 do
Begin
Write(‘ aa?oeia
i i?ieaeaia);
ia?aiaiiay f, eioi?ay i?eiao cia/aiea TRUE, eiaaea iooue aoaeao
iaeaeai.
Program depth_first_search;
Const n=9;
m:array[1..n, 1..n] of boolean =
(
(False, True, True, False, False, False, False, False,
False),
(True, False, True, False, False, False, True, True,
False),
(True, True, False, True, True, False, False, False,
False),
(False, False, True, False, True, False, False, False,
False),
(False, False, True, True, False, True, False, True,
False),
(False, False, False, False, True, False, True, True, True
),
(False, True, False, False, False, True, False, True, True
),
(False, True, False, False, True, True, True, False,
False),
(False, False, False, False, False, True, True, False,
False)
);
Var A, B: integer;
Procedure A_to_b(A, B: integer);
Var
Visited: array[1..n] of boolean;
f: boolean;
i: integer;
Procedure Depth(p: integer);
var k: integer;
Begin
Visited[p]:=True;
For k:=1 to n do
If not f then
If m[p, k] and not Visited[k] then
If k=B then
Begin
f:=True;
Write(B);
Break
End
else Depth(k);
If f then write(‘nil do
Begin
Write(l^.i:3);
l:=l^.next
End
End;
Begin
stack1:=nil;
stack2:=nil;
Write(‘Ia/aeueiay aa?oeia: ‘);readln(v);
Push(v, stack1);
While stack1NIL do
Begin
v:=peek(stack1);
i:=1;
While (icolor[j]) then
Begin
min:=Matrix[i, j];
a:=i;
b:=j
End;
len:=len+min
end;
Begin
Clrscr;
Init;
For k:=1 to n-1 do
Begin
Findmin(a, b);
Ribs[k].a:=a;
Ribs[k].b:=b;
col:=Color[b];
For i:=1 to n do
If color[i]=col then color[i]:=color[a];
End;
For i:=1 to n-1 do
Writeln(ribs[i].a, ‘ ‘, ribs[i].b);
Writeln(‘Length= ‘, len);
Readkey
End.
Aeai?eoi Aeaeeno?u.
Нашли опечатку? Выделите и нажмите CTRL+Enter
