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



Đề Bài: Cho N đoạn thẳng với các điểm đầu ai và điểm cuối bilà những số nguyên trong khoảng -1000..1000, ai < bi. Liệt kê số lượng tối đa K đoạn thẳng không giao nhau. Hai đoạn thẳng [a,b][c,d]được coi là không giao nhau nếu xếp chúng trên cùng một trục số, chúng không có điểm chung. Điều kiện này đòi hỏi: b < c hoặc d < a.

DOAN.INP
DOAN.OUT

Dữ liệu vào: tệp văn bản DOAN.INP
Dòng đầu tiên: số tự nhiên N, 1 < N £ 1000.
Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa hai số nguyên ai bi cách nhau qua dấu cách, biểu thị điểm đầu và điểm cuối của đoạn thứ i, i = 1..N. 
Dữ liệu ra: tệp văn bản DOAN.OUT
Dòng đầu tiên: số tự nhiên K.
K dòng tiếp theo, mỗi dòng một số tự nhiên v thể hiện chỉ số của các đoạn rời nhau tìm được.
Thí dụ bên cho biết tối đa có 5 đoạn rời nhau là 1, 2, 7, 3 và 4.


8
2 3
4 5
10 12
13 15
1 9
2 5
6 8
7 15


5
1
2
7
3
4


Thuật toán

Phương pháp: tham.
1. Sắp các đoạn tăng theo đầu phải b.
2. Khởi trị: Lấy đoạn 1, đặt r = b1 là đầu phải của đoạn này
3. Với mỗi đoạn j := 2..N tiếp theo xét:
Nếu đầu trái của đoạn j, aj > r thì  lấy đoạn   j  đưa vào kết quả
và chỉnh r là đầu phải của đoạn j, r := bj.
Độ phức tạp: cỡ NlogN  chi phí cho quick sort.
(*  Pascal  *)
(*===========================================
  Doan roi 1: Liet ke toi da cac doan thang
              khong giao nhau
  ===========================================*)
program DoanRoi1;
uses crt;
const mn = 1001; bl = #32 {Dấu cách}; nl = #13#10 {Xuống dòng};
      fn = 'doan.inp'; gn = 'doan.out';
type { Mô tả một đoạn }
  KieuDoan = record
               a,b: integer;
               id: integer; { Chỉ số đoạn }
             end;
  md1 = array[0..mn] of KieuDoan;
  mi1 = array[0..mn] of integer;
var n,m,r: integer; { n – số lượng đoạn }
                    { m – số lượng đoạn được chọn }
                    { r – đầu phải đang duyệt     }
    d: md1; { các đoạn d[1..n] }
    f,g: text;
    c: mi1; { mảng chứa kết qủa }
procedure Doc;
 var i: integer;
begin
  assign(f,fn); reset(f); readln(f,n);
  for i := 1 to n do
   begin
     read(f,d[i].a,d[i].b); d[i].id := i;
   end;
  close(f);
end;
(*---------------------------------
    Sắp tăng các đoạn d[t..p] theo
    đầu phải b.
  ---------------------------------*)
procedure Qsort(t,p: integer);
var i,j,m: integer;
    x: KieuDoan;
begin
  i := t; j := p; m := d[(i + j) div 2].b;
  while (i <= j) do
   begin
    while (d[i].b < m) do i := i + 1;
    while (m < d[j].b) do j := j - 1;
    if (i <= j) then
     begin
       x := d[i]; d[i] := d[j]; d[j] := x;
       i := i + 1; j := j - 1;
     end;
   end;
   if (t < j) then Qsort(t,j);
   if (i < p) then Qsort(i,p);
end;
procedure XuLi;
var i: integer;
begin
  m := 1; c[m] := 1; { Đưa đoạn 1 vào kết quả }
  r := d[m].b; { đầu phải của đoạn cuối trong kết quả }
  for i := 2 to n do
    if (r < d[i].a) then
      begin
        m := m + 1; c[m] := i; r := d[i].b;
      end;
end;
procedure Ghi;
  var i: integer;
begin
  assign(g,gn); rewrite(g); writeln(g,m);
  for i := 1 to m do writeln(g,d[c[i]].id);
  close(g);
end;
BEGIN
  Doc; Qsort(1,n); XuLi; Ghi;
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