Phương Pháp Truy Hồi

1.1. VÍ DỤ

Cho số tự nhiên n £ 100. Hãy cho biết có từng nào cách so sánh số n thành tổng của dãy những số nguyên dương, các cách phân tích là thiến 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 tất cả 7 giải pháp 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 xem như là có một cách phân tích thành tổng những số nguyên dương (0 là tổng của hàng rỗng))

Để giải bài toán này, trong chuyên mục trước ta đang dùng cách thức liệt kê tất cả các biện pháp phân tích với đếm số cấu hình. Bây giờ ta thử nghĩ xem, có giải pháp nào tính ngay ra con số các phương pháp phân tích mà không cần phải liệt kê hay không ?. Bởi vì khi số biện pháp phân tích kha khá lớn, phương pháp liệt kê tỏ ra hơi chậm. (n = 100 tất cả 190569292 biện pháp phân tích).

Nhận xét:

Nếu điện thoại tư vấn F là số giải pháp phân tích số v thành tổng các số nguyên dương £ m. Lúc đó: những cách phân tích số v thành tổng những số nguyên dương £ m có thể chia có tác dụng hai loại:

Loại 1: Không chứa số m trong phép phân tích, khi ấy số biện pháp phân tích các loại này chính là số bí quyết phân tích số v thành tổng các số nguyên dương v thì ví dụ chỉ có những cách phân tích loại 1, còn trong trường phù hợp m £

v thì sẽ sở hữu cả những cách phân tích các loại 1 và nhiều loại 2. Vì thế: F = F ví như m > v

F = F + F nếu như m £ v

Ta gồm công thức xuất bản F từ bỏ F và F. Phương pháp này có tên gọi là công thức truy vấn hồi đưa vấn đề tính F về việc tính các F cùng với dữ liệu nhỏ dại hơn. Tất nhiên cuối cùng ta sẽ lưu ý đế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ụ cùng với n = 5, bảng F vẫn là:

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

Một thành phần ở hàng trên: F và 1 phần tử ở cùng hàng, mặt trái: F.

Ví dụ F<5, 5> sẽ tiến hành tính bằng F<4, 5> + F<5, 0>, giỏi F<3, 5> sẽ được tính bởi F<2, 5> + F<3, 2>. Bởi vì vậy để tính F thì F và F phải được xem trước. Suy ra trang bị tự hợp lý và phải chăng để tính các phần tử trong bảng F sẽ phải là theo thứ tự từ trên xuống cùng trên mỗi hàng thì tính theo thiết bị tự từ trái qua phải.

Điều đó gồm nghĩa là thuở đầu ta bắt buộc tính hàng 0 của bảng: F<0, v> = số dãy gồm các bộ phận £ 0 mà tổng bằng v, theo quy ước ở đề bài xích thì F<0, 0> = 1 còn F<0, v> với mọi v > 0 các là 0.

Vậy lời giải dựng rất đối chọi giản: Khởi tạo chiếc 0 của bảng F: F<0, 0> = 1 còn F<0, v> với đa số v > 0 đều bằng 0, tiếp nối dùng cách làm truy hồi tính ra toàn bộ các bộ phận của bảng F. ở đầu cuối F là số giải pháp phân tích đề nghị tìm.

P_3_01_1.PAS * Đếm số phương pháp phân tích số n

program Analyse1; Bài toán so với 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 loại 0 của bảng F toàn số 0

F<0, 0> := 1; Duy chỉ có F<0, 0> = 1

for m := 1 khổng lồ n do Dùng phương pháp tính những dòng theo lắp thêm tự từ trên xuống dưới

for v := 0 khổng lồ n bởi vì Các phần tử trên một chiếc thì tính theo máy 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 ra mảng Current tương ứng với loại 0 của bảng F for m := 1 to n do begin Dùng dòng bây chừ Current tính dòng tiếp đến Next Û Dùng cái m - 1 tính cái m của bảng F for v := 0 khổng lồ n do if v else Next := Current + Next; Current := Next; Gán Current := Next có nghĩa là Current hiện giờ lại lưu các thành phần trên cái m của bảng F end; WriteLn(Current, ' Analyses');end.