Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng
-1000..1000, ai < bi, i = 1..n. Tìm K là số lượng nhiều đoạn nhất tạo thành một dãy các đoạn bao nhau liên tiếp. Hai đoạn [a,b][c,d] được gọi là bao nhau nếu đoạn này nằm lọt trong đọan kia, tức là a £ c < d £  b hoặc c £ a < b £ d.

DOAN.INP
DOAN.OUT

Dữ liệu vào: tệp văn bản DOAN.INP: xem bài trước
Dữ liệu ra: tệp văn bản DOAN.OUT
chứa duy nhất một số tự nhiên K.
Thí dụ này cho biết tối đa có 3 đoạn bao nhau là các đoạn [-1,12] Ê [8,11] Ê [8,10].


6
-1 12
8 10
8 11
2 7
17 18
13 20

3


Thuật toán

Phương pháp: Quy hoạch động.  
                Giả sử các đoạn được sắp tăng theo đầu phải b như sau. Nếu hai đoạn có cùng đầu phải thì đoạn nào có đầu trái nhỏ hơn sẽ được đặt sau.  Kí hiệu c(i) là số lượng lớn nhất các đoạn bao nhau liên tiếp trong đoạn i. Ta có,
c(1)  = 1,
Với i = 2...N:    c(i) = max { c(j) | 1 £ j < i, Đoạn j lọt trong đoạn i: aj ³ ai } + 1,
                Độ phức tạp: N2.
                Hàm SanhDoan(x,y)thiết lập trật tự giữa hai đoạn xy như sau:
s         Nếu x.b < y.b cho kết quả -1, nếu không: xét tiếp
s         Nếu x.b > y.b cho kết quả 1, nếu không: xét tiếp
s         Xét trường hợp x.b = y.b.
o        Nếu x.a < y.a cho kết quả 1, nếu không: xét tiếp
o        Nếu x.a > y.a cho kết quả -1, nếu không: xét tiếp
o        Hai đoạn trùng nhau: x.a = y.a và x.b = y.b cho kết qủa 0.
(*  Pascal  *)
uses crt;
const MN = 1001; bl = #32; nl = #13#10;
fn = 'doan.inp'; gn = 'doan.out';
type
Doan = record  a,b: integer;  end;
MD1 = array[0..MN] of Doan;
MI1 = array[0..MN] of integer;
var f,g: text;
d: MD1; { cac doan }
n: integer; { so doan }
procedure Doc; tự làm
function SanhDoan(x,y: Doan): integer;
begin
  if (x.b < y.b) then begin SanhDoan := -1; exit end;
  if (x.b > y.b) then begin SanhDoan := 1; exit end;
  if (x.a < y.a) then begin SanhDoan := 1; exit end;
  if (x.a > y.a) then begin SanhDoan := -1; exit end;
  SanhDoan := 0;
end;
procedure QSortB(t,p: integer);
var i,j: integer; m,x: Doan;
begin
  i := t; j := p; m := d[(i+j) div 2];
  while (i <= j) do
  begin
    while (SanhDoan(d[i],m) < 0) do i := i+1;
    while (SanhDoan(d[j],m) > 0) do j := j-1;
    if (i <= j) then
    begin
      x := d[i]; d[i] := d[j]; d[j] := x;
      i := i+1; j := j-1;
    end;
  end;
  if (t < j) then QSortB(t,j);
  if (i < p) then QSortB(i,p);
end;
function XuLi: integer;
   var c: mi1; { c[i] so doan bao nhau max }
     i,j,cmax: integer;
begin
  cmax := 0;
  for i := 1 to n do
  begin
    c[i] := 0;
    for j := i-1 downto 1 do
    begin
      if (d[j].b <= d[i].a) then break;
      if (d[j].a >= d[i].a) then
        if (c[j] > c[i]) then c[i] := c[j];
    end;
    c[i] := c[i] + 1;
    if (cmax < c[i]) then cmax := c[i];
  end;
  XuLi := cmax;
end;
procedure Ghi(k: integer);
begin
   assign(g,gn); rewrite(g); writeln(g,k); close(g);
end;
BEGIN
 Doc; QSortB(1,n); Ghi(XuLi); readln;
END.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts