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. Liệt kê tối đa K đoạn thẳng gối nhau liên tiếp.

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
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 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 tối đa có 3 đoạn  2,  4 và 5 tạo thành dãy đoạn gối nhau liên tiếp.


5
2 7
1 3
7 9
3 4
4 5

3
2
4
5

Thuật toán

Tương tự như bài Đoạn gối 1 nhưng cần tạo thêm con trỏ trước. t[i] = j có nghĩa là đoạn i được gối sau đoạn j. Thủ tục GiaiTrinh(i) liệt kê các đoạn gối liên tiếp từ phải qua trái thực chất là liệt kê theo chiều ngược các phần tử trong mảng con trỏ trước t bắt đầu từ phần tử thứ i. Giả sử t có dạng sau,
t[2] = 0; t[4] = 2; t[5] = 4;
và giả sử i = 5 là vị trí đạt trị cmax, ta phải ghi vào file kết quả g dãy các đoạn gối nhau liên tiếp như sau,
2 4 5
Ta chỉ việc gọi đệ quy muộn như sau
0
0
1
2
3
4
5



0

2
4
 procedure GiaiTrinh(i: integer);
 begin
  if (i <> 0) then
    begin GiaiTrinh(t[i]); writeln(g,d[i].id); end;
 end;
Độ phức tạp: cỡ  N2.
(*  Pascal  *)
(*=============================================
   Doan Goi 2: Liet ke toi da cac doan thang
                 goi nhau liên tiep
  =============================================*)
program DoanGoi2;
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 - so luong doan, m - so doan duoc chon }
    d: md1; // cac doan
    f,g: text;
    c: mi1; { c[i] = so luong max doan goi voi doan i }
    t: mi1; { tro truoc }
procedure Doc: tự viết
procedure Qsort(i1,i2: integer): tự viết
procedure XuLi;
var i,j,jmax: integer;
begin
  fillchar(t,sizeof(t),0); {Khởi trị mảng trỏ trước}
  c[1] := 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]+1; t[i] := jmax;
    end;
end;
procedure GiaiTrinh(i: integer): tự viết;
procedure Ket;
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]);
  GiaiTrinh(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


tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts