Trang chủ Tin Học Lớp 10 Cho một ma trận vuông kích thước N*M chỉ chứa...

Cho một ma trận vuông kích thước N*M chỉ chứa các số nguyên không âm. Ban đầu đặt một robot ở ô (1,1), yêu cầu tìm đường đi đến ô (N, M) sao cho chi phí thu đư

Câu hỏi :

Cho một ma trận vuông kích thước N*M chỉ chứa các số nguyên không âm. Ban đầu đặt một robot ở ô (1,1), yêu cầu tìm đường đi đến ô (N, M) sao cho chi phí thu được là nhỏ nhất. Biết rằng, tại ô (i, j) chỉ được đi sang ô (i+1, j) hoặc (i, j+1). Chi phí của đường đi được xác định bằng số chữ số 0 tận cùng của tích các số trên đường đi. Input: - Dòng đầu tiên chứa số nguyên N, M (N, M ≤ 1000) là kích thước của ma trận - N dòng tiếp theo, mỗi dòng chứa M số nguyên không âm và không vượt quá 109 Output: Một số nguyên duy nhất là chi phí của đường đi nhỏ nhất tìm được. Ví dụ: Input: 4 3 1 2 3 4 5 6 7 8 9 10 11 12 Output: 0 Giải thích: các cách đi thu được chi phí là 0: - 1 → 2 → 3 → 6 → 9 → 12, 1*2*3*6*9*12 = 3888 - 1 → 4 → 7 → 8 → 9 → 12, 1*4*7*8*9*12 = 24192 - 1 → 4 → 7 → 8 → 11 → 12, 1*4*7*8*11*12 = 29568

Lời giải 1 :

uses crt;
var fi,fo:text;
    n,m,i,j:integer;
a,b:array[-1..200,-1..200] of int64;

procedure taotep;
        begin
                assign(fi,'ChiPhi.inp');
                {$I-} reset(fi); {$I+}
                if ioresult<>0 then
                begin
                        rewrite(fi);
                        reset(fi);
                end;
                readln(fi,n,m);
                for i:=1 to n do
                begin
                        for j:=1 to m do read(fi,a[i,j]);
                        readln(fi);
                end;
                close(fi);
        end;

function min(x,y:int64):int64;
        begin
                min:=x;
                if y<x then min:=y;
        end;

procedure taomang;
        begin
                b[1,1]:=a[1,1];
                for i:=0 to n do b[i,0]:=999999999;
                for j:=0 to m do b[0,j]:=999999999;
                for j:=1 to m do
                        for i:=1 to n do
                        if (i<>1) or (j<>1) then
                                b[i,j]:=min(b[i-1,j],b[i,j-1])*a[i,j];
        end;

procedure truyvet(i,j:integer);
        begin
                if (i>1) or (j>1) then
                begin
                        if b[i-1,j]=min(b[i-1,j],b[i,j-1]) then truyvet(i-1,j)
                        else truyvet(i,j-1);
                end;
                write(a[i,j],' ');
        end;

BEGIN
        clrscr;
        taotep; taomang;
        writeln('Chi phi toi thieu la:',b[n,m]);
        write('Duong di la:');
        truyvet(n,m);
        readln
END.

Mình dùng cách quy hoạch động, dữ liệu vào ở tệp 'ChiPhi.inp', kết quả ghi ra màn hình.

Chúc bạn học tốt.

Cho mik xin ctlhn.

Thảo luận

Bạn có biết?

Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.

Nguồn : Wikipedia - Bách khoa toàn thư

Tâm sự 10

Lớp 10 - Năm thứ nhất ở cấp trung học phổ thông, năm đầu tiên nên có nhiều bạn bè mới đến từ những nơi xa hơn vì ngôi trường mới lại mỗi lúc lại xa nhà mình hơn. Được biết bên ngoài kia là một thế giới mới to và nhiều điều thú vị, một trang mới đang chò đợi chúng ta.

Nguồn : ADMIN :))

Liên hệ hợp tác hoặc quảng cáo: gmail

Điều khoản dịch vụ

Copyright © 2021 HOCTAPSGK