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

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

Thêm vào BST

Báo xấu

354
lượt xem 22
download

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

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

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 đườ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 (2
Ví 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ất thì 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ết Bằ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ớn hơ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