Đội ôn thi tin học trẻ không chuyên năm 2012

Status
Không mở trả lời sau này.
M

mikelhpdatke

Bạn thiếu cơ sở QHĐ.
F[1,j]:=W với j chạy từ 1->m.
F[i,j]:=F[i-1,j]+W với i chạy từ 2->n
 
Q

quanghero100

thiennu274 said:
Mình có bài này:
Bài toán con kiến
Trên một sân hình chữ nhật mxn, được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua sân đến dòng thứ m để lấy thức ăn trong ô.
Con kiến chỉ có thể đi mỗi lần một ô (hoặc ngang, hoặc xuống). Hãy chỉ ra đường đi để con kiến có được lượng thức ăn nhiều nhất.
Bài này là QHĐ mảng 2 chiều ấy. Bạn nào up code lên dùm mình
Thanks nhìu
Bấm để xem đầy đủ nội dung ...

hjhj bài này gần giống bài 2 trong đề thi tin học trẻ lần 10 tỉnh anh khối THPT, chỉ có điều cái kia là ma trận vuông còn ma trạn này kích thước mxn việc sửa lại không khó
Dưới đây là code tham khảo(chương trình đọc vào và xử lí cùng lúc nhìu ma trân mỗi ma trận cách nhau một dòng ******) ví dụ:
ở file input:
3
5 5 6
7 4 5
8 4 5
*********
4
7 4 5 7
1 5 4 2
8 7 4 5
3 6 5 4
********
2
7 8
6 4
*******
Mã: 
uses crt;
var a,b:array[0..100,0..100] of integer;
    c:array[0..100,0..100] of boolean;
    n,i,j:integer;
    f1,f2:text;
function max(b,a:integer):integer;
begin
  if a<=b then max:=b else max:=a;
end;
procedure QHD;
var i,j:integer;
begin
  fillchar(b,sizeof(b),0);
  for i:=1 to n do
    begin
      b[1,i]:=a[1,i]+b[1,i-1];
      b[i,1]:=a[i,1]+b[i-1,1];
    end;
  for i:=2 to n do
    for j:=2 to n do
        b[i,j]:=max(b[i-1,j],b[i,j-1])+a[i,j];
  writeln(f2,b[n,n]);
end;
procedure truyvet;
var i,j:integer;
begin
  fillchar(c,sizeof(c),true);
  i:=n;
  j:=n;
  c[n,n]:=false;
  repeat
      if (j>1) and (b[i,j-1]=max(b[i-1,j],b[i,j-1])) then
       begin
          dec(j);
          c[i,j]:=false;
       end;
     if (i>1) and (b[i-1,j]=max(b[i-1,j],b[i,j-1])) then
       begin
          dec(i);
          c[i,j]:=false;
       end;

  until (i=1) and (j=1);
  for i:=1 to n do
    for j:=1 to n do
      if c[i,j]=false then write(f2,'(',i,',',j,') ');
  writeln(f2);
  writeln(f2,'*********');
end;
begin
  assign(f1,'BAI2.INP');
  reset(f1);
  assign(f2,'BAI2.OUT');
  rewrite(f2);
  while not eof(f1) do
    begin
       readln(f1,n);
       for i:=1 to n do
         begin
           for j:=1 to n do
             read(f1,a[i,j]);
           readln(f1);
         end;
       readln(f1);
       QHD;
      truyvet;
    end;
  close(f2);
  close(f1);
end.
À quên đây là bài tìm đường đi có tổng lớn nhất từ ô (1;1) đến ô (n,n) nhớ điều chỉnh lại nha:D
 
Last edited by a moderator:
M

mikelhpdatke

Anh làm thuật j` thế, a post thuật toán lên đi chứ để thế này e đọc ko hiểu :-S :))
 
M

mikelhpdatke

Ah e hỏi a chút
Cái thuật của e dùng cơ sở là
F[1,j]:=W với j chạy từ 1->m.
F[i,j]:=F[i-1,j]+W với i chạy từ 2->n

Nhưng để chắc e nghĩ nên tạo viền cho bảng phương án đề tránh lỗi ra ngoài mảng.Khởi tạo viền với 1 giá trị đặc biệt sẽ tối ưu hơn.
Tuy nhiên đây cũng chỉ là 1 cách cho chắc chắn, có thể lược bỏ. Anh thấy thế nào :-/
P/s: Vote +1 đi a :))
 
M

mikelhpdatke

Bây giờ có a starlove_maknae_kyuhyun, và cuong276.
Mà sao ko thấy bác trong mục Mod của box thế :-?
 
Q

quanghero100

mikelhpdatke said:
Ah e hỏi a chút
Cái thuật của e dùng cơ sở là
F[1,j]:=W với j chạy từ 1->m.
F[i,j]:=F[i-1,j]+W với i chạy từ 2->n

Nhưng để chắc e nghĩ nên tạo viền cho bảng phương án đề tránh lỗi ra ngoài mảng.Khởi tạo viền với 1 giá trị đặc biệt sẽ tối ưu hơn.
Tuy nhiên đây cũng chỉ là 1 cách cho chắc chắn, có thể lược bỏ. Anh thấy thế nào :-/
P/s: Vote +1 đi a :))
Bấm để xem đầy đủ nội dung ...


Đoạn code sau chính là cái viền trong code của anh mà em nói nè, đó cũng chính là cơ sở quy hoạch động đó
Mã: 
for i:=1 to n do
    begin
      b[1,i]:=a[1,i]+b[1,i-1];
      b[i,1]:=a[i,1]+b[i-1,1];
    end;
 
Status
Không mở trả lời sau này.
Top Bottom