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 <ai , bi> 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 và thuộc một trong 4 dạng sau đây:
[d,c] - đoạn đóng: chứa điểm đầu d và điểm cuối c,
(d,c] - đoạn mở trái: không chứa điểm đầu d, chứa điểm cuối c,
[d,c) - đoạn mở phải: chứa điểm đầu d, không chứa điểm cuối c,
(d,c) - đoạn mở: không chứa điểm đầu d và điểm cuối c.
Hãy chỉ ra ít nhất K đoạn thẳng sao cho khi đặt chúng trên trục số thì có thể phủ kín đoạn <x, y> với tọa độ nguyên cho trước.

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 1 < N £ 1000.
Dòng thứ hai: Đoạn  x  y
Từ dòng thứ ba 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, nếu vô nghiệm K=0.
Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng phủ kín đoạn x  y.

6
(4,10 )
(-2, 5)
[ 5 , 7]  [6, 7)
[7, 8)  (8,9) 
(7 , 10 ]



3
1
2
6




Kết quả trên cho biết ít nhất là 3 đoạn 1, 2 và 6 sẽ phủ kín đoạn (4,10).
Chú ý: Giữa các số và các ký tự trong file input có thể chứa các dấu cách.
Thuật toán
Phương pháp: Tham
                Để ứng dụng thuật toán của bài Phủ đoạn 1 ta đưa các đoạn về cùng một dạng đóng bằng cách chỉnh lại các đầu mở. Cụ thể là thêm/bớt điểm đầu mở của mỗi đoạn một lượng e = 0.3 như sau, 
[d,c] giữ nguyên
(d,c] ®[d + e, c],
[d,c) ®[d, c - e],
(d,c) ®[d + e, c - e].
                Qui tắc trên khá dễ hiểu.  Bạn hãy giải thích vì sao chọn e= 0.3 mà không chọn e= 0.5?
                Hai trường a và b thể hiện các điểm đầu và cuối mỗi đoạn cần được khai báo kiểu real(float). Các biến liên quan đến các trường này trong thủ tục xử lí cũng cần được khai báo theo các kiểu trên.
                Ta đọc tất cả các đoạn và ghi vào mảng d[0..N], trong đó d[0] sẽ chứa đoạn x, y.
                Cách đọc các đoạn được tổ chức trên cơ sở giả thiết là các đoạn được viết đúng cú pháp. Mỗi lần ta đọc một kí tự ch từ tệp input. Nếu (ch = ‘(‘) hoặc (ch = ‘[‘) thì ta gặp kí tự đầu đoạn: ta tiến hành đọc một đoạn. Để đọc một đoạn ta lần lượt đọc số thứ nhất, bỏ qua dấu phảy (‘,’) ngăn cách giữa hai số rồi đọc số thứ hai. Thủ tục đọc một đoạn kết thúc khi gặp một trong hai dấu đóng ngoặc là ‘]’ hoặc ‘)’. Căn cứ vào các dấu mở và đóng ngoặc đầu và cuối mỗi đoạn ta xác định lượng  e cần thêm hoặc bớt cho mỗi điểm đầu hoặc cuối đoạn, đương nhiên các điểm này cần được biểu diễn dưới dạng số thực.
            Độ phức tạp: N2.

Chú ý

                Bạn có thể dùng kỹ thuật đồng dạng chuyển trục số sang trục số "phóng đại" gấp 3 lần. Khi đó các đoạn tương ứng sẽ được chuyển như sau:
[d,c] ® [3d - 1, 3c + 1],
(d,c] ® [3d + 1, 3c + 1],
[d,c) ® [3d - 1, 3c - 1],
(d,c) ® [3d + 1, 3c - 1].
Tức là giữ lại kiểu nguyên và chọn e = 1. Cách làm này có đơn giản hơn trong trường hợp giới hạn của d và c là nhỏ.
 (*  Pascal  *)
(*========================================
                Phu doan 2
  =========================================*)
program PhuDoan2;
uses crt;
const
  mn = 2002; bl = #32; nl = #13#10;
  fn = 'doan.inp'; gn = 'doan.out';
  MoVuong = '['; DongVuong = ']'; MoTron = '('; DongTron = ')';
  NgoacMo = [MoVuong, MoTron]; NgoacDong = [DongVuong, DongTron];
  ChuSo = ['0'..'9']; CongTru = ['+','-']; eps = 0.3;
type
  KieuDoan = record
a,b: real;
id: integer; { chỉ số đoạn }
 end;
  md1 = array[0..mn] of KieuDoan;
  mi1 = array[0..mn] of integer;
var n: integer; { n - so luong doan }
    d: md1;
    f,g: text;
    t: mi1;
    xy: KieuDoan;
    ch: char;
    k: integer; {dem so doan da doc}
    Ngoac: char;
(* Doc 1 so nguyen tu input file *)
function DocSo: integer;
var s,dau: integer;
begin
  s := 0; dau := 1;
  while not (ch in (CongTru + ChuSo)) do read(f,ch);
  if (ch in CongTru) then
  begin
    if (ch = '-') then dau := -1;
    read(f,ch);
  end;
  while not (ch in ChuSo) do read(f,ch);
  repeat
    s := 10*s + ord(ch) - ord('0');
    read(f,ch);
  until not (ch in ChuSo);
  DocSo := dau * s;
end;
procedure DocDoan;
begin
  k := k + 1; d[k].id := k; Ngoac := ch; d[k].a := DocSo;
  if (Ngoac = MoTron) then d[k].a := d[k].a + eps;
  while (ch <> ',') do read(f,ch);
  d[k].b := DocSo;
  while not(ch in NgoacDong) do read(f,ch);
  if (ch = DongTron) then d[k].b := d[k].b - eps;
end;
procedure Doc;
 var i: integer;
begin
  assign(f,fn); reset(f); readln(f,n); k := -1;
  while (k < n) and (not eof(f)) do
  begin
    read(f,ch);
    if (ch in NgoacMo) then DocDoan;
  end;
  close(f); xy.a := d[0].a; xy.b := d[0].b;
end;
procedure Qsort(l,r: integer): xem bài phủ đoạn 1;
function Tim(id,ic: integer; x: real): xem bài phủ đoạn 1;
procedure Ket(k: integer): xem bài phủ đoạn 1;
procedure XuLi: xem bài phủ đoạn 1;
BEGIN
  Doc; Qsort(1,n); XuLi;
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