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 trên trục số 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. 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: xem bài trước
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].
Thí dụ này cho biết ít nhất là 3 đoạn 1, 3 và 4 sẽ phủ kín đoạn [3, 23].

5
3 23
1 15
3 10
8 20
17 25
2 7

3
1
3
4

Thuật toán

Phương pháp: Tham
Sắp các đoạn tăng theo đầu phải b.
k : = 1; { chỉ số đầu tiên }
v := x; { Đầu trái của đoạn [x,y] }
Lặp đến khi  v ³ y
                   Duyệt ngược từ N đến k
                   Tìm đoạn  j  [aj, bj] đầu tiên có đầu trái aj £  v;
        Nếu không tìm được: vô nghiệm;
        Nếu tìm được:
                   Ghi nhận đoạn j;
                   Đặt lại v  :=  bj;
                   Đặt lại k := j+1;
Độ phức tạp: N2.
(*  Pascal  *)
 (*========================================
                Phu doan 1
      Tìm ít nhất K đoạn có thể phủ kín
           đoạn [x,y] cho trước
  =========================================*)
program PhuDoan1;
uses crt;
const
  mn = 2002; bl = #32; nl = #13#10;
  fn = 'doan.inp'; gn = 'doan.out';
type
  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: integer; { n - so luong doan }
    d: md1; { cac doan }
    f,g: text;
    t: mi1;
    x, y: integer; { Doan can phu }
procedure Doc;
 var i: integer;
begin
  assign(f,fn); reset(f); readln(f,n);
  readln(f,x, y);
  for i := 1 to n do
   begin
     readln(f,d[i].a,d[i].b);
     d[i].id := i;
   end;
  close(f);
end;
procedure Qsort(l,r: integer): tự viết
(*----------------------------------------
   Duyet nguoc cac doan d[s..e]
   tim doan i dau tien thoa d[i].a <= x
  ---------------------------------------*)
function Tim(s,e,x: integer): integer;
var i: integer;
begin
  Tim := 0;
  for i := e downto s do
    if (d[i].a <= x) then
      begin
        Tim := i;
        exit;
      end;
end;
procedure Ket(k: integer): tự viết
procedure XuLi;
var i,j,k,v: integer; { k - so doan tim duoc }
begin
  v := x;
  k := 0; t[k] := 0;
  repeat
    j := Tim(t[k]+1,n,v);
    if (j = 0) then { Khong tim duoc }
       begin  Ket(0); { vo nghiem } exit;  end;
    v := d[j].b; k := k + 1; t[k] := j;
  until (v >= y);
  Ket(k); { co nghiem }
end;
BEGIN
  doc; qsort(1,n); xuli;
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