Áp dụng nhân ma trận để tính số Fibonacci và lũy thừa

0
296

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.

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:

Chương trình này sẽ tính ra lần lượt số Fibonacci thứ NN+1 như mình đã comment ở trên:

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:

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):

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:

Chương trình cho ra kết quả:

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 :)))

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:

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).

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é !

Là một học sinh cấp 3 có niềm đam mê mãnh liệt với lập trình.
Theo dõi
Thông báo của
guest
0 Bình luận
Phản hồi nội tuyến
Xem tất cả bình luận