Bài toán tìm tổng lớn nhất trong tam giac
|
Cho ma trận A hình vuông có kích thước n*n. Đầu tiên bạn ở ô có tọa độ [1,1], bạn được phép đi sang phải và đi xuống dưới ô kề cạnh. Hãy tìm đường đi có tổng lớn nhất khi đi đến ô [n,n]. Show Input-Dòng đầu là số nguyên dương N (n<= 1000). – n dòng tiếp theo, mỗi dòng gồm n số nguyên dương biểu diễn ma trận A. Output– một dòng duy nhất là kết quả bài toán. Bài này mình viết để các bạn tham khảo một dạng QHĐ cơ bản, nên về dữ liệu mình không yêu cầu A[i,j] có giới hạn bao nhiêu, và nhiều dữ kiện khác. Ví dụInput 4 9 2 3 4 9 0 2 2 9 9 9 2 2 2 9 9 Output 63 – Gọi F[i,j] là tổng lớn nhất có được khi đi đến ô i,j. – Khởi tạo F[i,0]=F[0,j]=0; – Có 2 cách đi đến ô [i,j], một là đi từ trên xuống, hai là từ phải qua, như vậy ta có công thức lần lượt là F[i-1,j] và F[i,j-1]
ii) Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu. Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau. 2. Công thức QHĐ
Hàm mục tiêu : f = độ dài dãy con.
Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phươngán là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a 1 đến a i và phần tử cuối cùng là a i .
Nhận xét với cách làm này ta đã chia 1 bài toán lớn(dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn(dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
Ta có công thức QHĐ để tính L(i) như sau:
• L(1) = 1.(Hiển nhiên)
• L(i) = max(1, L(j)+1 với mọi phần tử j: 0 3. Cài đặt
Bảng phươngán là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau: Như vậy chi phí không gian của bài toán là O(n), chi phí thời gian là O(n2 ). Có một phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời gian là O(nlogn) Cho một bảng ~A~ kích thước ~m × n~ (~m~ dòng, ~n~ cột), trên đó ghi các số nguyên ~a_{ij}~. 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 đi:Từ ô ~(i, j)~ chỉ được quyền sang một trong ~3~ ô ~(i, j + 1); (i - 1, j + 1); (i + 1, j + 1)~. TAM GIÁC SỐ (Câu 4. Hội thi Tin Học Trẻ Phú Yên lần thứ XIX - năm 2016) 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Cho một tam giác gồm các số nguyên không âm (xem hình trên). Hãy viết chương trình tính tổng lớn nhất của các số nằm trên lộ trình từ đỉnh xuống: - Tại mỗi bước đi, lộ trình có thể đi xuống phía bên trái hoặc xuống phía bên phải. - Số hàng trong tam giác lớn hơn 1 và nhỏ hơn 100 - Các số nằm trong tam giác đều là số nguyên trong đoạn từ 0 đến 99. Dữ liệu vào: câu4.inp Dòng đầu tiên chứa số dòng trong tam giác, các dòng tiếp theo chứa các số trên các hàng đó. ví dụ: 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Kết quả: cau4.out Tổng lớn nhất các số ghi ra file cau4.out. trong ví dụ này là :30. -Thuật toán- - Sử dụng quy hoạch động để giải bài toán này - Sử dụng mảng 2 chiều A để lưu tam giác số, mảng F để thực hiện tính toán F[1,1]=A[1,1] F[i,1]=F[i-1,1]+A[i,1] F[i,j] = max(F[i-1,j-1], F[i-1,j]) + A[i,j] Đáp án: uses crt; Var A,F:array[1..100,1..100] of integer; i,j,n,max:integer; fi,fo:text; begin assign(fi,'tamgiacso.inp') ; reset(fi); assign(fo,'tamgiacso.out'); rewrite(fo); {doc du lieu tu tep vao mang 2 chieu A} readln(fi,N); readln(fi, a[1,1]); for i:=2 to N do begin for j:=1 to i do read(fi,a[i,j]); readln(fi); end; F[1,1]:=a[1,1]; for i:=2 to N do f[i,1]:=F[i-1,1]+a[i,1]; for i:=2 to N do for j:=2 to N do begin If F[i-1,j-1] > F[i-1,j] then F[i,j]:= F[i-1,j-1] +a[i,j] else F[i,j]:= F[i-1,j]+a[i,j]; end; Max:=f[n,1]; For j:= 2 to N do if max |
