Change background image
Chuyên Tin - Lê Khiết

Go downThông điệp [Trang 1 trong tổng số 1 trang]

© FMvi.vn

on Fri Jan 27, 2012 4:46 pm
anh thy

người mới

Đề: Cho số tự nhiên N và dãy gồm N số nguyên a[1],a[2],….,a[n].Cho số nguyên S>=o.Tìm dãy con dài nhất trong dãy trên sao cho tổng của các phần tử trong dãy con dãy con này <=S.
Dữ liệu vào: TONG.INP
Dòng 1: ghi số n,s
Dòng 2:ghi N số a[1],a[2],…,a[n]
Dữ liệu ra: TONG.OUT
Dòng 1:ghi độ dài dãy con dài nhất có tổng <=S
Dòng 2:ghi các phần tử trong dãy con dài nhất có tổng <=S
*Phân tích:
Gọi L[i,j] là độ dài của dãy con dài nhất
Khi xét phần tử từ ví trí 1 đến I mà có Z các phần tử trong dãy con <=j
-BCS:
Nếu i=0 (dãy a không có phần tử nào) nên L[0,j]=0 với mọi j=0,S
Nếu dãy a có 1 phần tử nên i=1
Nếu a[i]<=j thì L[1,j]=1
Nếu a[i]>j thì L[1,j]=0
-Xây dựng bảng:Tính L[i,j] với mọi i=2,n;với mọi j=0,S;
* Chọn số thứ I vào dãy con:
L[i,j]=L[i-1,j-a[i]]
*không chọn số thứ i:
L[i,j]=L[i-1,j]
-Truy vết:
Kết dòng i: L[N,S]
I=N;j=S;
Chừng nào còn số trong dãy làm
Begin
Nếu L[i,j]=L[i-1,j] thì không chọn số
Ngược lại
+chọn số i
+ tổng còn lại
+giảm i

Ví dụ:
TONG.INP
5 10
3 4 7 1 8
TONG.OUT
3
3 4 1
BẢNG
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 2 2 2 2
0 0 0 1 1 1 1 2 2 2 2
0 1 1 1 2 2 2 2 3 3 3
0 1 1 1 2 2 2 2 3 3 3

CHƯƠNG TRÌNH:
program tong;
const fi='TONG.INP';fo='TONG.OUT';
var N,S,i,j:integer;f:text;
L:array[0..100,0..100] of integer;
A:array[1..100] of integer;
DD:array[1..100] of boolean;
procedure doc;
begin
assign(f,fi);reset(f);
readln(f,N,S);
for i:=1 to N do read(f,a[i]);
close(f);
assign(f,fo);rewrite(f);
end;

procedure khoitao;
begin
Fillchar(l,sizeof(l),0);
For j:=0 to s2 do
If a[1]<=j then
[1,j]:=1
else
l[1,j]:=0;

end;


procedure xdbang;
begin
for i:=2 to N do
for j:=1 to S do
Begin
l[i,j]:=l[i-1,j];
If j-a[i]>=0 then
If l[i,j]<(1+l[i-1,j-a[i]) then
l[i,j]:=1+l[i-1,j-a[i]);
End;
end;

procedure truyvet;
begin
writeln(f,L[n,s]);
i:=n; j:=s;
while i>0 do
begin
if L[i,j]=L[i-1,j] then dec(i)
else
begin
dd[i]:=true;j:=j-a[i];
dec(i);
end;
for i:=1 to N do
if dd[i]=true then write(f,a[i],' ');
end;
end;
BEGIN
Fillchar(dd,sizeof(dd),false);
doc;khoitao;xdbang;truyvet;
END.
Bài trên làm sai rồi bạn tải bài của mình về tham khảo đi Link nè : [You must be registered and logged in to see this link.]

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà anh thy
Trả lời nhanh
on Fri Jan 27, 2012 4:55 pm
anh thy

người mới

Bài tập 5: CHIA ĐẤT
Một người nông dân có thửa ruộng HCN kích thước NxM, ông ta phân chia ruộng cho k người con đánh số từ 1 đến k( k<=10)
Việc phân chia thực hiện như sau: thửa ruộng được phân thành từng ô vuông có cạnh = 1 đơn vị độ dài. Ban đầu, mỗi người con nhận được trước 1 ô vuông, ko có trường hợp 2 người cùng nhận chung một ô và ko có trường hợp 2 người nhận ô vuông ban đầu có giá trị = nhau. Sau đó ở mỗi lượt, lần lượt mỗi người con theo số hiệu từ nhỏ đến lớn, nhậ tiếp các ô vuông chưa có ai nhận có giá trị = giá trị ô nhận ban đầu và kề cạnh với một trong các ô thuộc sở hữu của mình.
Hãy xác định diện tích nhận được của mỗi người.
DL vào: CHIADAT.INP
Dòng 1: ghi 3 số N,M,k
K dòng tiếp theo mỗi dòng gồm 2 số nguyên dương chỉ tọa độ ô của người con nhận.
Dòng thứ i trong N dòng tiếp theo, mỗi dòng ghi M số nguyên dương <=200.
DL ra: CHIADAT.OUT
Ghi k số: số thứ i trong k số là diện tích người con thứ i nhận được
Ví dụ:
CHIADAT.INP
4 7 3
1 2
3 6
4 3
CHIADAT.INP
11 12 5
------------
bảng :
1 1 1 1 1 2 2
1 1 1 1 2 2 2
1 1 3 2 2 2 2
3 3 3 3 2 2 2
CHƯƠNG TRÌNH:
Code:

program chiadat;
const fi='chiadat.inp';fo='chiadat.out';
      vx:array[1..4] of integer=(0,0,-1,1);
      vy:array[1..4] of integer=(-1,1,0,0);
var  m,n,k,x,y,s,d,c:integer;f:text;
      a:array[1..100,1..100] of integer;
      qx,qy,gx,gy:array[1..100] of integer;
procedure doc;
var i,j,z:integer;
begin
    assign(f,fi);reset(f);
    readln(f,n,m,k);
    for z:=1 to k do readln(f,gx[z],gy[z]);
    for i:=1 to n do
      begin
      for j:=1 to m do read(f,a[i,j]);
      end;
    readln(f);
    close(f);
end;
procedure hdrong;
begin
       
    d:=1;c:=0;
end;
function nt(x,y:integer):boolean;
begin
    if (x>=1)and(x<=n)and(y>=1)and(y<=m) then
      nt:=true else nt:=false;
end;
procedure them(x,y:integer);
begin
    inc(c);qx[c]:=x;qy[c]:=y;
end;
procedure lay(var x,y:integer);
begin
    x:=qx[d];y:=qy[d];inc(d);
end;
procedure loang(x,y:integer;var s:integer);
var i,x1,y1,t:integer;
begin
    hdrong;them(x,y);t:=a[x,y];a[x,y]:=0;
    while d<=c do
    begin
      lay(x,y);
      for i:=1 to 4 do
      begin
      x1:=x+vx[i];
      y1:=y+vy[i];
      if nt(x1,y1) and (a[x1,y1]=t) then
        begin
        them(x1,y1);
        inc(s);a[x1,y1]:=0;
        end;
      end;
    end;
end;
procedure ghi;
var i,j,z:integer;
begin
    assign(f,fo);rewrite(f);
    for i:=1 to n do
    for j:=1 to m do
    begin
      s:=1;
      for z:=1 to k do
      if (i=gx[z]) and (j=gy[z]) then
      begin
        loang(i,j,s);
        write(f,s,' ');
      end;
    end;
end;

BEGIN
    doc;ghi;close(f);
END.

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà anh thy
Trả lời nhanh

Về Đầu TrangThông điệp [Trang 1 trong tổng số 1 trang]

  © FMvi.vn

|_-Diễn Đàn Tin Học - Lê Khiết-_|

« Xem bài trước | Xem bài kế tiếp »

Bài viết liên quan

    Quyền hạn của bạn:

    Bạn không có quyền trả lời bài viết