kết quả từ 1 tới 7 trên 7

phủ đoạn

  1. #1
    Ðến Từ
    Bắc Giang
    Thành Viên Thứ: 390262
    Bài gửi
    4

    phủ đoạn

    HTML Code:
    program PhuDoan1;uses crt;constmn = 2002; bl = #32; nl = #13#10;
    fn = 'doan.inp'; gn = 'doan.out';
    typeKieuDoan = recorda,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---------------------------------------*) 23
    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 }
    beginv := x;k := 0;
     t[k] := 0;
    repeatj := 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.
    procedure Ket(k: integer): giúp mình viết đoạn này với ạ
    Quick reply to this message Trả lời       

  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: phủ đoạn

    - Bài này bạn cần phải cho biết đề bài. Đại ý của bài này mình đoán sơ sơ là: cho N đoạn thẳng trên trục số và 1 đoạn [x, y]; yêu cầu tìm K đoạn (bất kỳ, ít đoạn nhất,..) trong số N đoạn để che phủ toàn bộ đoạn [x, y].
    - Tìm K đoạn như thế nào thì phụ thuộc vào phần sort của bạn. Mình nghĩ nếu đã sort lại rồi mà còn dùng linear search thì thuật toán hơi kém hiệu quả khi phải chạy tới O(n^2) lận.
    - Phần 'procedure Ket' thì đây là xuất kết quả. Mình nghĩ là xuất chỉ số của đoạn cần bởi vì khi lưu trữ bạn có lưu lại chỉ số. Lần nữa, bạn nên post đề cho rõ ràng vì đây chỉ là suy đoán của mình.
    Mã:
    procedure Ket(k : integer);
    var i : integer;
    begin
        assign(f, gn);
        rewrite(f);
        writeln(f, k);
        for i := 1 to k do
            writeln(d[t[i]].id); ...
    end;
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    Bắc Giang
    Thành Viên Thứ: 390262
    Bài gửi
    4

    Reply: phủ đoạn

    DỀ NHƯ THẾ NÀY BẠN AK.
    Bài 1.7 Phủ đoạn 1
    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
    theo bạn khi đã sắp xếp lại rồi mình làm cách nào để không cần inear search

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: phủ đoạn

    Trước tiên, cho mình hỏi bạn sort cái gì theo thứ tự nào? Bạn nói ý tưởng ko cần code cũng đc.

  5. #5
    Ðến Từ
    Bắc Giang
    Thành Viên Thứ: 390262
    Bài gửi
    4

    Reply: phủ đoạn

    mình Sắp các đoạn tăng theo đầu phải b.

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: phủ đoạn

    Trích Nguyên văn bởi huyhung123 Xem bài viết
    mình Sắp các đoạn tăng theo đầu phải b.
    À, nếu là thế thì phải linear search thôi vì cái sort và tìm kiếm khác nhau.

  7. #7
    Ðến Từ
    Bắc Giang
    Thành Viên Thứ: 390262
    Bài gửi
    4

    Reply: phủ đoạn

    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? do?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(t,p: integer);
    var i,j,m: integer;
    x: KieuDoan;
    begin
    i := t; j := p; m := d[(i + j) div 2].b;
    while (i <= j) do
    begin
    while (d[i].b < m) do i := i + 1;
    while (m < d[j].b) do j := j - 1;
    if (i <= j) then
    begin
    x := d[i]; d[i] := d[j]; d[j] := x;
    i := i + 1; j := j - 1;
    end;
    end;
    if (t < j) then Qsort(t,j);
    if (i < p) then Qsort(i,p);
    end;


    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);
    var i: integer;
    begin
    assign(f,gn);
    rewrite(f);
    writeln(f,k);
    for i:= 1 to k do
    writeln(f,d[t[i]].id);
    close(f);
    end;


    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.
    Nguyên chương trình minhg làm đây bạn
    khi mình in ra thì kết quả như thế này
    3
    1
    3
    4