Ocena użytkownikóww: ***** / 1
Nadesłany przez Tomasz Lubiński, 09 sierpnia 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
graficzny1_d/ciag_graficzny.dpr:
//www.algorytm.org
//algorytm testowania czy podany ciąg stopni wierzcholków grafów jest graficzny
//Tomasz Lubiński (c) 2003
program ciag_graficzny;
uses
SysUtils;
{$R *.RES}
{$Apptype Console}
var
flag, graficzny: Boolean;
n,i,j,smin,s: Integer;
c: Array[1..100] of Integer;
begin
//pobierz dane
writeln('Podaj liczbe wierzcholkow grafu');
readln(n);
for i:=1 to n do
begin
writeln('Podaj stopien wierzcholka '+IntToStr(i));
readln(c[i]);
end;
//algorytm testowania czy podany ciąg stopni wierzcholkow jest graficzny
graficzny:=true;
//sprawdz czy suma ciągu jest liczbą parzystą
s:=0;
for i:=1 to n do s:=s+c[i];
if (s mod 2)<>0 then
graficzny:=false
else
//posortuj ciąg nierosnąco jeżeli suma jest liczbą parzystą
begin
flag:=true;
while (flag) do
begin
flag:=false;
for i:=1 to n-1 do
if c[i]<c[i+1] then
begin
s:=c[i];
c[i]:=c[i+1];
c[i+1]:=s;
flag:=true;
end;
end;
end;
//sprawdz czy spelniona jest nierownosc P. Erdos, T. Gallai (1960)
j:=1;
while (graficzny and (j<=n-1)) do
begin
s:=0;
for i:=1 to j do s:=s+c[i];
smin:=0;
for i:=1 to n do
if j<c[i] then smin:=smin+j
else smin:=smin+c[i];
if s>j*(j-1)+smin then graficzny:=false
else j:=j+1;
end;
//podaj użytkownikowi wynik
if (graficzny) then writeln('Podany ciąg jest graficzny')
else writeln('Podany ciąg nie jest graficzny');
readln;
end.