Thuật toán chia để trị

Thuật toán chia để trị(Devide and Conquer)

1. Giới thiệu
   Chia để trị là 1 phương pháp áp dụng cho các bài toán có thể giải quyết bằng cách chia nhỏ ra thành các bài toán con từ việc giải quyết các bài toán con này. Sau đó lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu.
2. Các bước
   Gồm 3 bước:
   
   1. Devide (Chia). Chia bài toán lớn thành những bài toán con có cùng kiểu với bài toán lớn.
   2. Conquer (Trị). Giải các bài toán con. Thông thường các bài toán con chỉ khác nhau về dữ liệu vào nên ta có thể thực hiện bằng một thủ tục đệ qui.
   3. Combine (Tổng hợp). Tổng hợp lại kết quả của các bài toán con để nhận được kết quả của bài toán lớn
3. Các giải thuật con điển hình
   
   1. Thuật toán tìm kiếm nhị phân (Binary-Search): update
   2. Thuật toán Quick-Sort : update
   3. Thuật toán Merge-Sort : update
   4. Thuật toán Strassen nhân hai ma trận.
   5. Thuật toán Karatsuba tính toán phép nhân…
4. Ví dụ đơn giản
   Tính lũy thừa
   Input: a,n : số nguyên
   Output: giá trị aⁿ
   Ý tưởng:
   1. Chia: chia nhỏ thành 2 bài toán con là tính lũy thừa bậc chẵn và lũy thừa bậc lẻ
      VD: a^m+n = a^m * aⁿ với 2⁸=2⁴*2⁴
   2. Trị: tiếp tục chia nhỏ bài toán đến n=1 thì trả về giá trị là a.
      if(n==1) return a;
   3. Tổng hợp: Trong quá trình chia nhỏ ta đã phân tích lũy thừa thành tích các lũy thừa nhỏ hơn và cuối cùng chỉ cần nhân vào thôi
   
   Code:
   

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

   
   Lưu ý: ta sẽ phải đệ quy 2 lần với luythua(a,n/2). Việc code như vậy sẽ làm tăng độ phức tạp của thuật toán, vì vậy ta có thể dùng 1 biến tạm lưu giá trị luythua(a,n/2) để tránh phải đệ quy 2 lần
   

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