1.1. VÍ 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ủa dãy các số 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.
Bạn đang xem: Phương pháp truy hồi
Ví dụ: n = 5 có 7 cách phân tích:
1. 5 = 1 + 1 + 1 + 1 + 12. 5 = 1 + 1 + 1 + 23. 5 = 1 + 1 + 34. 5 = 1 + 2 + 25. 5 = 1 + 46. 5 = 2 + 37. 5 = 5
(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ất cả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem, có cách nào tính ngay ra số lượng các cách phân tích mà không cần phải liệt kê hay khô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 = 100 có 190569292 cách phân tích).
Nhận xét:
Nếu gọi F
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 v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong trường hợ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
F
Ta có công thức xây dựng F
Ví dụ với n = 5, bảng F sẽ là:

Nhìn vào bảng F, ta thấy rằng F
Một phần tử ở hàng trên: F
Ví dụ 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
Đ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ần tử £ 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ủa bảng F. Cuối cùng F
P_3_01_1.PAS * Đếm số cách phân tích số n
program Analyse1; {Bài toán phân tích số}
const
max = 100; var
F: array<0..max, 0..max> of LongInt; n, m, v: Integer;
begin
Write('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 constmax = 100; varCurrent, Next: array<0..max> of LongInt; n, m, v: Integer;begin Write('n = '); ReadLn(n); FillChar(Current, SizeOf(Current), 0); Current<0> := 1; {Khởi tạo mảng Current tương ứng với dòng 0 của bảng F} for m := 1 to n do begin {Dùng dòng hiện thời Current tính dòng kế tiếp Next Û Dùng dòng m - 1 tính dòng m của bảng F} for v := 0 to n do if v else Next
Cách làm trên đã tiết kiệm được khá nhiều không gian lưu trữ, nhưng nó hơi chậm hơn phương pháp đầu tiên vì phép gán mảng (Current := Next). Có thể cải tiến thêm cách làm này như sau:
P_3_01_3.PAS * Đếm số cách phân tích số n
program Analyse3;const max = 100;var B: array<1..2, 0..max> of LongInt;{Bảng B chỉ gồm 2 dòng thay cho 2 dòng liên tiếp của bảng phương án} n, m, v, x, y: Integer;begin Write('n = '); ReadLn(n); {Trước hết, dòng 1 của bảng B tương ứng với dòng 0 của bảng phương án F, được điền cơ sở quy hoạch động} FillChar(B<1>, SizeOf(B<1>), 0); B<1><0> := 1; x := 1; {Dòng B
1.3. CẢI TIẾN THỨ HAI
Ta vẫn còn cách tốt hơn nữa, tại mỗi bước, ta chỉ cần lưu lại một dòng của bảng F bằng một mảng 1 chiều, sau đó dùng mảng đó tính lại chính nó để sau khi tính, mảng một chiều sẽ lưu các giá trị của bảng F trên dòng kế tiếp.
P_3_01_4.PAS * Đếm số cách phân tích số n
program Analyse4;constmax = 100;varL: array<0..max> of LongInt; {Chỉ cần lưu 1 dòng}n, m, v: Integer;beginWrite('n = '); ReadLn(n); FillChar(L, SizeOf(L), 0); L<0> := 1; {Khởi tạo mảng 1 chiều L lưu dòng 0 của bảng} for m := 1 to n do {Dùng L tính lại chính nó} for v := m to n do L
1.4. CÀI ĐẶT ĐỆ QUY
Xem lại công thức truy hồi tính F
P_3_01_5.PAS * Đếm số cách phân tích số n dùng đệ quy
program Analyse5;varn: Integer;function GetF(m, v: Integer): LongInt;begin if m = 0 then {Phần neo của hàm đệ quy} if v = 0 then GetF := 1 else GetF := 0 else {Phần đệ quy} if m > v then GetF := GetF(m - 1, v) else GetF := GetF(m - 1, v) + GetF(m, v - m);end;begin Write('n = '); ReadLn(n); WriteLn(GetF(n, n), ' Analyses');end.
Phương pháp cài đặt này tỏ ra khá chậm vì phải gọi nhiều lần mỗi hàm GetF(m, v) (bài sau sẽ giải thích rõ hơn điều này). Ta có thể cải tiến bằng cách kết hợp với một mảng hai chiều F. Ban đầu các phần tử của F được coi là "chưa biết" (bằng cách gán một giá trị đặc biệt). Hàm GetF(m, v) khi được gọi trước hết sẽ tra cứu tới F
P_3_01_6.PAS * Đếm số cách phân tích số n dùng đệ quy
program Analyse6;const max = 100;var n: Integer; F: array<0..max, 0..max> of LongInt;function GetF(m, v: Integer): LongInt;begin if F
Xem thêm: Công Thức Toán Đại Số Lớp 11 Chi Tiết, Đầy Đủ Cả Năm, ✓ Công Thức Toán 11
Việc sử dụng phương pháp đệ quy để giải công thức truy hồi là một kỹ thuật đáng lưu ý, vì khi gặp một công thức truy hồi phức tạp, khó xác định thứ tự tính toán thì phương pháp này tỏ ra rất hiệu quả, hơn thế nữa nó làm rõ hơn bản chất đệ quy của công thức truy hồi.
« Prev: Giải thuật và lập trình: Lời mở đầu