Bài toán đường đi của robot tạo thành số nhị phân lớn nhất

Bài toán đường đi của robot tạo thành số nhị phân lớn nhất Cho một bảng ô vuông m dòng, n cột
Nội dung trích xuất từ tài liệu:
Bài toán đường đi của robot tạo thành số nhị phân lớn nhất Bài toán đường đi của robot tạo thành số nhị phân lớn nhấtCho một bảng ô vuông m dòng, n cột (2Ví dụ:Ta có số 1011 (giá trị thập phân là 11)+ Ghép thêm số 1 vào sẽ là 10111 (giá trị mới là 23 = 2*11+1)+ Ghép thêm số 0 vào sẽ là 10110 (giá trị mới là 22 = 2*11+0)Tại ô (i,j) chỉ có thể đến từ ô (i-1, j) hoặc ô (i, j-1), để giá trị thu được là lớn nhấtthì phải đến từ ô có giá trị lớn hơn, như vậy công thức truy hồi sẽ là: F[i, j] = 2 * max( F[i, j-1], F[i-1, j] ) + A[i, j]2. Tính bảng phương ánĐể thuận tiện ta cần đặt hàng rào: cột 0 và dòng 0 của cả A và F đều đặt giá trị -1.Riêng ô A[1, 0] hoặc A[0, 1] cần đặt giá trị 0 để bắt đầu tính thì F[1,1] = A[1, 1].3. Truy vếtBằng thủ tục đệ quy: Bắt đầu từ ô (m,n), quá trình truy vết kết thúc khi ta truy đếnđến ô (1,1) và ra giá trị F[m,n], tại mỗi bước truy vết ta sẽ truy vết ô có giá trị lớnhơn trong 2 ô: (m-1,n) và (m,n-1).Cài đặt bằng ngôn ngữ Pascal:PROGRAM robot;VAR A:ARRAY[0..30,0..30] OF BYTE; F:ARRAY[0..30,0..30] OF LONGINT; m,n:INTEGER;PROCEDURE Enter;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:=0 TO m DO A[i,0]:=-1; FOR j:=0 TO n DO A[0,j]:=-1;END;FUNCTION Max(a,b:LONGINT):LONGINT;BEGIN IF (a>b) THEN Max:=a ELSE Max:=b;END;PROCEDURE Optimize;VAR i,j:INTEGER;BEGIN FOR i:=0 TO m DO F[i,0]:=-1; FOR j:=0 TO n DO F[0,j]:=-1; F[0,1]:=0; FOR i:=1 TO m DO FOR j:=1 TO n DO F[i,j]:=2*Max(F[i,j-1],F[i-1,j])+A[i,j];END;PROCEDURE Trace(i,j:INTEGER);BEGIN IF (i=1) AND (j=1) THEN writeln(F[m,n]) ELSE BEGIN IF F[i,j-1]>F[i-1,j] THEN Trace(i,j-1) ELSE Trace(i-1,j); writeln(i, ,j); END;END;BEGIN Assign(Input,Robot.inp); Reset(Input); Assign(Output,Robot.out); Rewrite(Output); Enter; Optimize; Trace(m,n); close(Input); close(Output);END.Cài đặt bằng ngôn ngữ C++#include #include using namespace std;int F[31][31],A[31][31],m,n;ofstream fo(robot.out);ifstream fi(robot.inp);void Enter(){ fi>>m>>n; fi.ignore(); int i,j; for (i=1; iA[i][j]; fi.ignore(); } for (i=0; i F[1][0]=0; for (i=1; i