TRƢỜNG ĐẠI HỌC KHOA HỌC HUẾ
KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP - TIỂU LUẬN
THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
LỚP CAO HỌC: NGÀNH KHOA HỌC MÁY TÍNH
GVHD: TS: HOÀNG QUANG
HVTH: CAO CHÍ HIỂN 0985945261
GIA LAI, 01/ 2019
MỤC LỤC
và LỜI NÓI ĐẦU ......................................................................................................... 1 PHẦN I: NỘI DUNG .............................................................................................. 2 I: ĐỘ PHỨC TẬP THUẬT TOÁN........................................................................ 2 1. Độ phức tạp thuật toán: .................................................................................. 2 2: Bài tập: .............................................................................................................. 3 ............................. 3
Bài 1: So sánh độ phức tập thuật toán Bài 2: Viết hàm tính an (với a real, n word) có độ phức tạp tính toán là O(1) ..................................................................................................................... 3 II. PHƢƠNG PHÁP ĐỆ QUY................................................................................ 5 1. Tim hiểu đệ quy ................................................................................................ 5 2. Bài tập Đệ quy trên kiểu dữ liệu mảng .......................................................... 6 Bài 3: Xóa tất cả các phần tử của dãy A gồm n phần tử có giá trị là X .......... 6 Bài 4. Viết chương trình tìm Max của dạy A gồm n phần tử (n>0) ................ 7 3. Bài tập Đệ quy trên kiểu dữ liệu danh sách liên kết đơn ............................. 9 Bài 5: Xóa tất cả các nút có trường Info là giá trị x. ....................................... 9 Bài 6: Tìm Max của trường Info trong danh sách liên kết đơn. ..................... 9 4. Bài tập Đệ quy trên kiểu dữ liệu cây nhi phân ........................................... 12 Bài 7. Viết hàm đếm số nút của cây có trường Info = x ................................ 13 Bài 8. Viết thủ tục đệ quy bổ sung 1 nút lá vào cây tìm kiếm nhị phân ........ 13 Cây tìm kiếm nhị phân: ................................................................................... 13
III. PHƢƠNG PHÁP QUY HOẠCH ĐỘNG
1. Cơ sở lý thuyết ................................................................................................ 17 a) Tư tưởng của phương pháp: ....................................................................... 17 b) Phạm vi áp dụng: ......................................................................................... 17 c) Nguyên lý của phương pháp: ...................................................................... 17 2. Phƣơng pháp thực hiện ................................................................................. 17 3. Giải bài toán bằng phƣơng pháp Quy hoạch động: (gồm 4 bƣớc) ........... 17 4. Một số bài toán Giải bằng phƣơng pháp Quy hoạch động ........................ 17 Bài 9. Bài toán cái túi nguyên (Số lượng các loại đổ vật không hạn chế) .... 17 Bài 10. Bài toán Sinh viên ôn thi .................................................................... 21 Bài 11. Người đi du lịch ................................................................................... 25 Bài 12: Bài toán xâu trong cực đại: ................................................................ 30 TÀI LIỆU THAM KHẢO .................................................................................... 34
LỜI NÓI ĐẦU
Việc xác định độ phức tạp tính toán của một thuật toán là một công việc
không hề đơn giản, trước đây chúng ta ít quan tâm đến việc đánh giá thuật toán mà
chỉ dừng lại ở mức độ đưa ra một thuật toán để giải quyết bài toán. Tuy nhiên một
bài toán có thể có nhiều thuật toán để giải. Do đó ta phải lựa chọn thuật đoán tối
ưu. Độ phức tạp thuật toán là cơ sở để đánh giá thuật toán đó có tốt hơn thuật toán
khác hay không. Đối với những thuật toán phức tạp thì việc xác định độ phức tạp
một cách chính xác là rất khó khăn đặc biệt đối với những thuật toán sử dụng giải
thuật đệ qui.
Trong phần náy, nhóm tôi đánh giá độ phức tạp của một số thuật toán. Đưa
ra một số bài toán giải hệ thức truy hồi:
- Dùng phương pháp Đệ quy để giải các bài toán trên nhiều kiểu dữ liệu như:
Kiểu dữ liệu cơ bản, kiểu mảng, danh sách liên kết đơn, cây nhị phân và cây
tìm kiếm nhị phân.
- Dùng phương pháp Quy hoạch động để giải một số bài toán tối ưu.
Đây là nội dung chính trong đề tài bài tập tiểu luận của nhóm em: THIẾT
KẾ VÀ PHÂN TÍCH THUẬT TOÁN
Mặc dù đã rất cố gắng nhưng tiểu luận này không tránh khỏi những sai sót.
Nhóm chúng em rất mong nhận được các ý kiến góp ý của thầy hướng dẫn và các
bạn.
Xin chân thành cảm ơn TS. HOÀNG QUANG đã tận tình hướng dẫn và tạo
điều kiện cho chúng em hoàn thành môn học này.
Gia Lai, ngày 10 tháng 01 năm 2019 Học viên thực hiện Cao Chí Hiển
Trang: 1
PHẦN I: NỘI DUNG
I: ĐỘ PHỨC TẬP THUẬT TOÁN
1. Độ phức tạp thuật toán:
Thời gian mà máy tính khi thực hiện một thuật toán không chỉ phụ thuộc vào
bản thân thuật toán đó, ngoài ra còn tùy thuộc từng máy tính. Để đánh giá hiệu quả
của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật
toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài
toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp thuật toán là một hàm phụ thuộc
đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính
xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng.
Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc
O-lớn
Bậc O-lớn: Gọi n là độ lớn đầu vào. Tùy thuộc từng bài toán mà n có thể
nhận những giá trị khác nhau. Chẳng hạn, bài toán tính giai thừa thì n chính là số
cần tính giai thừa. Nhiều bài toán số trị, chẳng hạn tính sai phân thì n là số chữ số
có nghĩa cần đạt được. Trong các phép tính đối với ma trận thì n là số hàng hoặc
cột của ma trận.
Độ phức tạp của bài toán phụ thuộc vào n. Ở đây ta không chỉ đặc trưng độ
phức tạp bởi số lượng phép tính, mà dùng một đại lượng tổng quát là tài nguyên
cần dùng R(n). Đó có thể là số lượng phép tính (có thể tính cả số lần truy nhập bộ
nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là thời gian thực hiện chương trình
(độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần phải cấp để chạy chương
trình (độ phức tạp về không gian).
Xét quan hệ giữa tài nguyên và độ lớn đầu vào, nếu như tìm được hằng số
C>0, không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n),g(n) đều dương
và R(n) ≤ C.g(n) thì ta nói thuật toán có độ phức tạp cỡ O(g(n))
Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:
Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ
không phụ thuộc vào độ lớn đầu vào. Chẳng hạn như các thao tác hệ thống: đóng,
mở Tập tin.
Trang: 2
Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ
nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần
tử của một mảng một chiều.
Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng
hạn như các thao tác tính toán với mảng nhiều chiều (tính định thức ma trận).
Độ phức tạp logarit, O(log n) (chú ý: bậc của nó thấp hơn so với O(n)).
Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất.
Độ phức tạp hàm mũ, O(2n). Trường hợp này bất lợi nhất và sẽ rất phi thực
tế nếu thực hiện thuật toán với độ phức tạp này.
2: Bài tập:
Bài 1: So sánh độ phức tập thuật toán và
Đặt g1(n) = ; g2 (n) =
Ta có:
=
> Vậy g1(n) > g2 (n)
Bài 2: Viết hàm tính an (với a real, n word) có độ phức tạp tính toán là O(1)
1. Phân tích thuật toán
Đặt b=an khi đó ta có các trường hợp sau:
- Nếu a=0 thì an=0
- Nếu a>0 ta có: b=an>0ln(b)=ln(an)
- Nếu a<0 ta có:
+ Nếu n là số lẻ thì b=an<0
+ Nếu n là số chẵn thì b=an=a2k=(ak)2 >0
Program Tinh_a_luythua_n;
2. Cài đặt chương trình
Trang: 3
Begin if a=0 then LuyThua:=0
End;
Const tfi='D:\luythua.inp'; tfo='D:\luythua.out'; Var fi, fo: text; Function LuyThua(a:real;n:byte):real; else if a>0 then LuyThua:=Exp(n*ln(a)) else begin a:=abs(a); if odd(n) then LuyThua:=-Exp(n*ln(a)) else LuyThua:=Exp(n*ln(a)); End { Thu tuc test ham LT} Procedure Xuly; Var a:real;n:byte; Begin Assign(fi,tfi); Reset(fi); Assign(fo,tfi); Rewrite(fo); While not eof(fi) do begin read(fi,a,n); Writeln(fo,a:0:3,'^',n,'=',LuyThua(a,n):0:3); end; close(fi); close(fo); End; BEGIN Xuly; END. 3. Kết quả thực hiện
Trang: 4
II. PHƢƠNG PHÁP ĐỆ QUY
1. Tim hiểu đệ quy
Đệ quy (tiếng Anh: recursion) là phương pháp dùng trong các chương trình
máy tính trong đó có một hàm tự gọi chính nó.
Định nghĩa theo đệ quy: Một khái niệm X được định nghĩa theo đệ quy nếu
trong định nghĩa X có sử dụng ngay chính khái niệm X.
Ví dụ 1: Định nghĩa số tự nhiên
- 0 là một số tự nhiên.
- n là số tự nhiên nếu n - 1 là số tự nhiên.
Đệ quy trong khoa học máy tính: Có một phương pháp chung để giải các bài toán là
chia bài toán thành các bài toán con đơn giản hơn cùng loại. Phương pháp này được gọi là k
thuật lập trình chia để trị. Chính nó là chìa khóa để thiết kế nhiều giải thuật quan trọng, là cơ sở
của quy hoạch động.
Chƣơng trình con đệ quy: Trong lập trình, có khái niệm: một chương trình con
(hàm, thủ tục) được gọi là đệ quy nếu trong quá trình thực hiện nó có phần phải gọi đến chính
nó.
Cấu trúc chính: Một chương trình con đệ quy căn bản gồm hai phần.
Phần cơ sở: chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể ban đầu của tham
số.
Phần đệ quy: định nghĩa tác động cần được thực hiện cho giá trị hiện thời của các tham số bằng
các tác động đã được định nghĩa trước đây với kích thước tham số nhỏ hơn.
Ví dụ: Hàm tính giai thừa của một số tự nhiên n (Đoạn mã sau được viết bằng ngôn ngữ Pascal)
function gt(n: Word): Longint; begin if n = 1 then gt:= 1 else gt:= n * gt(n - 1); end;
Trang: 5
2. Bài tập Đệ quy trên kiểu dữ liệu mảng
Bài 3: Xóa tất cả các phần tử của dãy A gồm n phần tử có giá trị là X 1. Thủ tục: Procedure DeletePT(var n: word; x: integer); var tam: integer; begin if n > 0 then if A[n] = x then begin n := n - 1; {Xoa 1 phan tu tim thay} DeletePT(n, x); {Tiep tuc tim va xoa neu co} end else begin tam := A[n]; n := n - 1; DeletePT(n, x); n := n + 1; A[n] := tam; end; end; 2. Chương trình Program TimMax; uses crt; const tfi ='D:\TTCaoHoc\DeletePT.inp'; tfo = 'D:\TTCaoHoc\DeletePT.out'; var A: Array[1..100] of integer; N, x, i : word; fi, fo : text; Procedure DocFile; var i : word; begin assign(fi,tfi); reset(fi); read(fi,n); read(fi, x); readln(fi); for i := 1 to n do read(fi,A[i]); close(fi); end; Procedure DeletePT(var n: word; x: integer); var tam: integer; begin if n > 0 then if A[n] = x then begin n := n - 1; {Xoa 1 phan tu tim thay} DeletePT(n, x); {Tiep tuc tim va xoa neu co} end else begin tam := A[n]; n := n - 1; DeletePT(n, x); n := n + 1;
Trang: 6
A[n] := tam; end; end; Begin clrscr; Docfile; assign(fo,tfo); rewrite(fo); Writeln('So luong PT: N= ', N); for i := 1 to N do write(A[i],#32); writeln; writeln('-----------'); DeletePT(n, x); Writeln('Xoa phan tu co gia tri: X= ', x); Writeln('So luong PT con lai: N= ', N); writeln(fo, N); for i := 1 to N do begin write(A[i],#32); write(fo, A[i], #32); end; writeln; readln; End. 3. Kết quả:
Bài 4. Viết chương trình tìm Max của dạy A gồm n phần tử (n>0) 1. Thủ tục Function Max(n: word): integer; begin if n = 1 then Max :=A[1] else if A[n] > Max(N-1) then Max := A[n] else Max := Max(n-1); end; 2. Cài đặt chương trình: Program TimMax; uses crt; const tfi ='D:\TTCaoHoc\dayso.inp'; tfo = 'D:\TTCaoHoc\MaxDQ.out'; var A: Array[1..100] of integer; N, i : word; fi, fo : text;
Trang: 7
Procedure DocFile; var i : word; begin assign(fi,tfi); reset(fi); read(fi,n); readln(fi); for i := 1 to n do read(fi,A[i]); close(fi); end; Function Max(n: word): integer; begin if n = 1 then Max :=A[1] else if A[n] > Max(N-1) then Max := A[n] else Max := Max(n-1); end; Begin clrscr; assign(fo, tfo); rewrite(fo); Docfile; for i := 1 to N do write(A[i],#32); writeln; writeln('-----------'); writeln(Max(N)); write(fo, 'Phan tu lon nhat: ',max(N)); close(fo); readln; End. 3. Kết quả:
Trang: 8
3. Bài tập Đệ quy trên kiểu dữ liệu danh sách liên kết đơn
Bài 5: Xóa tất cả các nút có trường Info là giá trị x. 1. Thủ tục: Procedure XoaDQ(Var F: TroNode; X: Integer); Var P : troNode; Begin If F <> Nil then IF F^.Info = X then Begin P := F; F := P^.Next; Dispose(P); XoaDQ(F,X); end Else XoaDQ(F^.Next, X); End; Procedure GhiDS(P: TroNode); var fo : text; Begin assign(fo, tfoDel); rewrite(fo); while P <> Nil do Begin Write(fo, P^.Info, #32); P := P^.next; End; close(fo); End; 2. Kết quả:
Xóa phần tử có trường Info là 6
1. Thủ tục:
Bài 6: Tìm Max của trường Info trong danh sách liên kết đơn. Function MaxDQ(F: troNode): Integer; Begin If F^.Next = Nil Then MaxDQ := F^.Info Else If F^.Info > MaxDQ(F^.Next) then MaxDQ := F^.Info else MaxDQ := MaxDQ(F^.Next); end; Procedure GhiMax(P: TroNode); var fo: text; Begin
Trang: 9
assign(fo, tfoMax); rewrite(fo); Writeln(fo, 'Gia tri Max: ', MaxDQ(P)); Close(fo); End;
2. Kết quả: Tìm giá trị có trường Info lơn nhất
3. Cài đặt chương trình Bài 5 và Bài 6
{Một số thủ tục hàm xử lý danh sách liên kết đơn bằng phương pháp đệ quy}
Program DSLienKetDon; uses crt; const tfi ='D:\TTCaoHoc\DSLKet.inp'; tfoDel = 'D:\TTCaoHoc\DelNodex.out'; tfoMax = 'D:\TTCaoHoc\MaxNode.out'; Type TroNode = ^Node; Node = Record Info : Integer; Next : TroNode; End; var Head : TroNode; N, x, i : word; fi, fo: text; Procedure Init(Var P: TroNode); Begin P := Nil; End; Procedure BSDau(Var F: TroNode; X: Integer); Var P : TroNode; Begin New(P); P^.Info := X; P^.Next := F; F:= P; End; Procedure BStang(var F: troNode; X: integer); begin If (F = nil) or (x <= F^.Info) then BSDau(F,X) else BStang(F^.Next, X); end; Procedure DisplayDS(P: TroNode); Begin While P <> Nil do Begin Write(P^.Info,#32); P := P^.Next; End; Writeln;
Trang: 10
End; Procedure DisplayNguoc(F: troNode); begin If F <> nil then begin DisplayNguoc(F^.Next); write(F^.info,#32); end; end; Procedure DisplayThuan(F: troNode); begin If F <> nil then begin Write(F^.Info,#32); DisplayThuan(F^.Next); end; end; Function MaxDQ(F: troNode): Integer; Begin If F^.Next = Nil Then MaxDQ := F^.Info Else If F^.Info > MaxDQ(F^.Next) then MaxDQ := F^.Info else MaxDQ := MaxDQ(F^.Next); end; Procedure XoaDQ(Var F: TroNode; X: Integer); Var P : troNode; Begin If F <> Nil then IF F^.Info = X then Begin P := F; F := P^.Next; Dispose(P); XoaDQ(F,X); end Else XoaDQ(F^.Next, X); End; Procedure DocFile; var X : integer; i : word; P: TroNode; begin Init(Head); assign(fi,tfi); reset(fi); read(fi,n); readln(fi); for i := 1 to n do begin read(fi,X); BSDau(Head,X); End; close(fi); end;
Trang: 11
Procedure GhiDS(P: TroNode); var fo : text; Begin assign(fo, tfoDel); rewrite(fo); while P <> Nil do Begin Write(fo, P^.Info, #32); P := P^.next; End; close(fo); End; Procedure GhiMax(P: TroNode); var fo: text; Begin assign(fo, tfoMax); rewrite(fo); Writeln(fo, 'Gia tri Max: ', MaxDQ(P)); Close(fo); End; Begin clrscr; Docfile; Writeln('So luong PT: N= ', N); DisplayDS(Head); writeln; Writeln('Phan tu co gia tri lon nhat = ',MaxDQ(Head)); GhiMax(Head); writeln('-----------'); Write('Nhap gia tri phan tu can xoa: X= '); readln(X); XoaDQ(Head, X); GhiDS(Head); DisplayDS(Head); writeln; write('Nhan gia tri phan tu can bo sung = '); readln(X); BSTang(Head,X); DisplayDS(Head); writeln('In danh sach nguoc De quy'); DisplayNguoc(Head); writeln; writeln('In danh sach thuan De quy'); DisplayThuan(Head); writeln; readln; End. 4. Bài tập Đệ quy trên kiểu dữ liệu cây nhi phân
Type TreeB = ^Node; Node = Record
Info: Integer; Left,Right: TroNode;
End;
Var T: TreeB;{ Cây nhị phân T}
Cho khai báo cây nhị phân T như sau:
Trang: 12
Bài 7. Viết hàm đếm số nút của cây có trường Info = x {Dem so Nut cu truong Info la X} Function DemNut(T: treeB; x: integer): integer; begin if T = nil then DemNut := 0 else if T^.info = x then DemNut := 1 + DemNut(T^.left, x) + DemNut(T^.right, x) else DemNut := DemNut(T^.left, x) + DemNut(T^.right, x); end; Bài 8. Viết thủ tục đệ quy bổ sung 1 nút lá vào cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân:
Là một dạng cây nhi phân được tổ chức theo một trật tự nào đó của các nút để thuận lợi
cho việc tìm kiếm. Giả sử dữ liệu tại một nút của cây có thành phần Info là khóa của các phần tử
và trên cây các nút không có 2 phần tử trùng khóa. Khái niệm cây tìm kiếm nhị phân được định
nghĩa như sau:
Cây tìm kiếm nhị phân là một cây nhi phân mà tại mỗi cây con của nó thỏa điều kiện:
Khóa của nút gốc lớn hơn khóa của tất cả các nút của cây con bên trái và nhỏ hơn khóa của tất cả
các nút của cây con bên phải.
Nếu cây rỗng thì x là nút gốc của cây, thuật toán dừng
Nếu khóa của nút gốc bằng khóa của x thì thuật toán dừng (nút đã có)
Nếu khóa của nút gốc lớn hơn khóa của x thì thêm x vào cây con trái
Nếu khóa của nút gốc nhở hơn khóa của x thì thêm x vào cây con phải
1. Thuật toán đệ quy thêm một nút vào cây tìm kiếm nhị phấn
new(t); t^.info:=x;
if t=nil then begin
addnut(t^.left,x)
if t^.info > x then else
if t^.info < x then
addnut(t^.right,x);
end else begin end;
//Them 1 nut vao cay BST sao cho cay van la BST} procedure addnut(var t:treeB; x:integer); begin t^.left:=nil; t^.right:=nil; end;
2. Thủ tục Bổ sung 1 nút vào BST
Trang: 13
Cài đặt chương trình cây nhị phân: Một số thủ tục duyệt cây nhị phân
= 'D:\TTCaoHoc\CayNP\treeNP.inp'; = 'D:\TTCaoHoc\CayNP\treeNP.out';
info:integer; left,right:treeB;
end;
= ^Node; Node = record
new(t); t^.info:=x;
if t=nil then begin
addnut(t^.left,x)
if t^.info > x then else
if t^.info < x then
addnut(t^.right,x);
end else begin end;
x:integer;
read(f,x); addnut(t,x);
t:=nil; assign(f,tfi); reset(f); while not seekeof(f) do begin end; close(f);
if t<>nil then begin
Program Cay_Nhi_phan; const tfi tfo type treeB var t:treeB; x : Integer; {=============================================== //Them 1 nut vao cay BST sao cho cay van la BST} procedure addnut(var t:treeB; x:integer); begin t^.left:=nil; t^.right:=nil; end; {//=============================================== //Doc du lieu tu file tree.inp dua vao cay} procedure InputFile; var f:text; begin end; {//=============================================== //Duyet cay} procedure duyetTruoc(t:treeB); begin write(t^.info,' '); {//duyet theo thu tu truoc}
duyetTruoc(t^.left);
Trang: 14
duyetTruoc(t^.right);
end
duyetSau(t^.left); duyetSau(t^.right); write(t^.info,' '); {//duyet theo thu tu Sau}
if t<>nil then begin end
duyetGiua(t^.left); write(t^.info,' '); {//duyet theo thu tu giua} duyetGiua(t^.right);
if t<>nil then begin end
InputFile; writeln;
writeln('Duyet cay theo thu tu giua'); DuyetGiua(t);
end; procedure duyetSau(t:treeB); begin end; procedure duyetGiua(t:treeB); begin end; Function DemNutLa(T: treeB): integer; begin if t = nil then DemNutLa := 0 else if (t^.left = nil ) and (t^.right = nil) then DemNutLa := 1 + DemNutLa(T^.left) + DemNutLa(T^.right) else DemNutLa := DemNutLa(T^.left) + DemNutLa(T^.right) end; {Dem so Nut cu truong Info la X} Function DemNut(T: treeB; x: integer): integer; begin if T = nil then DemNut := 0 else if T^.info = x then DemNut := 1 + DemNut(T^.left, x) + DemNut(T^.right, x) else DemNut := DemNut(T^.left, x) + DemNut(T^.right, x); end; BEGIN writeln('Duyet cay theo thu tu truoc'); DuyetTruoc(T); writeln; writeln('Duyet cay theo thu tu sau'); DuyetSau(T); writeln; write('Nhap phan tu can tim: x= '); readln(x); writeln('So luong pt x:', DemNut(T,x));
Trang: 15
writeln;
writeln('So luong nut la =', demNutLa(T)); readln; END. Dữ lieu tập tin được đưa vào:
Phần tử cuối cùng có giá trị 30 không được bổ sung vì đã tồn tại rồi. // input: file tree.inp co noi dung nhu sau: // // 15 9 25 7 12 20 30 17 16 27 28 37 (gom 12 nut) // // voi du lieu tren, su dung thuat toan tao cay BST // // thi hinh dang cay se duoc tao ra nhu sau: // // // // 15 // // / \ // // 9 25 // // / \ / \ // // 7 12 20 30 // // / / \ // // / / \ // // 17 27 37 // // / \ // // 16 28 //
Trang: 16
III. PHƢƠNG PHÁP QUY HOẠCH ĐỘNG
1. Cơ sở lý thuyết
a) Tư tưởng của phương pháp:
- Sử dụng nguyên lý chia để trị (tránh tính toán lại các bài toán con đã xét)
- Cách tiếp cận từ dưới lên
b) Phạm vi áp dụng:
- Các bài toán có được bằng việc tổng hợp các nghiệm của các bài toán con
- Các bài toán tối ưu rời rạc
c) Nguyên lý của phương pháp:
Vận dụng nguyên lý tối ưu của Bellman: “Trong một dãy tối ưu của các lựa
chọn thì một dãy con của nó cũng là tối ưu”.
2. Phƣơng pháp thực hiện
o Phân tích bài toán (biểu diễn bài toán dưới dạng một bài toán nhiều mức)
o Xây dựng giải pháp đệ quy (lập công thức truy hồi)
o Lập bảng (sử dụng các mảng để tính toán các giá trị theo kiểu dưới-lên)
o Tổng hợp kết quả (kiến tạo một lời giải cho bài toán từ các thông tin đã tính
toán)
3. Giải bài toán bằng phƣơng pháp Quy hoạch động: (gồm 4 bƣớc)
Bước 1: Phân tích bài toán
Bước 2: Giải pháp đệ quy
Bước 3: Lập bảng tính toán
Bước 4: Tổng hợp kết quả
Đánh giá độ phức tạp tính toán
4. Một số bài toán Giải bằng phƣơng pháp Quy hoạch động
Bài 9. Bài toán cái túi nguyên (Số lƣợng các loại đổ vật không hạn chế)
Có n loại đồ vật có kích thước và giá trị khác nhau c[i]R;m[i]N* tương
ứng là giá trị và kích thước của loại đồ vật thứ i; số lượng mỗi loại không hạn
chế. Một tên trộm mang theo một chiếc túi có kích thước là pN*. Vậy hắn phải
lựa chọn mỗi loại đồ vật lấy số lượng bao nhiêu để giá trị lấy cắp được là lớn nhất.
Trang: 17
1. Xác định bài toán
Input: n, p N*; c[i]R; m[i]N*; i=1..n
Output: x[i]: Số lượng loại đồ vật thứ i cần lấy sao cho và
đạt giá trị lớn nhất.
2. Phương pháp thực hiện,
Sử dụng phương pháp quy hoạch động theo 4 bước sau:
Bƣớc 1: Phân tích bài toán:
Gọi P(r,s) là bài toán cái túi trong đó: r là kích thước túi, s là số loại đồ vật.
Các giá trị cần tìm: U[r,s] là số lượng loại đồ vật thứ s cần lấy sao cho L[r,s]
là giá trị cực đại của bài toán P(r,s). Bài toán ban đầu P(p,n)
Bƣớc 2: Giải pháp đệ quy
-Suy biến: Khi s=1 thì U[r,s]= r div m[i]L[r,s]=U[r,s]*c[i]
- Chung: Khi s>1 thì:
L[r,s]= Max {c[s]*k+L[r-k*m[i],s-1]} với k=0..r div m[s]
L[r,s]= c[s]*k'+L[r-k'*m[i],s-1]
U[r,s]=k'
for s:=1 to n do for r:= 0 to p do if s = 1 then
begin u[r,1]:= r div m[1];
l[r,1]:= u[r,1]*c[1]; end else begin tinhL[r, s]; tinhU[r, s] end; end;
Bƣớc 3: Lập bảng
Bƣớc 4: Tổng hợp kết quả
Procedure Tonghop; Var r,s:integer; Begin r:=p;
Trang: 18
for s:= n downto 1 do begin x[s]:=u[r,s]; r:= r-x[s]*m[s]; end; End; 3. Cài đặt chương trình
= =
fi fo nmax= 100; pmax= 1000; L,U:array[0..pmax,0..nmax] of integer; m,c,x: array[1..nmax] of integer;
i:integer;
assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readln(f,m[i],c[i]); readln(f,p); close(f);
max:=tam; k1:=k;
tam:=k*c[s] + L[r-k*m[s],s-1]; if tam > max then begin end;
k1:=0; max:=L[r,s-1]; for k:=1 to r div m[s] do begin end; u[r,s]:=k1; l[r,s]:=max;
u[r,1]:= r div m[1]; l[r,1]:=u[r,1] * c[1];
fillchar(u,sizeof(u),0); fillchar(l,sizeof(l),0); for s:=1 to n do
for r:=0 to p do if s=1 then begin end else Tinh_UL(r,s);
Program Bai_Toan_Cai_Tui; {Han ch so luong vat cung loai} 'D:\input.txt'; const 'D:\output.txt'; Var r,s, n,p:integer; Procedure Doc_Du_Lieu; var f:text; begin end; Procedure Tinh_UL(r,s:integer); var k,k1,max,tam:integer; begin end; Procedure Lap_Bang; var r,s:integer; begin end;
Trang: 19
x[s]:=u[r,s]; r:=r-x[s]*m[s];
assign(f,fo); rewrite(f); r:=p; for s:=n downto 1 do begin end; Writeln(f,'Gia tri toi uu: ',L[p,n]); Writeln(f,'Cac vat duoc chon:'); for i:=1 to n do writeln(f,'Vat thu ',i,' so luong ',x[i]); close(f);
Doc_Du_lieu; Lap_bang;
Procedure Tong_Hop_KQ; var f:text; r,s,i:integer; begin end; BEGIN Tong_hop_KQ; { for r := 0 to p do begin for s :=0 to N do write(L[r,s],',',U[r,s],#32); writeln; end; } Tong_hop_KQ; readln; END.
4. Kết quả một số bộ test
Bộ test 1:
Trang: 20
Bộ test 3
Bộ test 2
Bài 10. Bài toán Sinh viên ôn thi
Một sinh viên còn m ngày để ôn thi n môn. Theo kinh nghiệm của anh ta, nếu
ôn môn j trong i ngày thì được điểm là a[i,j]. Giả sử cho biết các a[i,j] (với
a[i,j]<=a[i+1,j]).
Tìm bộ x[j] (số ngày ôn môn j, với j=1..n) sao cho x[j]=m và sinh viên đạt
tổng điểm lớn nhất (a[x[j], j]max).
1. Xác định bài toán
Input: + m,n (m là số ngày, n là số môn)
+ A[i,j] (với i=1..m, j=1..n ) số điểm đạt được khi ôn môn j trong i ngày
Output: + Tổng số điểm lớn nhất
+ X[j] (j=1..n) số ngày ôn môn j sao cho x[j]=m (j=1..n)
Môn thi thứ j 1 2 … n-1 n
Số ngày ôn thi (x[j]) ? ? … ? ?
Trang: 21
Nhận xét
Bài toán này quy về bài toán cái túi nguyên
Trong đó:
+ Số ngày tối đa để ôn thi là m ngày tương ứng với khối lượng tối đa của
chiếc túi là p.
+ Giá trị điểm đạt được khi ôn môn j trong i ngày tương ứng với đồ vật thứ j
được lấy với số lượng i cái (A[i,j]).
2. Phương pháp thực hiện,
Sử dụng phương pháp quy hoạch động theo 4 bước sau:
Bƣớc 1: Phân tích bài toán
Gọi P(r,s) là bài toán sinh viên ôn thi Trong đó: + r N*: số ngày ôn thi + s N*: số môn học Bài toán ban đầu là P(m,n) Các giá trị cần tìm: L[r,s]: giá trị tối ưu của bài toán P(r,s) U[r,s] là số lượng ngày dành để ôn môn s tức X[s].
Bƣớc 2: Giải pháp đệ quy
L[r,s] = Max(A[k,s] + L[r- k, s-1])
L[r,s] = A[k‟,s] + L[r-k‟,s-1] U[r,s] = k‟
+ Trường hợp tổng quát (s>1) Ta có 0≤k≤r Giả sử giá trị lớn nhất khi k đạt được tại k‟. Ta có: + Trường hợp suy biến: số môn = 1 (s=1) U[r,1] =r; L[r,1] = A[r,1] (với r=1..m)
U[r,s]:=r; L[r,s]:=A[r,1];
For s:=1 to n do If s=1 then Begin End Else TinhUL(r,s);
Procedure LapBang; Var r,s:integer; Begin For r:=1 to m do End;
Bƣớc 3: Lập bảng
Thủ tục TinhUL(r,s) được viết như sau: Procedure TinhUL(r,s:integer);
Trang: 22
max:=tam; k1:=k;
tam:= A[k,s] + L[r- k,s-1]; if tam>max then begin end;
Var k,k1,max,tam:integer; Begin max:= L[r,s-1]; k1:=0; for k:=1 to r do begin end; L[r,s]:=max; U[r,s]:=k1; End;
x[s]:=U[r,s]; r:=r - x[s];
Bƣớc 4: Tổng hợp kết quả Procedure THKQ; var r,s:integer; begin Writeln('Ket qua diem lon nhat: ',L[m,n]); Writeln('Lich hoc nhu sau:'); r:=m; For s:=n downto 1 do Begin End; For s:=1 to n do writeln('Mon ',s, ' hoc ',X[s], ' ngay'); end;
'D:\SVonthi.inp'; 'D:\SVonthi.out';
nmax= 1000; A,L,U:array[0..nmax,0..nmax] of integer; X:array[1..nmax] of integer; n,m:integer;
i,j:integer;
for j:=1 to n do read(fi,a[i,j]); readln(fi);
fillchar(L,sizeof(L),0); fillchar(U,sizeof(U),0); assign(fi,tfi); reset(fi); readln(fi,m,n); for i:=1 to m do begin end; close(fi);
Program SVOnThi; tfi = const tfo = Var Procedure NhapDL; var fi:text; begin end; Procedure TinhUL(r,s:integer); Var k,k1,max,tam:integer;
3. Cài đặt chương trình
Trang: 23
max:=tam; k1:=k;
tam:= A[k,s] + L[r- k,s-1]; if tam > max then begin end;
max:= L[r,s-1]; k1:=0; for k:=1 to r do begin end; L[r,s]:=max; U[r,s]:=k1;
U[r,s]:=r; L[r,s]:=A[r,1];
For s:=1 to n do If s=1 then Begin End Else TinhUL(r,s);
for s:=1 to n do write(u[r,s],'\',L[r,s],' '); writeln;
For r:=1 to m do for r:=1 to m do begin end;
X[s]:=U[r,s]; r:=r - x[s];
assign(fo,tfo); rewrite(fo); Writeln(fo,'Ket qua diem lon nhat: ',L[m,n]); Writeln(fo,'Lich hoc nhu sau:'); r:=m; For s:=n downto 1 do Begin End; For s:=1 to n do writeln(fo,'Mon ',s, ' hoc ',X[s], ' ngay'); close(fo);
NhapDL; LapBang; THKQ;
Begin End; Procedure LapBang; Var r,s:integer; Begin End; Procedure THKQ; var fo:text; r,s:integer; begin end; BEGIN END.
Trang: 24
4. Kết quả các bộ test
Bộ test 2
Bộ test 3
Bộ test 1
Bài 11. Ngƣời đi du lịch
Một người đi từ thành phố 0 đến thành phố n và có thể đi qua n-1 thành phố khác 1, 2,..., n-1, theo lộ trình: 0 i1 i2 ….. ik n, trong đó: 0 < i1 < i2 < …< ik < n,Giá vé của xe đi từ thành phố i đến thành phố j là c[i,j]. Tìm một lộ trình từ thành phố 0 đến thành phố n sao cho tổng chi phí về giá vé đạt cực tiểu.
1. Xác định bài toán
Input + N: với ý nghĩa là có N+1 thành phố từ thành phố 0 đến thành phố N.
+ Ma trận C[i,j] (i=0..N, j=0..N) là ma trận chi phí, trong đó C[i,j] là chi phí
trực tiếp để đi từ thành phố i đến thành phố j (i có đường đi trực tiếp đến j). Nếu i không có đường đi trực tiếp đến j thì C[i,j] = +∞.
Trang: 25
Output + Chi phí nhỏ nhất để đi từ thành phố 0 đến thành phố N.
+ X[i] (i=1..m) là số thứ tự của các thành phố phải đi qua khi đi từ
thành phố 0 đến thành phố n (0X[1]X[2]…X[m]n).
2. Phương pháp thực hiện,
Sử dụng phương pháp quy hoạch động theo 4 bước sau:
Bƣớc 1: Phân tích bài toán
Gọi P(r) là bài toán du lịch
Trong đó:
+ r N*: là số thứ tự của thành phố cần đến từ thành phố 0.
Bài toán ban đầu là P(n)
Các giá trị cần tìm:
L[r]: chi phí nhỏ nhất để đi từ thành phố 0 đến thành phố r
K[r]: là số thứ tự của thành phố kế trước thành phố r trên đường đi từ thành
phố 0 đến thành phố r.
Ví dụ
Input: n=3
Mảng A
i\j 0 1 2 3
0 0 4 2 6
1 4 0 1 2
2 2 1 0 3
3 6 2 3 0
Output: Chi phí thấp nhất = 5
Lịch trình: 0 2 3
Bƣớc 2: Giải pháp đệ quy
+ Trƣờng hợp tổng quát (r > 0):
L[r] = Min(L[i]+C[i,r]) với (0≤ i Giả sử giá trị nhỏ nhất đạt được tại i‟ ta có K[r]=i‟. + Trường hợp suy biến (r=0) Ta có Nếu r=0 ta có L[0]=0; K[0] không xác định. Bƣớc 3: Lập bảng i 0 1 2 3 L[i] 0 4 2 5 r,i,min,i1:integer; min:=L[i]+c[i,r];
i1:=i; if (L[i] + C[i,r]) < min then
begin
end; min:=C[0,r];
i1:=0;
for i:=0 to r-1 do
begin
end;
l[r]:=min;
k[r]:=i1; x[i]:=k[r]
r:=x[i]; K[i] 0 0 0 2 'D:\NguoiDL.inp';
'D:\NguoiDL.out'; =
=
1000;
10000; = tfi
tfo
maxn =
vc
C:array[0..maxn,0..maxn] of longint;
l,k:array[0..maxn] of longint; Program NguoiDLich;
const
var
i, n:integer;
procedure NhapDL; 3. Cài đặt chương trình read(f,t);
if t>0 then C[i,j]:=t
else C[i,j]:=vc; begin
end;
readln(f); assign(f,tfi);
reset(f);
readln(f,n);
for i:=0 to n do
begin
for j:=0 to n do
end;
close(f); min:=L[i]+c[i,r];
i1:=i; if (L[i] + C[i,r]) < min then
begin
end; min:=c[0,r];
i1:=0;
for i:=0 to r-1 do
begin
end;
l[r]:=min;
k[r]:=i1; end; i,j,r:integer;
x:array[0..maxn] of integer; var f:text; i,j,t:integer;
begin
end;
procedure LapBang;
var r,i,j,min,i1:integer;
begin
{l[0]:=0; k[0]:=vc;}
for r:=0 to n do
begin
if r = 0 then
begin L[0] := 0;
K[0] := 0;
end
else
begin
end;
for i:=0 to n do write(L[i],' ');
writeln;
for i:=0 to n do write(K[i],' ');
end;
procedure THKQ;
var f:text;
begin
assign(f,tfo);
rewrite(f);
writeln(f,'Chi phi thap nhat ',L[n]);
writeln(f,'Lich trinh'); r:=n; i:=0; x[0]:=n; close(f); NhapDL;
Lapbang; while r >0 do
begin
i := i + 1;
x[i] := k[r];
r := x[i];
end;
for j:= i downto 0 do
if x[j]=n then
write(f,' ',x[j])
else write(f,x[j],' -> ');
end;
BEGIN
writeln('Xuat bang chi phi: ');
for i := 0 to n do
write(L[i],#32);
writeln;
writeln('Xuat bang lo trinh: ');
for i := N downto 0 do
write(K[i],#32);
writeln;
THKQ;
END. 4. Kết quả các bộ test Bộ test 2 Bộ test 1 Bộ test 3 S là xâu trong của T nếu S nhận được bằng cách xoá đi một số ký tự nào đó. Ví dụ: „ABC‟ là xâu trong của „GAHEBOOC‟ Bài toán: Cho 2 xâu T1, T2. Tìm một xâu S là xâu trong chung của T1 và T2 có độ dài cực đại. Ví dụ: T1=„ABCDAE‟ và T2=„XYACADK‟ có xâu „ACD‟ là xâu trong chung với độ dài cực đại. 1. Xác định bài toán + Xâu T1 =‟x1, x2,…, xm‟ và xâu T2 =‟y1, y2,…, ym‟. Input:
Output: +Độ dài xâu con chung tìm được
+ Xâu C là xâu con chung tìm được 2. Phương pháp thực hiện, Bƣớc 1: Phân tích bài toán
Gọi P(r,s) là bài toán xâu con chung Trong đó:
+ r N*: độ dài xâu T1
+ s N*: độ dài xâu T2 Bài toán ban đầu là P(m,n)
Các giá trị cần tìm:
L[r,s]: độ dài lớn nhất của xâu con chung tìm được từ r ký tự đầu của xâu T1 và s
ký đầu của xâu T2 Bƣớc 2: Giải pháp đệ quy + Trường hợp tổng quát: cả hai xâu khác rỗng (r>0) and( s>0)
Nếu T1[r] = T2[s] ta có L[r,s] = 1 + L[r-1,s-1].
Còn nếu T1[r] ≠ T2[s] thì L[r,s] = Max(L[r-1,s], L[r,s-1])
+ Trường hợp suy biến: một trong hai xâu rỗng hoặc cả hai xâu rỗng (T1=‟‟ or
T2=‟‟)
Nếu xâu cả hai xâu T1 và T2 rỗng ta có L[0,0] = 0 Nếu chỉ xâu T1 rỗng ta có L[0,s] = 0 (s=1..n);
Nếu chỉ xâu T2 rỗng ta có L[r,0] = 0 (r=1..m); for r:=0 to m do for s:=0 to n do if (r=0) or (s=0) then L[r,s]:=0
else if T1[r]=T2[s] then L[r,s]:= 1 + L[r-1,s-1]
else L[r,s]:=max(L[r,s-1],L[r-1,s]); procedure LapBang;
var r,s:byte;
begin
end;
Độ phức tạp O(m.n) Bƣớc 3: Lập bảng C:=T1[r] + C;
r:=r-1; s:=s-1; if T1[r]=T2[s] then
begin
end
else if Ll[r-1,s] >L[r,s-1] then r:=r-1 else s:=s-1; C:='';
r:=m; s:=n;
While (r>0) and (s>0) do
Begin
End;
writeln(‘Do dai lon nhat cua xau con chung la: ‘,L[m,n]);
writeln(‘Xau con chung dai nhat tim duoc la:’,C);
close(f); procedure THKQ;
var r,s:byte;
begin
end; Bƣớc 4: Tổng hợp kết quả 'D:\xaucon.inp';
'D:\xaucon.out'; tfi =
tfo =
maxmn=200; Program XauConChungMax;
const
var T1,T2,c:string;
m,n:byte;
L:array[0..maxmn,0..maxmn] of byte;
procedure NhapDL;
var f:text;
begin assign(f,tfi);
reset(f);
readln(f,T1);
readln(f,T2);
m:=length(T1); 3. Cài đặt chương trình n:=length(T2);
close(f); for s:=1 to n do
if T1[r]=T2[s] then L[r,s]:= 1 + L[r-1,s-1]
else L[r,s]:=max(L[r,s-1],L[r-1,s]); fillchar(L,sizeof(L),0);
for r:=1 to m do c:=T1[r] + C;
r:=r-1; s:=s-1; if T1[r]=T2[s] then
begin
end
else if l[r,s-1] > l[r-1,s] then s:=s-1 else r:=r-1; c:='';
r:=m; s:=n;
While (s>0) and (r>0) do
begin
End;
assign(f,tfo); rewrite(f);
writeln(f,l[m,n]);
writeln(f,c);
close(f); NhapDL;
LapBang;
THKQ; end;
Function Max(A,B: integer): integer;
Begin
if A > B then
Max := A
else
Max := B;
End;
procedure LapBang;
var r,s:byte;
begin
end;
procedure THKQ;
var r,s:byte;
f:text;
begin
end;
BEGIN
END. Bộ test 1 Bộ test 2 4. Kết quả các bộ test 1. Bài giảng Thiết kế và phân tích thuật toán – TS Hoàng QuangTrang: 26
procedure LapBang;
var
begin
l[0]:=0;
for r:=1 to n do
begin
end;
end;
Độ phức tạp O(n2)
Bƣớc 4: Tổng hợp kết quả
procedure THKQ;
var
r,i,j:integer;
x:array[0..maxn] of integer;
begin
writeln(f,'Chi phi thap nhat ',L[n]);
writeln(f,'Lich trinh duong di');
r:=n; i:=0; x[1]:=n
while r > 0 do
begin i:=i+1;
end;
for j:=i downto 1 do writeln(x[i]);
end;
Độ phức tạp O(n)
Trang: 27
Trang: 28
Trang: 29
Bài 12: Bài toán xâu trong cực đại:
Trang: 30
Trang: 31
Trang: 32
Trang: 33
TÀI LIỆU THAM KHẢO
Trang: 34