Công thức truy hồi

1.1. VÍ DỤ

Cho số tự nhiên n £ 100. Hãy cho thấy thêm có từng nào cách so sánh 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à thiến của nhau chỉ tính là một cách.

Bạn đang xem: Công thức truy hồi

Ví dụ: n = 5 tất cả 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ó 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 dãy rỗng))

Để giải vấn đề này, trong phân mục trước ta đã dùng cách thức liệt kê toàn bộ các bí quyết 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 giải pháp phân tích mà không nhất thiết phải liệt kê hay không ?. Bởi vì khi số biện pháp phân tích tương đối lớn, phương thức liệt kê tỏ ra khá chậm. (n = 100 có 190569292 biện pháp phân tích).

Nhận xét:

Nếu call F là số phương pháp phân tích số v thành tổng các số nguyên dương £ m. Khi đó: các cách đối chiếu số v thành tổng những số nguyên dương £ m hoàn toàn 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ố phương pháp phân tích một số loại này đó là số bí quyết 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 các loại 1, còn trong trường phù hợp m £

v thì sẽ có được cả những cách phân tích loại 1 và nhiều loại 2. Bởi vì thế: F = F giả dụ m > v

F = F + F nếu m £ v

Ta có công thức tạo F từ bỏ F với F. Phương pháp này mang tên gọi là công thức truy tìm hồi đưa việc tính F về việc tính các F cùng với dữ liệu bé dại hơn. Tất nhiên ở đầu cuối 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 bộ phận ở hàng trên: F và một phần tử ở thuộc hàng, mặt trái: F.

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

Điều đó gồm nghĩa là thuở đầu ta đề nghị tính sản phẩm 0 của bảng: F<0, v> = số dãy bao gồm các phần tử £ 0 nhưng mà tổng bởi v, theo quy ước ở đề bài bác thì F<0, 0> = 1 còn F<0, v> với tất cả v > 0 đa số là 0.

Vậy giải mã dựng rất đơn giản: Khởi tạo cái 0 của bảng F: F<0, 0> = 1 còn F<0, v> với đa số v > 0 đều bởi 0, sau đó dùng công thức truy hồi tính ra tất cả các thành phần của bảng F. ở đầu cuối F là số phương pháp phân tích yêu cầu tìm.

P_3_01_1.PAS * Đếm số bí quyết 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 loại 0 của bảng F toàn số 0

F<0, 0> := 1; Duy chỉ tất cả F<0, 0> = 1

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

for v := 0 khổng lồ n do Các thành phần trên một dòng thì tính theo máy tự từ bỏ 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 chế tạo mảng Current tương xứng với chiếc 0 của bảng F for m := 1 lớn n do begin Dùng dòng hiện nay Current tính dòng kế tiếp Next Û Dùng mẫu m - 1 tính loại 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 lưu giữ các phần tử trên dòng m của bảng F end; WriteLn(Current, ' Analyses');end.