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

Chia sẻ: Cao Chi Hien Hien | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

63
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung của tiểu luận bao gồm 3 chương với các nội dung: độ phức tạp thuật toán; phương pháp đệ quy; phương pháp quy hoạch động. Để nắm chi tiết hơn nội dung nghiên cứu, mời các bạn cùng tham khảo tiểu luận.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận ngành Khoa học máy tính: Thiết kế và phân tích thuật toán

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 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 Bài 1: So sánh độ phức tập thuật toán O( N ) và O(log 2 n) ............................. 3 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 O( N ) và O(log 2 n) Đặt g1(n) = N ; g2 (n) = log 2 n 1 g1(n) n n2 Ta có: lim  lim  lim n  g 2( n) n  log n log 2 n 2 n  1 1 ' 2 '  lim ( n)  lim (n ) = lim 2 n  lim n.ln 2  lim n  lim n   ' ' n  (log 2 n) n  (log 2 n) n  1 n  2 n n n n n.ln 2 Vậy g1(n) > g2 (n)  O( N ) > O(log2 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)  b  eln( a  e n.ln( a ) n ) - Nếu a
Const tfi='D:\luythua.inp'; tfo='D:\luythua.out'; Var fi, fo: text; Function LuyThua(a:real;n:byte):real; Begin if a=0 then LuyThua:=0 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 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 Bài 6: Tìm Max của trường Info trong danh sách liên kết đơn. 1. Thủ tục: 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
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 Cho khai báo cây nhị phân T như sau: Type TreeB = ^Node; Node = Record Info: Integer; Left,Right: TroNode; End; Var T: TreeB;{ Cây nhị phân T} 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. 1. Thuật toán đệ quy thêm một nút vào cây tìm kiếm nhị phấn 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 2. Thủ tục Bổ sung 1 nút vào BST //Them 1 nut vao cay BST sao cho cay van la BST} procedure addnut(var t:treeB; x:integer); begin if t=nil then begin new(t); t^.info:=x; t^.left:=nil; t^.right:=nil; end else begin if t^.info > x then addnut(t^.left,x) else if t^.info < x then addnut(t^.right,x); end; end; 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 Program Cay_Nhi_phan; const tfi = 'D:\TTCaoHoc\CayNP\treeNP.inp'; tfo = 'D:\TTCaoHoc\CayNP\treeNP.out'; type treeB = ^Node; Node = record info:integer; left,right:treeB; end; 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 if t=nil then begin new(t); t^.info:=x; t^.left:=nil; t^.right:=nil; end else begin if t^.info > x then addnut(t^.left,x) else if t^.info < x then addnut(t^.right,x); end; end; {//=============================================== //Doc du lieu tu file tree.inp dua vao cay} procedure InputFile; var f:text; x:integer; begin t:=nil; assign(f,tfi); reset(f); while not seekeof(f) do begin read(f,x); addnut(t,x); end; close(f); end; {//=============================================== //Duyet cay} procedure duyetTruoc(t:treeB); begin if tnil then begin write(t^.info,' '); {//duyet theo thu tu truoc} duyetTruoc(t^.left); Trang: 14
duyetTruoc(t^.right); end end; procedure duyetSau(t:treeB); begin if tnil then begin duyetSau(t^.left); duyetSau(t^.right); write(t^.info,' '); {//duyet theo thu tu Sau} end end; procedure duyetGiua(t:treeB); begin if tnil then begin duyetGiua(t^.left); write(t^.info,' '); {//duyet theo thu tu giua} duyetGiua(t^.right); end 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 InputFile; writeln; writeln('Duyet cay theo thu tu truoc'); DuyetTruoc(T); writeln; writeln('Duyet cay theo thu tu sau'); DuyetSau(T); writeln; writeln('Duyet cay theo thu tu giua'); DuyetGiua(t); write('Nhap phan tu can tim: x= '); readln(x); writeln('So luong pt x:', DemNut(T,x)); Trang: 15
writeln('So luong nut la =', demNutLa(T)); writeln; 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 n Output: x[i]: Số lượng loại đồ vật thứ i cần lấy sao cho  x[i]  m[i]  p i 1 và n  x[i]  c[i] đạt giá trị lớn nhất. i 1 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' Bƣớc 3: Lập bảng 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 4: Tổng hợp kết quả Procedure Tonghop; Var r,s:integer; Begin r:=p; Trang: 18