Hàm mũ nhanh

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ũ được sử dụng rộng rãi trong các bài toán số học. Cùng nhau tìm hiểu nào!

Tìm hiểu về hàm mũ nhanh

Để hiểu kỹ thuật này, chúng ta cần có kiến thức cơ bản về:

Bạn đang xem: Hàm mũ nhanh

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong 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ìm hiểu về hàm mũ nhanh.

Bài toán đặt ra

Giả sử chúng ta có một bài toán như sau: Cho một số nguyên dương n, hãy tính giá trị của n^n, với điều kiện kết quả nhỏ hơn 10^18.

Ví dụ:

• Input: 3
  Output: 27

Lời giải ban đầu

Theo định nghĩa của hàm mũ, ta có thể triển khai code như sau:

#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(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> k;
    cout << power(n, k) << endl;
    return 0;
}

Tuy nhiên, độ phức tạp của chương trình trên là O(k). Có cách nào để giảm thời gian thực hiện không?

Nhận xét

Hãy cùng nhìn lại định nghĩa của hàm mũ. Giả sử n = 2 và k = 8. Lúc này, ta có thể tính 2^8 như sau:

2^8 = (2^4)^2 = (2^2)^2 * 2 = (2^1)^2 * 2 * 2 = 2 * 2 * 2 * 2 = 16

Từ hai nhận xét trên, ta có thể đưa ra quy tắc sau: Nếu k là số chẵn, ta có thể áp dụng phương pháp trên để tính n^k. Ngược lại, ta sẽ giảm k đi 1 và tính n^k theo công thức n^k = (n^(k/2))^2 * n.

Lời giải cải tiến

Xem thêm : Nghị luận về Sự lười biếng

Từ công thức trên, ta có thể triển khai code như sau:

#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(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> k;
    cout << power(n, k) << endl;
    return 0;
}

Vậy thì độ phức tạp của chương trình trên là O(log k).

Kết luận

Qua bài viết này, chúng ta đã nắm được cách tính hàm mũ nhanh. Tiếp theo, chúng ta sẽ tìm hiểu về Hash.

Chúng ta đã tìm hiểu cùng nhau về hàm mũ nhanh và giải quyết bài toán như thế nào. Nếu bạn có bất kỳ câu hỏi hay góp ý nào, hãy để lại bình luận để chúng ta có thể cùng phát triển bài viết tốt hơn. Cảm ơn bạn đã theo dõi bài viết!

Thảo luận

Nếu bạn gặp 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 để nhận được sự hỗ trợ từ cộng đồng.

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập