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 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 hai loạ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 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 nếu m > v

F = F + F nếu m £ v

Ta có công thức xây dựng F từ F và F. Công thức này có tên gọi là công thức truy hồi đưa việc tính F về việc tính các F với dữ liệu nhỏ hơn. Tất nhiên cuối cùng ta sẽ quan tâm đến F: Số các cách phân tích n thành tổng các số nguyên dương £ n.

Ví dụ với n = 5, bảng F sẽ là:

*

Nhìn vào bảng F, ta thấy rằng F được tính bằng tổng của:

Một phần tử ở hàng trên: F và một phần tử ở cùng hàng, bên trái: 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 thì F và F phải được tính trước. Suy ra thứ 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.

Đ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 là số cách phân tích cần tìm.


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 := Current + Next; Current := Next; {Gán Current := Next tức là Current bây giờ lại lưu các phần tử trên dòng m của bảng F} end; WriteLn(Current, ' Analyses');end.


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 đóng vai trò là dòng hiện thời trong bảng phương án} y := 2; {Dòng B đóng vai trò là dòng kế tiếp trong bảng phương án} for m := 1 to n do begin {Dùng dòng x tính dòng y Û Dùng dòng hiện thời trong bảng phương án để tính dòng kế tiếp} for v := 0 to n do if v else B := B + B; x := 3 - x; y := 3 - y; {Đảo giá trị x và y, tính xoay lại} end; WriteLn(B, ' Analyses');end.


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 := L + L;WriteLn(L, ' Analyses');end.


1.4. CÀI ĐẶT ĐỆ QUY

Xem lại công thức truy hồi tính F = F + F, ta nhận thấy rằng để tính F ta phải biết được chính xác F và F. Như vậy việc xác định thứ tự tính các phần tử trong bảng F (phần tử nào tính trước, phần tử nào tính sau) là quan trọng. Tuy nhiên ta có thể tính dựa trên một hàm đệ quy mà không cần phải quan tâm tới thứ tự tính toán. Việc viết một hàm đệ quy tính công thức truy hồi khá đơn giản, như ví dụ này ta có thể viết:


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, nếu F chưa biết thì hàmGetF(m, v) sẽ gọi đệ quy để tính giá trị của F rồi dùng giá trị này gán cho kết quả hàm, còn nếu F đã biết thì hàm này chỉ việc gán kết quả hàm là F mà không cần gọi đệ quy để tính toán nữa.


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 = -1 then {Nếu F chưa biết thì đi tính F} begin if m = 0 then {Phần neo của hàm đệ quy} if v = 0 then F := 1 else F := 0 else {Phần đệ quy} if m > v then F := GetF(m - 1, v) else F := GetF(m - 1, v) + GetF(m, v - m); end; GetF := F; {Gán kết quả hàm bằng F}end;begin Write('n = '); ReadLn(n); FillChar(f, SizeOf(f), $FF); {Khởi tạo mảng F bằng giá trị -1} WriteLn(GetF(n, n), ' Analyses');end.

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