Hàm mũ nhanh

Dẫn nhập

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một kĩ thuật tính toán hàm mũ được áp dụng rất nhiều trong các bài toán liên quan đến số học. Hãy cùng nhau tìm hiểu xem nó là gì nhé!

---

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• 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++
• Các kiến thức cần thiết để theo dõi khóa học   
• Đệ quy

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Hàm mũ nhanh

---

Bài toán đặt ra

Ta có một bài toán như sau:

Cho một số nguyên dương  và số nguyên không âm . Hãy in ra giá trị của  , dữ liệu đảm bảo kết quả nhỏ hơn .

Ví dụ:

Input	Output
3 4	81

---

Lời giải ban đầu

Theo đúng như định nghĩa,  ( phần tử ). Do đó, ta nghĩ đến việc dùng vòng lặp để nhân  số nguyên  với nhau.

Triển khai ý tưởng trên ra code ta có như sau

#include<bits/stdc++.h>
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;
}

Các bạn có thể thấy ngay độ phức tạp của chương trình trên sẽ là . Vậy thì liệu có cách làm giảm thời gian thời gian không?

---

Nhận xét

Hãy cùng thử biến đổi một chút dựa vào định nghĩa của .

Giả sử  chẵn thì ta có

Do đó, ta nhận thấy rằng nếu  chẵn thì chỉ cần tính  rồi nhân hai giá trị lại với nhau.

Với  lẻ thì điều gì sẽ xảy ra?

Ta thấy nếu  lẻ thì ta có thể tính . Khi này  chẵn nên ta áp dụng phương pháp trên để tính .

Từ hai nhận xét trên ta có thể đưa ra được quy tắc sau

Các bạn có thấy mô hình trên quen không? Đó chính là mô hình của đệ quy mà ta đã nói ở những bài trước. Do đó, ta sẽ dùng đệ quy để giải quyết bài toán này. Tuy nhiên, nếu sử dụng đệ quy thì công thức trên là chưa đủ. Các bạn có nhận ra công thức trên thiếu gì không?

Câu trả lời chính là giá trị cơ sở. Vậy thì giá trị cơ sở ở đây là gì? Ta thấy biến  luôn bị chia đôi do đó đến lúc nào đó  sẽ về 0. Mặc khác, . Do đó, đây chính là giá trị cơ sở của ta.

Công thức trên đầy đủ sẽ như sau

---

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

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

#include<bits/stdc++.h>
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 sẽ là bao nhiêu? Ta thấy, qua mỗi bước, giá trị  lại bị chia đôi nên số lần gọi đệ quy là . Do đó, độ phức tạp thuật toán là .

---

Kết luận

• Qua bài này chúng ta đã nắm được về Hàm mũ nhanh
• Bài sau 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 ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – 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 gì 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.