phủ đoạn

HTML: 
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 ạ
 
T

tengiday

Happy life
- 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.
[ah]
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;
[/ah]
 
Sửa lần cuối:
H

huyhung123

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
 
T

tengiday

Happy life
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.
 
H

huyhung123

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.a,d.b);
d.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.b < m) do i := i + 1;
while (m < d[j].b) do j := j - 1;
if (i <= j) then
begin
x := d; d := 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.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].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
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Bài viết đang hot

Thống kê

Chủ đề
100,587
Bài viết
467,311
Thành viên
339,810
Thành viên mới nhất
thanhnttg00017

Bài viết được quan tâm nhiều

Top