Phương pháp truy hồi

1.1. VÍ DỤ

Cho số tự nhiên n £ 100. Hãy cho thấy thêm có bao nhiêu cách so với số n thành tổng của dãy các số nguyên dương, những cách phân tích là hoạn của nhau chỉ tính là 1 trong những cách.

Bạn đang xem: Phương pháp truy hồi

Ví dụ: n = 5 bao gồm 7 bí quyết 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 là có 1 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 vấn đề này, trong phân mục trước ta vẫn dùng phương pháp liệt kê tất cả các giải pháp phân tích với đếm số cấu hình. Bây giờ ta thử nghĩ xem, có bí quyết nào tính ngay ra số lượng các bí quyết phân tích mà không cần thiết phải liệt kê hay là không ?. Cũng chính vì khi số biện pháp phân tích kha khá lớn, cách thức liệt kê tỏ ra tương đối chậm. (n = 100 bao gồm 190569292 phương pháp phân tích).

Nhận xét:

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

Loại 1: Không đựng số m trong phép phân tích, lúc ấy số biện pháp phân tích các loại này đó là số giải pháp phân tích số v thành tổng các số nguyên dương v thì cụ thể chỉ có các cách phân tích một số loại 1, còn vào trường hợp m £

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

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

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

Ví dụ cùng 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ử ở sản phẩm trên: F và 1 phần tử ở cùng hàng, bên trái: F.

Ví dụ F<5, 5> sẽ tiến hành tính bởi F<4, 5> + F<5, 0>, xuất xắc F<3, 5> sẽ được tính bởi F<2, 5> + F<3, 2>. Bởi vì vậy nhằm tính F thì F với F phải được tính trước. Suy ra sản phẩm tự phù hợp để tính các bộ phận trong bảng F sẽ buộc phải là theo sản phẩm công nghệ tự từ trên xuống cùng trên mỗi sản phẩm thì tính theo thiết bị tự từ bỏ trái qua phải.

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

Vậy lời giải dựng rất đối chọi giản: Khởi tạo loại 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, tiếp đến dùng cách làm truy hồi tính ra toàn bộ các thành phần của bảng F. Cuối cùng F là số phương pháp phân tích đề xuất tìm.

P_3_01_1.PAS * Đếm số giải pháp phân tích số n

program Analyse1; Bài toán đối chiếu 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 cái 0 của bảng F toàn số 0

F<0, 0> := 1; Duy chỉ gồm F<0, 0> = 1

for m := 1 to n do Dùng bí quyết tính các dòng theo máy tự từ trên xuống dưới

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