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ê các đoạn thẳng gối nhau có tổng chiều dài C lớn nhất.


DOAN.INP

DOAN.OUT
Dữ liệu vào: tệp văn bản DOAN.INP: xem bài Đoạn gối 1.
Dữ liệu ra: tệp văn bản DOAN.OUT
Dòng đầu tiên: số tự nhiên C.
Mỗi dòng tiếp theo chứa một số tự nhiên biểu thị chỉ số của đoạn thẳng gối nhau liên tiếp trong dãy tìm được.
Thí dụ này cho biết hai đoạn 2  và 4 tạo thành dãy đoạn gối nhau liên tiếp có tổng chiều dài max là 39.

8
2 7
1 3
7 9
3 40
3 5
2 3
5 9
9 16


39
2
4


Thuật toán

Phương pháp: Quy hoạch độngkết hợp với con trỏ trước t để giải trình kết quả.  
Giả sử các đoạn được sắp tăng theo đầu phải b. Kí hiệu c(i) là tổng chiều dài lớn nhất các đoạn thẳng gối nhau liên tiếp 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). Để ý rằng (bi -  ai) là chiều dài đoạn thứ i, ta có
c(1)  = chiều dài đoạn 1 = b1 - a1,
Với i = 2..N:    c(i) = max { c(j) | 1 £ j < i,  đoạn j kề trước đoạn i: bj= ai } + (bi -  ai), 
Nếu j là chỉ số đạt max thì đặt ti=  j.
            Độ phức tạp:  N2.
(*  Pascal  *)
(*=============================================
    Doan Goi 3: Liet ke cac doan goi nhau
                co tong chieu dai max
  ============================================*)
program DoanGoi3;
uses crt;
const
  mn = 1001; bl = #32; nl = #13#10;
  fn = 'doan.inp'; gn = 'doan.out';
type
  KieuDoan = record a,b,id: 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;
    f,g: text;
    c: mi1; {c[i] = chieu dai max nhan i lam doan cuoi}
    t: mi1; { tro truoc }
procedure Doc; tự viết
procedure Qsort(l,r: integer); tự viết
procedure XuLi;
var i,j,jmax: integer;
begin
  fillchar(t,sizeof(t),0);{ Khơỉ tạo mảng trỏ trước }
  c[1] := d[1].b - d[1].a; { Chieu dai doan 1 }
  for i := 2 to n do
    begin
      c[i] := 0; jmax := i;
        for j := i-1 downto 1 do
          begin
            if (d[j].b < d[i].a) then break;
            if (d[j].b = d[i].a) then
               if (c[j] > c[jmax]) then
                         jmax := j;                
          end;
      c[i] := c[jmax] + (d[i].b - d[i].a); t[i] := jmax;
    end;
end;
procedure GiaiTrinh(i: integer); tự viết
procedure Ket; tự viết
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