//
you're reading...
Bài tập huấn luyện

Bài 1.1 Đoạn rời 1

[Sáng tạo trong thuật toán và lập trình – Quyển 2]


Đề bài


Cho N đoạn thẳng 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ê 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
8 5
2 3 1
4 5 2
10 12 7
13 15 3
1 9 4
2 5
6 8
7 15

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.


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.
  1. 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.


Chương trình


[Sáng tạo trong lập trình – Quyển 2 – Bài 1.1]


Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 148,992 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: