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.  Liệt kê tối đa K đoạn bao nhau.

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
Dòng đầu tiên:  số tự nhiên K.
Tiếp đến là K dòng, mỗi dòng chứa một số tự nhiên là chỉ số của đoạn trong dãy tìm được. Các chỉ số được liệ kê theo trật tự bao nhau từ lớn đến nhỏ.
Thí dụ này cho biết tối đa có 3 đoạn bao nhau là các đoạn 1, 5  và 2:  [-1,12] Ê [8,11] Ê [8,10].

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

3
1
5
2



Thuật toán

Giống bài Đoạn bao nhau 1. Để có danh sách đoạn bao nhau ta dùng mảng trỏ t[1..n],  t[i] trỏ đến đoạn j là đoạn nằm trong đoạn i và c[j] đạt giá trị max.
Độ phức tạp: N2.
(*  Pascal  *)
uses crt;
const MN = 1001; bl = #32; nl = #13#10;
fn = 'doan.inp'; gn = 'doan.out';
type
Doan = record  a,b: integer; id: integer;  end;
MD1 = array[0..MN] of Doan;
MI1 = array[0..MN] of integer;
var f,g: text;
d: MD1;
t: MI1; { tro truoc }
n: integer;
imax, k: integer;
procedure Doc; tự làm
function SanhDoan(x,y: Doan): integer; tự làm
procedure QSortB(t,p: integer): tự làm
procedure XuLi;
var c: mi1;
i,j: integer;
begin
  imax := 1;
  for i := 1 to n do
  begin
    c[i] := 0; t[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
        begin c[i] := c[j]; t[i] := j end;
    end;
    c[i] := c[i] + 1;
    if (c[imax] < c[i]) then imax := i;
  end;
  k := c[imax];
end;
procedure Path(i: integer);
begin
  if (i = 0) then exit;
  writeln(g,d[i].id); Path(t[i]);
end;
procedure Ghi;
begin
   assign(g,gn); rewrite(g); writeln(g,k);
   path(imax); close(g);
end;
BEGIN
 Doc; QSortB(1,n); XuLi; Ghi; 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