Tin học đường đi tốt nhất

[bùi thị xuân mai]

[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.

Bài 4: Đường đi tốt nhất:
Sân chơi là một mặt phẳng chia ra thành N hàng đánh số từ 1 đến N (1<N<100).Ở hàng thứ i (1≤ i ≤ N) có i ô điểm có giá trị cho trước là những số nguyên dương (không vượt quá 1000). Trò chơi là chọn một lộ trình với ô xuất phát là ô ở hàng thứ nhất, lần lượt đi qua một trong 2 ô lân cận ở hàng tiếp theo (theo hướng mũi tên) cho đến khi đến được một ô ở hàng cuối cùng và thu nhặt các điểm số có ở các ô trên đường đi qua (lộ trình sẽ thăm đúng N ô) (Hình vẽ dưới minh họa cho một ví dụ với N=4).
Cho trước một bảng biểu thị giá trị điểm số các ô trên từng hàng. Hãy lập trình tìm một lộ trình hợp quy định của luật chơi và thu được điểm số cao nhất.
Dữ liệu vào là tệp DUONGDI.INP có cấu trúc như sau:
- Dòng thứ nhất chứa số tự nhiên N;
- N dòng tiếp theo sẽ chứa các giá trị điểm số trên các ô điểm ở dòng tương ứng. Dòng thứ i sẽ có i giá trị.Các giá trị cách nhau một khoảng trắng.
Dữ liệu ra là tệp DUONGDI.OUT gồm 2 dòng:
- Dòng thứ nhất chứa giá trị tổng điểm lớn nhất thu được theo lộ trình tối ưu;
- Dòng thứ 2 chứa N số nguyên là giá trị các ô điểm mà lộ trình tối ưu đi qua.

			8
		5		1
	2		6		9
3		4		2		3

[TBODY] [/TBODY]

Ví dụ:

DUONGDI.INP		DUONGDI.OUT
4 8 5 1 2 6 9 3 4 2 3		23 8 5 6 4

[TBODY] [/TBODY]

Chú ý:Nếu chỉ nêu được số điểm lớn nhất mà không chỉ được lộ trình đi thì được ½ số điểm của bài.

 

[chơn nhân (boy)]

USES MATH;
var a,b: array[0..100,0..100] of integer;
c: array[0..100] of integer;
imax,m,i,j,n,min,d: integer;
f,g: text;
procedure nhap;
var i,j : integer;
begin
assign(f,'duongdi.inp'); reset(f);
assign(g,'duongdi.out'); rewrite(g);
readln(f,n);
for i:=1 to n do
for j:=1 to i do
read(f,a[i,j]);
end;
procedure loang;
begin
for i:=1 to n do begin b[i,0]:=-1; b[i,i+1]:=-1; end;
b[1,1]:=a[1,1];
//writeln(b[1,1]);
for i:=2 to n do
begin
for j:=1 to i do
begin
b[i,j]:=max(b[i-1,j-1],b[i-1,j])+a[i,j];
//write(b[i,j]:3);
end;
//writeln;
end;
end;
procedure truyvet;
begin
imax:= b[n,1];
for i:=1 to n do
if b[n,i]> imax then begin imax:= b[n,i];j:=i end;
//writeln(g,imax);
m:=n;
c[m]:=a[n,j];
while i>0 do
begin
if b[i,j]=(b[i-1,j-1])+a[i,j]then dec(j); dec(i);
dec(m); c[m]:=a[i,j];
end;
end;
BEGIN
NHAP;
LOANG;
TRUYVET;
writeln(g,imax);
for i:=1 to n do write(g,c,' ');
close(f);
close(g);
END.

 

[chơn nhân (boy)]

USES MATH;
var a,b: array[0..100,0..100] of integer;
c: array[0..100] of integer;
imax,m,i,j,n,min,d: integer;
f,g: text;
procedure nhap;
var i,j : integer;
begin
assign(f,'duongdi.inp'); reset(f);
assign(g,'duongdi.out'); rewrite(g);
readln(f,n);
for i:=1 to n do
for j:=1 to i do
read(f,a[i,j]);
end;
procedure loang;
begin
for i:=1 to n do begin b[i,0]:=-1; b[i,i+1]:=-1; end;
b[1,1]:=a[1,1];
//writeln(b[1,1]);
for i:=2 to n do
begin
for j:=1 to i do
begin
b[i,j]:=max(b[i-1,j-1],b[i-1,j])+a[i,j];
//write(b[i,j]:3);
end;
//writeln;
end;
end;
procedure truyvet;
begin
imax:= b[n,1];
for i:=1 to n do
if b[n,i]> imax then begin imax:= b[n,i];j:=i end;
//writeln(g,imax);
m:=n;
c[m]:=a[n,j];
while i>0 do
begin
if b[i,j]=(b[i-1,j-1])+a[i,j]then dec(j); dec(i);
dec(m); c[m]:=a[i,j];
end;
end;
BEGIN
NHAP;
LOANG;
TRUYVET;
writeln(g,imax);
for i:=1 to n do write(g,c,' ');
close(f);
close(g);
END.

 

[chơn nhân (boy)]

USES MATH;
var a,b: array[0..100,0..100] of integer;
c: array[0..100] of integer;
imax,m,i,j,n,min,d: integer;
f,g: text;
procedure nhap;
var i,j : integer;
begin
assign(f,'duongdi.inp'); reset(f);
assign(g,'duongdi.out'); rewrite(g);
readln(f,n);
for i:=1 to n do
for j:=1 to i do
read(f,a[i,j]);
end;
procedure loang;
begin
for i:=1 to n do begin b[i,0]:=-1; b[i,i+1]:=-1; end;
b[1,1]:=a[1,1];
//writeln(b[1,1]);
for i:=2 to n do
begin
for j:=1 to i do
begin
b[i,j]:=max(b[i-1,j-1],b[i-1,j])+a[i,j];
//write(b[i,j]:3);
end;
//writeln;
end;
end;
procedure truyvet;
begin
imax:= b[n,1];
for i:=1 to n do
if b[n,i]> imax then begin imax:= b[n,i];j:=i end;
//writeln(g,imax);
m:=n;
c[m]:=a[n,j];
while i>0 do
begin
if b[i,j]=(b[i-1,j-1])+a[i,j]then dec(j); dec(i);
dec(m); c[m]:=a[i,j];
end;
end;
BEGIN
NHAP;
LOANG;
TRUYVET;
writeln(g,imax);
for i:=1 to n do write(g,c,' ');
close(f);
close(g);
END.