Bài giảng Phân tích và thiết kế thuật toán (Phần 2) - ĐH Phương Đông

Cùng nắm kiến thức trong bài giảng "Phân tích và thiết kế thuật toán (Phần 2)" thông qua việc tìm hiểu các nội dung sau: quy hoạch động, thuật toán đồ thị cơ bản. Mời các bạn xem qua và nắm được kiến thức đã trình bày trong bài giảng này thật hiệu quả.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích và thiết kế thuật toán (Phần 2) - ĐH Phương ĐôngQuy hoạch độngCông thức truy hồiVí dụCho số tự nhiên n ≤ 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng củadãy cácsố nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách.n = 5 có 7 cách phân tích:(Lưu ý: n = 0 vẫn coi là có 1 cách phân tích thành tổng các số nguyên dương (0 làtổng của dãy rỗng))Để giải bài toán này, trong chuyên mục trước ta đã dùng phương pháp liệt kê tấtcả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem,cócáchnàotínhngayrasốlượngcáccách phântíchmàkhôngcầnphảiliệtkêhaykhông?.Bởi vì khi số cách phân tích tương đối lớn, phương pháp liệt kê tỏ ra khá chậm. (n = 100có 190569292 cách phân tích).Nhận xét:Nếu gọi F[m, v] là số cách phân tích số v thành tổng các số nguyên dương ≤ m. Khiđó: Các cách phân tích số v thành tổng các số nguyên dương ≤ m có thể chia làm hailoại: • Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại này chính là số cách phân tích số v thành tổng các số nguyên dương < m, tức là 68/129 số cách phân tích số v thành tổng các số nguyên dương ≤ m - 1 và bằng F[m - 1, v]. • Loại 2: Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v - m thành tổng các số nguyên dương ≤ m (Lưu ý: điều này chỉ đúng khi không tính lặp lại các hoán vị của một cách). Có nghĩa là về mặt số lượng, số các cách phân tích loại này bằng F[m, v - m]Trong trường hợp m > v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong trườnghợp m ≤ v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế: • F[m, v] = F[m - 1, v] nếu m > v • F[m, v] = F[m - 1, v] + F[m, v - m] nếu m ≤ vTa có công thức xây dựng F[m, v] từ F[m - 1, v] và F[m, v - m]. Công thức này có têngọi là công thứctruyhồiđưa việc tính F[m, v] về việc tính các F[m, v] với dữ liệu nhỏhơn. Tất nhiên cuốicùng ta sẽ quan tâm đến F[n, n]: Số các cách phân tích n thành tổng các số nguyên dương≤ n.Với n = 5, bảng F sẽ là:Nhìn vào bảng F, ta thấy rằng F[m, v] được tính bằng tổng của:Một phần tử ở hàng trên: F[m - 1, v] và một phần tử ở cùng hàng, bên trái: F[m, v - m].F[5, 5] sẽ được tính bằng F[4, 5] + F[5, 0], hay F[3, 5] sẽ được tính bằng F[2, 5] + F[3,2].Chính vì vậy để tính F[m, v] thì F[m - 1, v] và F[m, v - m] phải được tính trước. Suy rathứ tự hợp lý để tính các phần tử trong bảng F sẽ phải là theo thứ tự từ trên xuống vàtrên mỗi hàng thì tính theo thứ tự từ trái qua phải. 69/129Điều đó có nghĩa là ban đầu ta phải tính hàng 0 của bảng: F[0, v] = số dãy có các phầntử ≤ 0 mà tổng bằng v, theo quy ước ở đề bài thì F[0, 0] = 1 còn F[0, v] với mọi v > 0đều là 0.Vậy giải thuật dựng rất đơn giản: Khởi tạo dòng 0 của bảng F: F[0, 0] = 1 còn F[0, v]với mọi v > 0 đều bằng 0, sau đó dùng công thức truy hồi tính ra tất cả các phần tử củabảng F. Cuối cùng F[n, n] là số cách phân tích cần tìmPROG01_1.PAS * Đếm số cách phân tích số nprogram Analyse1; {Bài toán phân tích số}constmax = 100;varF: array[0..max, 0..max] of LongInt;n, m, v: Integer;beginWrite(n = ); ReadLn(n);FillChar(F[0], SizeOf(F[0]), 0); {Khởi tạo dòng 0 của bảng F toàn số 0}F[0, 0] := 1; {Duy chỉ có F[0, 0] = 1}for m := 1 to n do {Dùng công thức tính các dòng theo thứ tự từ trên xuống dưới}for v := 0 to n do {Các phần tử trên một dòng thì tính theo thứ tự từ trái qua phải}if v < m then F[m, v] := F[m - 1, v]else F[m, v] := F[m - 1, v] + F[m, v - m]; WriteLn(F[n, n], Analyses);{Cuối cùngF[n, n] là số cách phân tích}end. 70/129Cải tiến thứ nhấtCách làm trên có thể tóm tắt lại như sau: Khởi tạo dòng 0 của bảng, sau đó dùng dòng0 tính dòng 1, dùng dòng 1 tính dòng 2 v.v... tới khi tính được hết dòng n. Có thể nhậnthấy rằng khi đã tính xong dòng thứ k thì việc lưu trữ các dòng từ dòng 0 tới dòng k - 1là không cần thiết bởi vì việc tính dòng k+ 1 chỉ phụ thuộc các giá trị lưu trữ trên dòngk. Vậy ta có thể dùng hai mảng một chiều: Mảng Current lưu dòng hiện thời đang xétcủa bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Current được gán các giá trịtương ứng trên dòng 0. Sau đó dùng mảng Current tính mảng Next, mảng Next sau khitính sẽ mang các giá trị tương ứng trên dòng 1. Rồi lại gán mảng Current := Next và tiếptục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương ứng trêndòng 2 v.v... Vậy ta có cài đặt cải tiến sau:PROG01_2.PAS * Đếm số cách phân tích số nprogram Analyse2;constmax = 100;varCurrent, Next: array[0..max] of LongInt;n, m, v: Inte ...