Góc học tập
18/01/2020 11:07:18 PM

Thuật toán chia để trị (devide and conquer)

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.

Phương pháp này gồm có 3 bước:

 

Bước 1: Chia/Tách nhỏ

Tại bước này thì bài toán ban đầu sẽ được chia thành các bài toán con cho đến khi không thể chia nhỏ được nữa. Các bài toán con kiểu sẽ trở thành 1 bước nhỏ trong việc giải quyết bài toán lớn.

Bước 2: Trị/Giải quyết bài toán con

Tại bước này ta sẽ phải tìm phương án để giải quyết cho bài toán con một cách cụ thể.

Bước 3: Kết hợp lời giải lại để suy ra lời giải

Khi đã giải quyết xong cái bài toán nhỏ, lặp lại các bước giải quyết đó và kết hợp lại những lời giải đó để suy ra kết quả cần tìm (có thể ở dạng đệ quy).

Ví dụ minh hoạ: Tìm phần tử nhỏ nhất không có trong một dãy các số nguyên dương khác nhau đã được sắp xếp.

 

#include
 
 
int smallestMissing(int arr[], int low, int high)
{
// base condition
if (low > high) return low;
 
int mid = low + (high - low) / 2;
 
// if mid index matches with the mid element, then the mismatch
// lies on the right half
if (arr[mid] == mid) return smallestMissing(arr, mid + 1, high);
else
// mismatch lies on the left half
return smallestMissing(arr, low, mid - 1);
}
 
// main function
int main(void)
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
 
int low = 0, high = n - 1;
 
printf("The smallest missing element is %d",
smallestMissing(arr, low, high));
 
return 0;
}

» Các tin khác: