Đăng Nhập

Vui lòng khai báo chính xác tên truy cập và mật khẩu!

Quên mật khẩu?

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

Share
    Xếp
    avatar

    Giới tính : Nữ

    Tuổi : 25

    Đến từ : HCM

    Ngày Tham gia : 13/06/2011

    Tổng số bài gửi : 380

    #1

     on Thu Oct 13, 2011 12:23 am

    Cho một bảng ô vuông m dòng, n cột (2<=n,m<=30) các ô ghi các số là 0 hoặc 1. Tìm đường đi của robot, từ góc trái trên (ô (1,1)) xuống góc phải (ô (m, n)) dưới theo nguyên tắc chỉ được dịch chuyển sang phải và xuống dưới sao cho các số trên đường đi tạo thành một số nhị phân có giá trị lớn nhất.
    Dữ liệu vào: ghi trong tệp tin văn bản Robot.inp gồm
    - Dòng đầu tiên ghi giá trị m và n
    - M dòng tiếp theo, trên mỗi dòng ghi n số 0 hoặc 1 các số này cách nhau ít nhất 1 khoảng trống.
    Dữ liệu ra: Ghi vào tập tin văn bản robot.out gồm
    - Dòng đầu tiền ghi giá trị thập phân của số nhị phân được tạo thành ở trên.
    - Các dòng tiếp theo ghi tọa độ các bước đi (dòng ghi trước, cột ghi sau).
    Ví dụ:
    Robot.inp robot.out
    5 5
    1 0 1 1 0
    0 0 1 0 1
    0 0 1 0 1
    1 0 0 1 1
    1 1 0 1 0
    374
    1 2
    1 3
    2 3
    3 3
    3 4
    3 5
    4 5
    5 5

    1. Công thức truy hồi:
    Gọi F[i,j] là giá trị thập phân của số nhị phân lớn nhất bằng cách đi từ ô (1,1) tới ô (i,j).
    Khi thêm một chữ số 0 hoặc 1 vào cuối một số nhị phân thì ta sẽ được giá trị mới là:
    2 * (giá trị cũ) + (số thêm).
    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; i<=m; i++)
    {
    for (j=1; j<=n; j++)
    fi>>A[i][j];
    fi.ignore();
    }
    for (i=0; i<=m; i++) A[i][0]=-1;
    for (j=0; j<=n; j++) A[0][j]=-1;
    }

    int Max(int a, int b)
    {
    return (a>b)?a:b;
    }

    void Optimize()
    {
    int i,j;
    for (i=0; i<=m; i++) F[i][0]=-1;
    for (j=0; j<=n; j++) F[0][j]=-1;
    F[1][0]=0;
    for (i=1; i<=m; i++)
    for (j=1; j<=n; j++)
    F[i][j] = 2 * Max(F[i][j-1],F[i-1][j]) + A[i][j];
    }

    void Trace(int i, int j)
    {
    if ( i==1 && j==1)
    fo<<F[m][n]<<endl;
    else
    {
    if (F[i-1][j]>F[i][j-1])
    Trace(i-1,j);
    else
    Trace(i,j-1);
    fo<<i<<" "<<j<<endl;
    }
    }
    void main()
    {
    Enter();
    Optimize();
    Trace(m,n);

    fi.close();
    fo.close();
    }