Tất nhiên để tính A mũ n trong lập trình C/C++ thì ta có thể tính luôn bằng hàm pow, hoặc không dùng hàm thì cũng có thể dùng cách đơn giản hơn là duyệt vòng lặp. Nhưng trong bài viết này chúng ta sẽ sử dụng chia để trị, mục đích là nhằm nắm chắc hơn phương pháp thuật toán này.
XEM THÊM Duyệt đồ thị, tìm kiếm đường đi dài nhất, đường đi ngắn nhất trong đồ thị Kiểm tra đồ thị liên thông trong bài toán đồ thị lập trình Sinh các chuỗi nhị phân có độ dài bằng n trong C/C++ Tìm dãy con có tổng trọng số lớn nhất trong lập trình C/C++ Tính A^n bằng phương pháp chia để trị Quy hoạch động tìm xâu con chung độ dài lớn nhất
Ta viết code chia để trị cho bài toán tính a mũ n như sau:
#include <iostream>
using namespace std;
long long chiadetri(int a,int n)
{
//2 trường hợp suy biến
if(n== 0 ) return 1;
if(n==1) return a;
//Chia đôi n và gọi đệ quy chia đệ trị
int temp = chiadetri(a,n/2);
//n&1 tương đương với nếu n là số lẻ - dấu & là toán tử thao tác trên bit
if(n&1) return temp*temp*a;//n lẻ trả vè kq là temp*temp*a
return temp*temp; //ngược lại trả về temp * temp
}
int main()
{
int a, n; cin>>a>>n;
cout<<"a^n = "<<chiadetri(a,n); //Gọi hàm tính a^n bằng pp chia để trị
}
[Xem tất cả bài viết chủ đề C/C++ tại đây]
Đọc thêm: Tìm hiểu thuật toán chia để trị trong lập trình, ví dụ áp dụng
