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 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 các đoạn thẳng rời nhau. Hai đoạn được xem là rời nhau nếu chúng không có điểm chung. Các đoạn có dạng như trong bài Phủ đoạn 2.

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.
Từ dòng thứ hai: liệt kê các đoạn, mỗi dòng có thể chứa nhiều đoạn, mỗi đoạn được ghi trọn trên một dòng.
Dữ liệu ra: tệp văn bản DOAN.OUT
Dòng đầu tiên: số  K.
Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng rời nhau.

8
( -2, 3) [3 , 5) [8, 12] [13 ,15 )
(1 , 9 ) ( 2, 5 ]  [5 ,8 )  [7, 15]



5
1 2 7 3 4



Kết quả trên cho biết có tối đa 5 đoạn rời nhau là 1, 2, 7, 3 và 4.

Thuật toán

Phương pháp: Tham.
Trước hết ta chỉnh lại các đầu hở giống như bài trước sau đó áp dụng thuật toán của bài đoạn rời.
Các điểm đầu và cuối đoạn và các biến liên quan được khai báo kiểu số thực.
Độ phức tạp: N.logN  chi phí cho quick sort.
(*   Pascal   *)
(*========================================
   liet ke toi da cac doan thang roi nhau           
  =========================================*)
program DoanRoi2;
uses crt;
Tổ chức dữ liệu: xem bài Phủ đoạn 2
function DocSo: xem bai Phu doan 2;
procedure DocDoan: xem bai Phu doan 2;
procedure Doc: xem bai Phu doan 2;
procedure Qsort(l,r: integer): xem bai Phu doan 2;
procedure XuLi : xem bai Doan roi 1;
procedure Ket: xem bai Doan roi 1 ;
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