Bài toán di chuyển từ Tây sang Đông

Chia sẻ: Abcdef_45 Abcdef_45 | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

362
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cho một bảng A kích thước m x n, trên đó ghi các số nguyên. 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 cũng được). Quy tắc: Từ ô A[i, j] chỉ được quyền sang một trong 3 ô A[i, j + 1]; A[i - 1, j + 1]; A[i + 1, j + 1]. Hãy tìm vị trí ô xuất phát và 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán di chuyển từ Tây sang Đông

Bài toán di chuyển từ Tây sang Đông Cho một bảng A kích thước m x n, trên đó ghi các số nguyên. 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 cũng được). Quy tắc: Từ ô A[i, j] chỉ được quyền sang một trong 3 ô A[i, j + 1]; A[i - 1, j + 1]; A[i + 1, j + 1]. Hãy tìm vị trí ô xuất phát và 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. Gợi ý: Gọi B[i, j] là số điểm lớn nhất có thể có được khi tới ô A[i, j]. Rõ ràng đối với những ô ở cột 1 thì B[i, 1] = A[i, 1]: Với những ô (i, j) ở các cột khác. Vì chỉ những ô (i, j – 1), (i – 1, j – 1), (i + 1, j – 1) là có thể sang được ô (i, j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần B[i, j] là số điểm lớn nhất có thể nên B[i, j] = max(B[i, j - 1], B[i - 1, j - 1], B[i + 1, j - 1]) + A[i, j]. Ta dùng công thức truy hồi này tính tất cả các
B[i, j]. Cuối cùng chọn ra B[i, n] là phần tử lớn nhất trên cột n của bảng B và từ đó truy vết tìm ra đường đi nhiều điểm nhất. Cài đặt bằng ngôn ngữ Pascal: PROGRAM tay_dong; CONST Max = 2000000000; VAR A,B,T:ARRAY[0..101,1..100] OF LONGINT; Tong:LONGINT; m,n,dongcuoi:INTEGER; PROCEDURE Nhap; VAR i,j:INTEGER; BEGIN readln(m,n); FOR i:=1 TO m DO BEGIN FOR j:=1 TO n DO read(A[i,j]); readln; END; FOR i:=1 TO n DO END;
FUNCTION Min(i,j:INTEGER):INTEGER; VAR m:INTEGER; BEGIN m:=i-1; IF B[i,j-1] < B[m,j-1] THEN m:=i; IF B[i+1,j-1] < B[m,j-1] THEN m:=i+1; Min:=m; END; PROCEDURE Taobang; VAR i,j,d:INTEGER; BEGIN FOR j:=1 TO n DO BEGIN B[0,j]:=Max; B[m+1,j]:=Max; END; FOR i:=1 TO m DO B[i,1]:=A[i,1];
FOR j:=2 TO n DO FOR i:=1 TO m DO BEGIN d:=min(i,j); B[i,j]:=B[d,j-1]+A[i,j]; T[i,j]:=d; END; tong:=B[1,n]; dongcuoi:=1; FOR i:=2 TO m DO IF tong>B[i,n] THEN BEGIN tong:=B[i,n]; dongcuoi:=i; END; END; PROCEDURE TruyVet(dong,cot:INTEGER);
BEGIN IF cot=0 THEN writeln(tong) ELSE BEGIN TruyVet(T[dong,cot],cot-1); write(dong,' '); END; END; BEGIN assign(Input,'input.inp'); reset(Input); assign(Output,'Output.out'); rewrite(Output); Nhap; Taobang; TruyVet(dongcuoi,n); close(Input);
close(Output); END. Cài đặt bằng ngôn ngữ C++ #include #include using namespace std; #define MAX 100 #define MAXINT 2000000000 ifstream fi("Input.inp"); ofstream fo("Output.out"); int A[MAX+2][MAX+1],B[MAX+2][MAX+1],T[MAX+2][MAX+1],m,n,R,sum; void Enter() { fi>>m>>n; int i,j;
for (i=1; iA[i][j]; fi.ignore(); } } int Min(int i, int j) { int m=i-1; if (B[i][j-1]
for (i=1; i
void Trace(int i, int j) { if (i==0) fo