PHƯƠNG PHÁP TRUY HỒI

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.