//
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]


About pascalteacher

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

Thảo luận

Chưa có phản hồi.

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười Hai 2016
M T W T F S S
« Nov   Jan »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

sunset

Detroit Night

White-winged Scoter | Macreuse à ailes blanches

More Photos

Thống kê

  • 95,281 lượt xem

%d bloggers like this: