Trong bài viết này, chúng ta sẽ khám phá một kỹ thuật tính toán hàm mũ nhanh, một phương pháp được ứng dụng rộng rãi trong các bài toán liên quan đến số học. Hãy cùng nhau khám phá xem hàm mũ nhanh là gì và cách áp dụng nó!
Điều cần biết trước
Để hiểu bài viết này một cách tốt nhất, bạn nên có kiến thức cơ bản về:
- Biến, kiểu dữ liệu và toán tử trong c+ +
- Câu điều kiện, vòng lặp và hàm trong C++
- Mảng trong C++
- Các kiến thức cần thiết để theo dõi khóa học
- Đệ quy
Trong bài viết này, chúng ta sẽ tập trung vào kỹ thuật "hàm mũ nhanh".
Bài toán đặt ra
Hãy xem xét một bài toán nhỏ sau đây:
Cho một số nguyên dương n. Hãy tính và in ra giá trị của n^k, trong đó k là một số nguyên dương nhỏ hơn n^k.
Ví dụ:
Input: 3 4 Output: 81
Lời giải ban đầu
Theo định nghĩa của n^k, ta có n^k = n n n ... n (k lần nhân n với chính nó). Vì vậy, ta có thể sử dụng vòng lặp để tính kết quả.
Dưới đây là một ví dụ về cách triển khai ý tưởng này trong code:
#include using namespace std; typedef long long ll; int n, k; ll power(int n, int k){ ll res = 1; while(k--) res *= n; return res; } int main(){ cin >> n >> k; cout << power(n, k) << endl; return 0; } Tuy nhiên, phương pháp này có độ phức tạp là O(k). Liệu có cách nào tối ưu hơn không?
Nhận xét
Hãy xem xét một vài biến đổi dựa trên định nghĩa của k (n,k ≤ 100).
Giả sử k là số chẵn, ta có: n^k = (n^(k/2)) * (n^(k/2)).
Do đó, nếu k là số chẵn, ta chỉ cần tính n^(k/2) và nhân hai giá trị này với nhau.
Với k là số lẻ, thì ta có: n^k = n^(k-1) * n.
Khi này k-1 là số chẵn, ta có thể áp dụng phương pháp trên để tính n^(k-1).
Từ hai nhận xét trên, ta có thể suy ra quy tắc sau: n^k = n^(k/2) n^(k/2) (nếu k chẵn) n^k = n^(k-1) n (nếu k lẻ)
Các bạn có nhận ra mô hình trên quen thuộc không? Đó chính là mô hình của đệ quy mà chúng ta đã tìm hiểu ở những bài trước. Vậy nên, chúng ta có thể sử dụng đệ quy để giải quyết bài toán này. Tuy nhiên, công thức trên vẫn chưa hoàn chỉnh. Các bạn có nhận ra điều gì thiếu không?
Câu trả lời là giá trị cơ sở. Vậy giá trị cơ sở ở đây là gì? Ta thấy biến k luôn bị chia đôi cho đến khi k = 0. Nhớ rằng, n^0 = 1. Đây chính là giá trị cơ sở.
Công thức hoàn chỉnh sẽ như sau: n^k = n^(k/2) n^(k/2) (nếu k chẵn) n^k = n^(k-1) n (nếu k lẻ) n^0 = 1
Lời giải cải tiến
Dựa trên công thức trên, ta có thể triển khai một phiên bản cải tiến của code:
#include using namespace std; typedef long long ll; int n, k; ll power(int n, int k){ if(k == 0) return 1; ll res = power(n, k / 2); if(k % 2) return res * res * n; return res * res; } int main(){ cin >> n >> k; cout << power(n, k) << endl; return 0; } Độ phức tạp của chương trình trên là O(logk). Vì qua mỗi bước, giá trị k lại bị chia đôi, do đó số lần gọi đệ quy là k.
Kết luận
Qua bài viết này, chúng ta đã tìm hiểu về kỹ thuật "hàm mũ nhanh" và cách áp dụng nó. Đây là một kỹ thuật tính toán quan trọng trong số học và có thể giúp giảm đáng kể thời gian tính toán.
Trong bài viết tiếp theo, chúng ta sẽ tìm hiểu về "Hash".
Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý để chúng ta có thể phát triển bài viết tốt hơn. Hãy luôn luyện tập, thử thách và không ngại khó!
Thảo luận
Nếu bạn có bất kỳ khó khăn hay thắc mắc nào về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để được sự hỗ trợ từ cộng đồng.
