SEQUENCE

Trong rất nhiều bài toán, ta đã đưa về được công thức truy hồi để giải quyết vấn đề, việc cuối cùng là giải công thức truy hồi đó để đưa ra lời giải. Thông thường thì tìm ra công thức truy hồi mới khó vì để tìm ra công thức truy hồi thì ta cần biết lý thuyết liên quan vấn đề cần giải quyết và phải suy luận nhiều, việc giải công thức truy hồi đơn giản hơn một chút, ta có một số kỹ thuật sau:

I. Dãy truy hồi và quy hoạch động

Đây là cách làm thông dụng nhất mà ta dùng khi đã có công thức truy hồi, vì nó dễ lập trình. Nhưng những bài toán rơi vào dạng này thì thường quá trình tìm ra công thức truy hồi hơi cực.

Do cách làm này khá quen thuộc, nên tôi chỉ lướt sơ qua. Giả sử ta có công thức F[N] = min{2*F[N-1], 3*F[N-2] + 3}+N. Với F[1] = 1, F[2] = 2, 1<=N<=10^6.

Ta khai báo một array để lưu lại các giá trị F[i] và tính kết quả từ dưới lên.

II. Dãy truy hồi tuyến tính và ma trận

Để bắt đầu tôi muốn hỏi một câu: để tính a^N mod M (trong đó a, N, M là số nguyên dương nhỏ hơn 10^9, mod là phép lấy phần dư) bạn thực hiện thế nào? Thông thường ta vẫn hay thực hiện:

Cách làm này chạy trong O(N), khá chậm khi N lớn. Nếu để ý a^N = (a^(N/2))^2, ta chỉ cần tính a^(N/2), sau đó bình phương lên. Tương tự để tính a^(N/2), ta cũng tính a^(N/4) rồi bình phương lên. Với cách làm này ta tính a^N chỉ trong O(logN).

Bỏ qua vấn đề đó đi, ta quay lại vấn đề chính. Ta xét ví dụ sau:

Bài toán: Ta có N (1<=N<=10^9) viên gạch kích thước 1x2, ta cần xếp N viên gạch kín cả vùng hình chữ nhật có kích thước 2xN. Có bao nhiêu cách xếp như vậy, bạn chỉ cần tính kết quả lấy phần dư khi chia cho 10003.

Giải quyết:

Với N=1, ta có 1 cách xếp.

Với N=2, ta có 2 cách xếp.

Với N>2, ta xét

Gọi F[N] là số cách xếp các viên gạch vào hình chữ nhật 2xN.

Nhìn hình vẽ, ta suy ra công thức truy hồi, F[N] = F[N-1]+F[N-2], với F[1]=1, F[2]=2. Đây chính là dãy Fibonacy.
Dựa vào công thức truy hồi này, ta có thể dùng một vòng for để chạy tìm ra kết quả, độ phức tạp là O(N), nhưng bài toán yêu cầu N có thể lên tới 10^9, cách làm này không giải quyết được trường hợp N lớn.

Thật ra ta có thể tìm ra công thức tổng quát của dãy Fibonacy. F[N] = q^N+(1/q)^N với q=(1+sqrt(5))/2. Khi N khá lớn, (1/q)^N tiến về 0. Ta chỉ cần tính Round(q^N), với Round() là hàm làm tròn. Nhưng khó khăn ở chổ q không là số nguyên, ta không dễ tính Round(q^N) (mod M). Hướng đi này có lẽ cũng khó hiện thực, ta thử tìm hướng đi khác:

Xét ma trận A = 

và vector f(N) = 

Ta thấy f(N) = A*f(N-1)

     = A*Af(N-2) = A^2*f(N-2)

     = A^3*f(N-3) = … = A^(N-2)f(2) (với N>1)

Quay lại yêu cầu bài toán, ta tìm F[N]. Thật ra tìm ra f(N) cũng là tìm được kết quả F[N], vì khi tìm được f(N) thì ta biết được F[N] và F[N-1]. Chú ý f(N) là một vector.

Theo công thức ta tính toán f(N) = A^(N-2)*f(2). Vậy chỉ cần tính A^(N-2) là ta có f(N), quay về bài toán nhân ma trận, ở đây N có thể lên tới 10^9.

Không phải tự dưng tôi hỏi bạn câu hỏi làm sao tính a^N. Để tính A^N cũng tương tự vậy, chỉ khác ở chổ thay vì nhân hai số, thì ta nhân 2 ma trận. Như vậy ta có thể tính A^N trong log(N), vấn đề coi như được giải quyết. Ta nhắc lại nhé, ta tìm F[N] => phải tìm f(N) => phải tìm A^N. Ý tưởng đã xong, bây giờ hiện thực thôi.

Đánh giá độ phức tạp: Do ma trận này kích thước 2x2, nhân hai ma trận ta mất thời gian khá ít, nên việc tính A^N chỉ mất trong O(logN).

Bạn có thể xem code tại đây

Nhận xét nhỏ: nếu bạn để ý, bài toán tính a^N chính là giải dãy truy hồi g[N]=a*g[N-1] với g[0]=1. Mọi thứ có liên quan với nhau, cái khó ta phải tìm ra tính tổng quát của các vấn đề cụ thể.
                                 

Tổng quát:

Tại sao ta lại có ma trận A, ta xét công thức truy hồi tuyến tính tổng quát:

F[N] = a0*F[N-1] + a1*F[N-2] + … + ak-1*F[N-k], với các số ai là hằng số và ta biết các giá trị F[0], F[1],...,F[k-1]. Ta tìm giá trị F[N] với N>=k.

Đặt ma trận A = 

Dòng đầu tiên là các hệ số trong công thức truy hồi, dòng thứ hai có tất cả các số là 0 trừ số thứ nhất là 1,…, dòng cuối cùng thì số kế cuối cùng là 1.
 và f(N) = 

Bạn hãy nhân A*f(N-1), kết quả chính là f(N). Nói cụ thể f(N) = A*f(N-1).=...=A^(N-k)*f(k).
Tới đây bạn có thể thực hiện tương tự như dãy Fibonacy.

Bạn có thể xem code tại đây.

Về độ phức tạp, như đã nói ở trên ta mất thời gian nhân hai trận và tính A^N, vậy độ phức tạp tổng cộng là O(k^3*logN), với k là kích thước của ma trận A.

III. Dãy số có công thức tổng quát dạng đa thức
Đối với dạng này, ta sẽ không cần biết công thức truy hồi của dãy số, nhưng ta vẫn có thể tìm ra công thức tổng quát của nó. Tức là ta tìm ra chính xác F[N] = p(N), với p(x) là một đa thức. Để tính F[N] thì ta chỉ việc thay số vào tính p(N). Để làm được điều này ta cần nhắc lại một ít lý thuyết.
1. Nếu ta có F[N] = F[N-1] + g(N), với g(N) là một đa thức bậc k, thì công thức tổng quát của F[N] là một đa thức bậc k+1.
2. Ta hoàn toàn có thể xác định được đa thức bậc k nếu ta biết được giá trị tại k+1 điểm khác nhau.

Dựa vào hai tính chất này, ta có thể tìm được công thức tổng quát của dãy số nếu ta dự đoán được nó có dạng đa thức.

Ví dụ: Xét hình vuông NxN (1<=N<=10^9) được kẻ như hình vẽ. Bạn hãy tính xem có bao nhiêu hình tam giác trong hình vuông đó, tính số dư kết quả khi chia cho 10003. 

Giải quyết: gọi F[N] là kết quả cho hình vuông NxN, hình vuông đỏ là F[N-1]. Với mỗi hình tam giác con bên ngoài hình vuông đỏ, nó góp phần tạo nhiều nhất không quá N tam giác. Mà ta có 2N-2 tam giác con bên ngoài, nên số tam giác F[N] hơn F[N-1] là đa thức theo N bậc không quá 2 ,vì nó sẽ không vượt quá N*(2N-2). Vì vậy F[N] = F[N-1]+g(N) với g(N) là một đa thức bậc không quá 2. Suy ra F[N] là đa thức bậc không quá 3. Để xác định đa thức bậc 3, ta cần giá trị tại 4 điểm, để đơn giản ta chọn N=1,2,3,4, tức là ta phải tính F[1], F[2], F[3], F[4].
Bằng cách đếm bằng tay, ta tính được F[1] = 2, F[2] = 10, F[3] = 28, F[4]= 60. Thật ra tôi viết một chương trình nhỏ để tính F[1], F[2], F[3], F[4]. Code đây, với code này chỉ chạy được khoảng tới N=10.

Do F[N] là đa thức bậc không quá 3, ta đặt F[N]=a*N^3+b*N^2+c*N+d. Thay N=1,2,3,4 vào ta giải hệ phương trình
a+b+c+d=1
8a+4b+2c+d=10
27a+9b+3c+d=28
64a+16b+4c+d=60.
Giải hệ này, ta được a=2/3, b=1, c=1/3, d=0.
Vậy F[N] = (2*N^3+3*N^2+N)/3 = N(N+1)(2N+1)/3.

Đã có công thức tổng quát, việc code thì dễ dàng. Chú ý với N=10^9 thì ta cần một xử lí nhỏ để tránh tràn số.

IV. Tổng kết:

Bài viết đã trình bày một vài phương pháp để giải các bài toán khi ta tìm được công thức truy hồi của chúng. Đối với N<=10^6, ta thường dùng quy hoạch động để giải chúng. Những trường hợp cần giải quyết với N lớn như N=10^9, ta cần xài 1 số kỹ thuật:
1. Giải ra công thức tổng quát theo N, thông thường thì ta ít tiếp cận cách làm này, vì nó mất ta nhiều thời gian và sử dụng nhiều phép biến đổi để giải.
2. Nếu công thức truy hồi dạng tuyến tính, ta có thể dùng ma trận để giải như đã đề cập mục II
3. Nếu ta xác định được F[N] là một đa thức, ta có thể áp dụng mục III để giải nó.

Người viết: Dương Thành Phong