Violet
Dethi

Tin tức thư viện

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

12099162 Kính chào các thầy, cô. Khi cài đặt phần mềm , trên PowerPoint và Word sẽ mặc định xuất hiện menu Bộ công cụ Violet để thầy, cô có thể sử dụng các tính năng đặc biệt của phần mềm ngay trên PowerPoint và Word. Tuy nhiên sau khi cài đặt phần mềm , với nhiều máy tính sẽ...
Xem tiếp

Quảng cáo

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (024) 66 745 632
  • 096 181 2005
  • contact@bachkim.vn

Tìm kiếm Đề thi, Kiểm tra

Đề thi chọn HSG

Wait
  • Begin_button
  • Prev_button
  • Play_button
  • Stop_button
  • Next_button
  • End_button
  • 0 / 0
  • Loading_status
Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Nguyễn Thiện Thùy
Ngày gửi: 14h:45' 23-05-2020
Dung lượng: 59.0 KB
Số lượt tải: 120
Số lượt thích: 0 người
1. Dạng 1:
- Đi từ điểm [1,1] đến [m,n]:
(Đi từ ô đầu tiên đến ô cuối cùng của mảng 02 chiều)
- Yêu cầu: Tổng giá trị tại vị trí ô [i,j] là lớn nhất (nhỏ nhất)
- Quy luật di chuyển:
Từ ô [1,1], đi theo hướng xuống dưới hoặc sang phải đến ô cuối cùng [m,n]
A[i,j]
(
A[i,j+1]

(



A[i+1,j]



Ví dụ:
Duongdi.inp
Duongdi.out


Giá trị Max
Giá trị Min

3 3
12 11 15
4 6 9
-12 25 -4
50
12 11 6 25 -4
25
12 4 -12 25 -4


Thuật toán
Gọi F[i,j] là giá trị lớn (nhỏ) nhất của cách đi theo quy luật đến ô [i,j]
Theo cách đi (đi từ ô đầu tiên [1,1]) nên ta có: F[1,1]:=A[1,1]
Để đạt được giá trị F[i,j] ta cần xét theo yêu cầu:
+ Lớn nhất:
F[i,j]:=F[i,j-1] + A[i,j] nếu F[i,j-1] > F[i-1,j]
(đi từ ô [i,j-1] đến ô [i,j]: đi sang phải)
Ngoài ra:
F[i,j]:=F[i-1,j] + A[i,j] (trường hợp F[i-1,j] > F[i,j-1])
(đi từ ô [i-1,j] đến ô [i,j]: đi xuống dưới)
+ Nhỏ nhất:
F[i,j]:=F[i,j-1] + A[i,j] nếu F[i,j-1] < F[i-1,j]
(đi từ ô [i,j-1] đến ô [i,j]: đi sang phải)
Ngoài ra:
F[i,j]:=F[i-1,j] + A[i,j] (trường hợp F[i-1,j] < F[i,j-1])
(đi từ ô [i-1,j] đến ô [i,j]: đi xuống dưới)
(Trường hợp F[i,j-1] = F[i-1,j] , đi theo cách nào cũng được)
Công thức QHĐ tổng quát chung lại cho 2 trường hợp:
F[i,j]:=MAX(F[i,j-1], F[i-1,j]) + A[i,j] (cho bài toán tìm MAX)
F[i,j]:=MIN(F[i,j-1], F[i-1,j]) + A[i,j] (cho bài toán tìm MIN)
Truy vết (Xuất đường đi)
Gọi Đệ quy
+ Xét giá trị F[i,j] tại ô [i,j] nếu trước đó đi từ ô [i-1,j], tức là đi từ ô bên trên xuống, ngược lại nếu nếu trước đó đi từ ô [i,j-1], tức là đi từ ô bên trái sang. Khi đó ta xác định được đường đi theo yêu cầu của bài toán.
+ Với trường hợp chung tại ô [i,j] ta có bài toán tổng quát nếu xét từ ô đích [m,n] ta sẽ lần ngược về ô ban đầu [1,1].
+ Thuật toán gọi Đệ quy:
Procedure Truyvet(i,j:Integer);
Begin
If F[i,j]=F[i-1,j] + A[i,j] then Dec(i)
Else
Dec(j);
If (i>0) and (j>0) then
Begin
Truyvet(i,j);
Write(f,A[i,j],` `); {Nếu xuất giá trị ra tệp}
End;
End;
* Lưu ý: Khi thực hiện gọi Đệ quy: Truyvet(m,n) chỉ xuất đường đi từ ô ban đầu [1,1] đến trước ô [m,n], do đó ta cần phải xuất thêm giá trị (vị trí) của ô [m,n].
Khử Đệ quy
+ Thực hiện truy vết theo cách dò
 
Gửi ý kiến