H
hai6f2009
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
026. ĐƯỜNG ĐI NHIỀU ĐIỂM NHẤT
Cho một bảng A kích thước m x n (1 [TEX]\leq [/TEX] m, n [TEX]\leq [/TEX] 100), trên đó ghi các số nguyên aij ([TEX]\| {a}_{ij} \| [/TEX] [TEX]\leq [/TEX] 100). Một
người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cung được).
Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i+ 1, j + 1).
Yêu cầu: Hãy tìm vị trí ô xuất phát và một hành trình đi từ cột 1 sang cột n sao cho tổng các số
ghi trên đờng đi là lớn nhất.
Dữ liệu: Vào từ file van bản MAX.INP. Trong đó:
• Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
• m dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải.
Kết quả: Ghi ra file van bản MAX.OUT. Trong đó:
• Dòng 1: Ghi số điểm tối đa có được
• n dòng tiếp theo, dòng thứ i ghi chỉ số hàng của ô thứ i trong hành trình.
Các số trên 1 dòng trong Input/ Output file cách nhau ít nhất 1 dấu cách
Ví dụ:
MAX.INP
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7
MAX.OUT
41
1
2
3
2
3
4
5
ĐÂY LẦ CODE CỦA MÌNH:
nhưng nó cho kq là 42 và không in đường đi. Mình tìm mãi mà vẫn chưa ra cách giải. Vậy mong các bạn hãy giúp đỡ cho mình. Mình xin cảm ơn
!
Cho một bảng A kích thước m x n (1 [TEX]\leq [/TEX] m, n [TEX]\leq [/TEX] 100), trên đó ghi các số nguyên aij ([TEX]\| {a}_{ij} \| [/TEX] [TEX]\leq [/TEX] 100). Một
người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cung được).
Quy tắc đi: Từ ô (i, j) chỉ được quyền sang một trong 3 ô (i, j + 1); (i - 1, j + 1); (i+ 1, j + 1).
Yêu cầu: Hãy tìm vị trí ô xuất phát và một hành trình đi từ cột 1 sang cột n sao cho tổng các số
ghi trên đờng đi là lớn nhất.
Dữ liệu: Vào từ file van bản MAX.INP. Trong đó:
• Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.
• m dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải.
Kết quả: Ghi ra file van bản MAX.OUT. Trong đó:
• Dòng 1: Ghi số điểm tối đa có được
• n dòng tiếp theo, dòng thứ i ghi chỉ số hàng của ô thứ i trong hành trình.
Các số trên 1 dòng trong Input/ Output file cách nhau ít nhất 1 dấu cách
Ví dụ:
MAX.INP
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7
MAX.OUT
41
1
2
3
2
3
4
5
ĐÂY LẦ CODE CỦA MÌNH:
Mã:
[FONT=Arial][SIZE=3]program timduongdi;
const fi='max.inp';
fo='max.out';
var f:text;
n,m,cs,max:integer;
a,b:array[0..100,0..100] of integer;
c,p,s:array[1..100] of integer;
procedure enter;
var i,j:integer;
begin
assign(f,fi);
reset(f);
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function maxnumber(x,y,z:integer):integer;
begin
if (x>y) and( x>z) then maxnumber:=x
else if y>z then maxnumber:=y
else maxnumber:=z;
end;
procedure optimize;
var i,j:integer;
begin
b[1,1]:=a[1,1];
for i:=1 to n do
begin
b[0,i]:=0;
b[i,n+1]:=0;
end;
for i:=1 to m do
begin
b[i,0]:=0;
b[m+1,i]:=0;
end;
for i:=2 to m do b[i,1]:=a[i,1]+b[i-1,1];
for j:=2 to n do b[1,j]:=a[1,j]+b[j-1,1];
for i:=2 to m do
for j:=2 to n do
b[i,j]:=maxnumber(b[i,j-1],b[i+1,j-1],b[i,j-1])+a[i,j];
end;
procedure trace;
var i,j,k:integer;
begin
max:=b[m,1];
for j:=1 to n do
if b[m,j]> max then
begin
k:=b[m,j];
cs:=j;
end;
i:=m; j:=cs; c[i]:=j;
while i>1 do
begin
k:=b[i,j];
dec(i);
s[i]:=i;
c[i]:=k;
j:=k;
p[i]:=k;
end;
end;
procedure printresult;
var i,j:integer;
begin
assign(f,fo);rewrite(f);
writeln(f,b[m,n]);
for i:=1 to n do
write(f,p[i],' ');
close(f);
end;
BEGIN
enter;
optimize;
trace;
printresult;
END.[/SIZE][/FONT]
Last edited by a moderator: