| |
Даны n, n<=20, отрезков находящихся на оси Ох. Для каждого отрезка i, i=1,2,...,n, известны координаты его концов. Напишите программу, которая подсчитает максимальное количество взаимно непересекающихся отрезков. Отрезки пересекаются если у них есть хотя бы одна общая точка, включая края.
Количество отрезков и координаты их краев(целые числа) вводятся с клавиатуры. На экран выводится максимальное число непересекающихся отрезков.
uses crt;
const nmax=20;
type koordinaty=record
a,b:real;
end;
mas=array[1..nmax] of koordinaty;
otrezki=0..nmax;
var t:mas;
n:otrezki;
p:boolean;
label 1;
procedure vvod(var k:otrezki; var m:mas);
var i:otrezki;
begin
write('n= ');
readln(k);
for i:=1 to k do begin
readln(m[i].a,m[i].b);
if m[i].b textcolor(4);
writeln(' ERROR');
p:=true;
exit;
end
else p:=false;
end;
end;
procedure vivod(m:mas);
var i:otrezki;
begin
for i:=1 to n do
writeln(m[i].a:7:3,m[i].b:7:3);
end;
procedure sort(var m:mas);
var vr:^koordinaty;
i,j:otrezki;
begin
new(vr);
for i:=1 to n-1 do
for j:=i+1 to n do
if m[i].a>m[j].a then begin
vr^:=m[i];
m[i]:=m[j];
m[j]:=vr^;
end;
dispose(vr);
end;
procedure zigzag(var m:mas);
var v:^real;
i:otrezki;
begin
new(v);
for i:=1 to n do
if not odd(i) then
with m[i] do begin
v^:=a;
a:=b;
b:=v^;
end;
dispose(v);
end;
function MAX(m:mas):otrezki;
var f,i:otrezki;
begin
f:=n;
for i:=2 to n do
if (m[i].b<=m[i-1].b)or(m[i-1].a=m[i].a) then dec(f);
max:=f;
end;
BEGIN
clrscr;
textcolor(15);
vvod(n,t);
if p then goto 1;
sort(t);
vivod(t);
zigzag(t);
writeln('MAX= ',max(t));
1:;
textcolor(15);
writeln(' Press ');
readln
END.
<< Назад
|
|
