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. Hãy tìm số lượng tối đa K đoạn thẳng gối nhau liên tiếp. Hai đoạn thẳng [a,b][c,d] được gọi là gối nhau nếu xếp chúng trên cùng một trục số thì điểm đầu đoạn này trùng với điểm cuối của đoạn kia, tức là c = b hoặc d = a.

DOAN.INP
DOAN.OUT
Dữ liệu vào: tệp văn bản DOAN.INP: xem Đoạn gối 1
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 có tối đa 3  đoạn gối nhau liên tiếp là [1,3], [3,4] [4,5].

5
2 7
1 3
7 9
3 4
4 5

3

Thuật toán

Phương pháp: Quy hoạch động + Tham.
Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là số lượng tối đa các đoạn thẳng gối nhau tạo thành một dãy nhận đoạn i làm phần tử cuối dãy (khi khảo sát các đoạn từ 1..i). Ta có
c(1) =1,
Với i = 2...N:  c(i) = max { c(j) | 1 £j < i, Đoạn j kề trước đoạn i:  bj= ai } + 1.
Lợi dụng các đoạn sắp tăng theo đầu phải b, với mỗi đoạn i  ta chỉ cần duyệt ngược các đoạn j đứng trước đoạn i cho đến khi phát hiện bất đẳng thức bj < ai.  
Kết quả: K = max { c(i)  | i = 1...n }.
Độ phức tạp: cỡ N2 vì với mỗi đoạn  ta phải duyệt tối đa tất cả các đoạn đứng trước đoạn đó.
(* Pascal *)
 (*============================
    Đoạn Gối 1: Số lượng tối đa
    các đoạn gối nhau.
  ============================*)
program DoanGoi1;
uses crt;
const
  mn = 1001; bl = #32; nl = #13#10;
  fn = 'doan.inp'; gn = 'doan.out';
type
  KieuDoan = record a,b: integer; end;
  md1 = array[0..mn] of KieuDoan;
  mi1 = array[0..mn] of integer;
var n,m: integer; { n – số lượng đoạn, m – số đoạn được chọn }
    d: md1; { các đoạn d[1..n]}
    f,g: text;
    c: mi1; { c[i] = số lượng max các đoạn gối nhau đến i }
procedure Doc; tự viết
procedure Qsort(t,p: integer);tự viết
procedure XuLi;
var i,j: integer;
begin
  c[1] := 1;
  for i := 2 to n do { Tính c[i] }
    begin
      c[i] := 0;
        for j := i-1 downto 1 do
          begin
            if (d[j].b < d[i].a)  { doan j khong noi voi i }
            then break;
            if (d[j].b = d[i].a) then { j noi voi i }
               if (c[j] > c[i]) then c[i] := c[j];
          end;
      c[i] := c[i] + 1;
    end;
end;
procedure Ket; { Tim c max va hien thi ket qua }
var i,imax: integer;
begin
  assign(g,gn); rewrite(g);
  imax := 1;
  for i := 2 to n do
    if (c[imax] < c[i]) then imax := i;
  writeln(g,c[imax]); close(g);
end;
BEGIN
  Doc; Qsort(1,n); XuLi;  Ket;
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