Số Fibonacci sử dụng nhân ma trận là một giải thuật chia và trị giúp tìm số Fibonacci thứ N với đô phức tạp O[logN], nhanh hơn với phương pháp sử dụng quy hoạch động hay đệ quy bạn hay dùng.
Với kiến thức này thì phải có thể tìm số Fibonacci thứ 1018.
NỘI DUNG :
- Lý Thuyết
- Cài Đặt
- Video Tutorial
image
1. Lý Thuyết
Để tìm số Fibonacci thứ N có nhiều thuật toán :
- Đệ quy với độ phức tạp rất tệ O[1.618n]
- Quy hoạch động O[N]
- Nhân ma trận O[logN]
Nếu bạn tìm số Fibonacci thứ N với N ≤ 107 thì thì thuật toán quy hoạch động với độ phức tạp O[N] có thể chấp nhận được.
Tuy nhiên khi N lớn hơn thì ta cần một thuật toán hiệu quả hơn đó là dựa vào chia và trị, để học được bài này các bạn cần có kiến thức về phép nhân ma trận trong lập trình và lũy thừa nhị phân.
Nếu bạn chưa rõ có thể tham khảo tại blog của mình luôn
Cơ sở của thuật toán :
image
Như vậy để tính được số Fibonacci thứ N bạn chỉ cần tính lũy thừa của ma trận và in phần tử trong ma trận kết quả.
2. Cài Đặt
Bài toán này mình sẽ tính số Fibonacci và chia dư kết quả cho số 109 + 7.
Ở đây mình sẽ cài đặt theo cách là xây dựng một struct ma trận và nạp chồng toán tử nhân cho ma trận này.
Cách này thì khó hiểu khi xây dựng struct và nạp chồng nhưng lại dễ dàng sử dụng khi áp dụng vào khi tính lũy thừa.
Bài toán tính số Fibonacci và tính lũy thừa của một số là bài toán kinh điển trong lập trình. Nhưng các bài toán này ở dạng đơn giản thì sẽ vô cùng tiếp cận với các lập trình viên. Nhưng, những cách thường dùng của 2 bài tập trên thường đơn giản, thiếu chiều sâu và không đủ mạnh để chạy và tính toán với các bài toán tương tự, nhưng bộ test lại lớn thậm chí là rất lớn. Vậy trong bài viết ngày hôm nay chúng ta cùng tìm hiểu về một cách khác để giải bài toán này đó là phương pháp Nhân Ma Trận.
NỘI DUNG BÀI VIẾT
Trước hết mình sẽ đi vào bài toán tính số Fibonacci. Để tìm số Fibonacci thứ [latex]N[/latex] chúng ta tính theo công thức truy hồi sau:
[latex]\begin{cases}F_1 = F_2 = 1 \\ F_n = F_{n – 1} + F_{n – 2} [n > 2]\end{cases}[/latex]
Công thức này chắc nhiều bạn đã biết, đây là cách đơn giản nhất để tính số Fibonacci thứ [latex]N[/latex]. Công thức trên sẽ cho độ phức tạp là [latex]O[N][/latex], độ phức tạp này không phù hợp với các bài toán với [latex]N[/latex] lớn.
Ngoài ra các bạn có thể sử dụng công thức sau:
[latex]F_n = \frac{[\frac{1+\sqrt{5}}{2}]{n}-[\frac{1-\sqrt{5}}{2}]{n}}{\sqrt{5}}[/latex]
Coông thức này sẽ cho về một độ phức tạp rất tuyệt vời là [latex]O[1][/latex] nhưng vấn đề là công thức này quá dài dòng, khó nhớ. Chúng ta chỉ nhớ được khi có google :]]].
Tính nhanh số Fibonacci với nhân ma trận
Khi sử dụng nhân ma trận công thức tổng quát sẽ là như sau:
[latex]\begin{cases}F_{2k} = F_k \times [2F_{k+1}-F_k] \\ F_{2k+1} = F_{k+1}^2+F_k^2\end{cases}[/latex]
Cài đặt với C++
Ta cài đặt với C++ như sau:
include
using namespace std; pair fibo[int n] {
if [n == 0]
return {0, 1};
auto p = fibo[n >> 1];
int c = p.first * [2 * p.second - p.first];
int d = p.first * p.first + p.second * p.second;
if [n & 1]
return {d, c + d};
return {c, d};
int n = 5;
auto ans = fibo[n];
cout 0] {
if [b & 1]
result = result * a % m;
a = a * a % m;
b >>= 1;
}
return result;
int n = 123948;
int64_t ans = Pow[n, 2, 1000000007];
cout