Áp dụng nhân ma trận để tính số Fibonacci và 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
Bài toán tính số Fibonacci
Trước hết mình sẽ đi vào bài toán tính số Fibonacci. Để tìm số Fibonacci thứ N chúng ta tính theo công thức truy hồi sau:
\begin{cases}F_1 = F_2 = 1 \\ F_n = F_{n - 1} + F_{n - 2} (n > 2)\end{cases}
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ứ N. Công thức trên sẽ cho độ phức tạp là O(N), độ phức tạp này không phù hợp với các bài toán với N lớn.
Ngoài ra các bạn có thể sử dụng công thức sau:
F_n = \frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}
Coông thức này sẽ cho về một độ phức tạp rất tuyệt vời là O(1) 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:
\begin{cases}F_{2k} = F_k \times (2F_{k+1}-F_k) \\ F_{2k+1} = F_{k+1}^2+F_k^2\end{cases}
Cài đặt với C++
Ta cài đặt với C++ như sau:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <bits/stdc++.h> using namespace std; pair<int64_t, int64_t> 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 main() { int n = 5; auto ans = fibo(n); cout << ans.first << '\n'; // số fibo thứ N cout << ans.second << '\n'; // số fibo thứ N+1 return 0; } |
Chương trình này sẽ tính ra lần lượt số Fibonacci thứ N và N+1 như mình đã comment ở trên:
|
1 2 |
5 8 |
Các bạn có thể dùng Python hoặc số lớn trong C++ để có thể thấy rõ ràng sự chênh lệch tốc độ giữa 2 cách này nhé.
Bài toán tính lũy thừa của một số
Bài toán tính lũy thừa m của một số n tức tính n^m cũng là một bài toán mà bất kì lập trình viên nào cũng phải trải qua. Thông thường chúng ta sẽ tính như sau:
|
1 2 3 4 5 6 7 |
int64_t Pow(int n, int m) { int64_t ans = 1; for (int i = 0; i < m; ++i) ans *= n; return ans; } |
Các này sẽ cho độ phức tạp là O(N). Ngoài ra bạn có thể sử dụng cách tính bằng đệ quy, cách này dễ cài đặt hơn nhưng cũng sẽ cho độ phức tạp là O(N):
|
1 2 3 4 5 6 |
int64_t Pow(int n, int m) { if (m == 0) return 1; return Pow(n, m - 1) * n; } |
2 cách này là không đủ nhanh trong trường hợp với các bài toán tính lũy thừa lấy phần dư nhưng m rất lớn có thể lên tới 10^9 hoặc lớn hơn.
Chúng ta sẽ thay đổi một chút để lấy được một tốc độ thuật toán tốt hơn.
Ý tưởng nhân ma trận
Ở đây mình có ý tưởng như sau. Với việc a^0 luôn bằng 1. Chúng ta sẽ chỉ cần xử lý nốt phần còn lại với số mũ khác 0. Minh sẽ có công thức như sau:
a^n = \begin{cases} 1 &\text{nếu } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{nếu } n > 0 \text{ và } n \text{ chẵn}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{nếu } n > 0 \text{ và } n \text{ lẻ}\\ \end{cases}
Mình xin phép được trình bày công thức luôn, vì phần này khá khó để có thể chứng minh.
Cài đặt bằng C++
Từ công thức trình bày ở phần trên chúng ta có thể viết lại hàm tính lũy thừa như sau:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <bits/stdc++.h> using namespace std; int64_t Pow(int64_t a, int64_t b) { if (b == 0) return 1; int64_t result = Pow(a, b / 2); if (b % 2) return result * result * a; else return result * result; } int main() { int n = 123948; int64_t ans = Pow(n, 2); cout << ans << '\n'; return 0; } |
Chương trình cho ra kết quả:
|
1 |
15363106704 |
Mình sẽ viết lại một chút, dành cho những bạn thích sự gọn gàng :)))
|
1 2 3 4 5 6 7 8 9 10 |
int64_t Pow(int64_t a, int64_t b) { int64_t result = 1; while (b > 0) { if (b & 1) result = result * a; a = a * a; b >>= 1; } return result; } |
Bài toán tính lũy thừa phần dư
Một bài toán khác nâng cao hơn với bài toán tính lũy thừa lấy phần dư. Số chia ở đây sẽ tùy thuộc vào bài toán.
Giả sử với bài toán tính lũy thừa a^b mod m. Mình sẽ chỉnh sửa lại hàm Pow như sau:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <bits/stdc++.h> using namespace std; int64_t Pow(int64_t a, int64_t b, int64_t m) { a %= m; int64_t result = 1; while (b > 0) { if (b & 1) result = result * a % m; a = a * a % m; b >>= 1; } return result; } int main() { int n = 123948; int64_t ans = Pow(n, 2, 1000000007); cout << ans << '\n'; return 0; } |
Chương trình này sẽ cho ra kết quả của a^b mod m với mod là phép chia lấy dư. Trong trường hợp này mình làm với a = 123948, b = 2, m = 1000000007 (10^9 + 7).
|
1 |
363106599 |
Tất cả các thuật toán cài đặt với C++ ở trên đều có độ phức tạp là O(logN).
Ngoài ra, với số chia m là số nguyên tố chúng ta có thể dùng định lý Fermat nhỏ, các bạn có thể tham khảo thêm tại đây.
Tổng kết
Như vậy là trong bài viết này mình đã hướng dẫn các bạn những cách khác tối ưu hơn để giải quyết bài toán tìm số Fibonacci thứ N hay tính lũy thừa của một số bất kì cũng như là bài toán lũy thừa lấy phần dư. Đây cũng là kiến thức các bạn nên nắm được cũng như là phải biết nếu tham gia các kì thi như OI hay ICPC… . Cảm ơn bạn đã đọc bài viết này. Hãy tiếp tục ủng hộ Lập trình không khó trong các bài viết tiếp theo nhé !
![Ebook “300 bài code thiếu nhi” [PDF]](https://blog.luyencode.net/wp-content/uploads/2021/04/300-bai-code-thieu-nhi.jpg)
