Tiểu luận Khoa học máy tính: Thiết kế và phân tích thuật toán (chuẩn nhất)

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>0ln(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à pN*. 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 (0X[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

Trang: 26

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

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)

'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

Trang: 27

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;

Trang: 28

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

Trang: 29

Bộ test 3

Bài 12: Bài toán xâu trong cực đại:

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

Trang: 30

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

Trang: 31

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.