Đoạn gối 2

Cho N đoạn thẳng trên trục số với các điểm đầu a_i và điểm cuối b_i là những số nguyên trong khoảng -1000..1000, a_i < b_i. 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ỡ  N².

(*  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

VÀ

LẬP TRÌNH