[Chia để trị] Tính lũy thừa a^n

Giờ rảnh được chút, làm thêm một bài nữa về một thuật toán cơ bản: tính lũy thừa aⁿ bằng phương pháp chia để trị.
Chắc mọi người đa số hay dùng vòng lặp nhỉ (cứ ừ đại đi), bây giờ đổi gió xíu nhé

Vào luôn vấn đề, như mọi người đã biết, aⁿ được tính bằng cách nhân n lần số a (nói vậy cho gọn đi)
Mình lấy ví dụ:

a⁸ = a . a . a . a . a . a . a . a (8 chữ a lận nhé)

Ta nhận thấy rằng có thể chia nửa cái phép tính trên kia ra, như thế này:

a⁸ = a^{4 + 4} = a⁴ . a⁴

trong đó, a⁴ có thể được tính:

a⁴ = a² . a²

Lại một lần nữa chia nhỏ :

a² = a¹ . a¹ = a . a

Đến đây ra có thể dễ dàng đưa ra a (a cùng n là input của bài toán này).

Vậy ta nhận ra được phần base case của thuật đệ quy ở đây (hay nhiều sách tiếng Việt gọi là phần neo ấy, mình học trên Khan nên đọc quen rồi) chính là khi số mũ đưa về 1, ta có thể đưa thẳng ra giá trị a

• Từ đó ta suy ra cách giải quyết bài toán thế này: chia nhỏ số mũ n ra cho đến khi n = 1

Vậy hàm pow với tham số : int pow(int a, int n)
Sẽ có phần base case:

if(n == 1)
    return a;

Thế còn recursive case (phần đệ quy) ? Thì theo như ví dụ ở trên, ta có công thức:

aⁿ = a^n/2 . a^n/2

Chuyển ra code:

return pow(a, n/2) * pow(a, n/2);

Thế nhưng nếu n là một số lẻ thì sao? Ví dụ như n = 3:

a⁵ = a . a . a . a . a (1)
Thì trong trường hợp này, n/2 sẽ bằng 5/2 = 2 (do n kiểu int nên số sẽ tự bỏ đi phần thập phân)
(1) = a² . a² . a
do là số lẻ nên khi khi mod 2 (chia lấy dư) thì số dư sẽ luôn luôn là 1
=> Với n là số lẻ, khi chia ra sẽ luôn thừa một số a

Vậy ta suy ra công thức:

aⁿ = a^n/2 . a^n/2 với n là số lẻ

hay chuyển ra code:

return pow(a, n/2) * pow(a, n/2) * a;

Tổng hợp lại công thức tổng quát:

aⁿ =

• a^n/2 * a^n/2 nếu n chẵn
• a^n/2 * a^n/2 * a nếu n lẻ

Và cuối cùng là code, dài dòng lê thê lắm rồi:

int pow(int a, int n)
{
    if(n == 1) {
        return a;
    } else { 
        if(n % 2 == 0)
            return pow(a, n/2) * pow(a, n/2);
        else
            return pow(a, n/2) * pow(a, n/2) * a;
    }
}

Thế nhưng, ta lại thấy code trên có 1 điểm không tốt, đó chính là trong phần đệ quy, hàm pow được tính 2 lần trong khi chúng giống hệt nhau:

return pow(a, n/2) * pow(a, n/2);

Vậy ta sẽ gán chúng vào một biến, như thế thì sẽ đỡ phải tính lại thêm 1 lần:

int pow(int a, int n)
{
    if(n == 1) {
        return a;
    } else {
        int temp = pow(a, n/2);
        if(n % 2 == 0)
            return temp * temp;
        else
            return temp * temp * a;
    }
}

Code ngắn gọn hơn xíu:

int pow(int a, int n)
{
    if(n == 1) return a;
    int tmp = pow(a, n/2);
    return (n & 1) ? tmp * tmp * a : tmp * tmp;
}

Cập nhật:

Dùng vòng for(i=0->n): dpt=O(n)

Dùng chia để trị: T(n)= T(n/2)+O(1) => dpt=O(logn)

=> Dùng phương pháp chia để trị nhanh hơn là dùng vòng lặp

Kết thúc bài chưa có kinh nghiệm nên viết bài có vẻ lê thê quá, mọi người thông cảm