Trang chủLập trìnhCTDL & Thuật toánTìm hiểu thuật toán chia để trị trong lập trình, ví dụ...

Tìm hiểu thuật toán chia để trị trong lập trình, ví dụ áp dụng

Thuật toán chia để trị là một trong những thuật toán được áp dụng tương đối nhiều trong các bài toán thực tế, vậy thuật toán chia để trị là gì, như thế nào, làm sao áp dụng thì chúng ta sẽ cùng tìm hiểu trong bài viết này.

Thuật toán chia để trị

Chia để trị nói đúng hơn thì đây chỉ là 1 phương pháp lập trình chứ chưa đúng với nghĩa thuật toán, phương pháp chia để trị có thể áp dụng được cho các thuật toán khác nhau.

Phương pháp chia để trị sử 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, Kết quả cuối cùng của bài toán sẽ được tổng hợp lại từ việc giải quyết các bài toán con này.

Hình ảnh mình họa thuật toán Merge Sort là 1 thuật toán sử dụng phương pháp chia để trị

Phương pháp chia để trị sẽ bao gồm 3 bước cơ bản sau:

Bước 1: Chia/Tách nhỏ: Tại bước này thì bài toán ban đầu sẽ được chia dần thành các bài toán con cho đến khi không thể chia nhỏ được nữa. Kiểu các bài toán con sẽ trở thành 1 bước nhỏ nhất trong việc giải quyết bài toán lớn, trong mảng thì thường chia tới mức chỉ còn 1 phần tử á@@

Bước 2: Trị/Giải quyết bài toán con: Hehe…tại bước này thì ta sẽ tìm cách giải quyết bài toán con đó một cách cụ thể tùy vào bài toán đưa ra.

Bước 3: Kết hợp lời giải lại để suy ra lời giải cuối cùng: 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, mình khá kém trong vấn đề trình bày và giải thích, thế mà phải giải thích thứ oái oăm, khó hiểu này. Cùng đi vào ví dụ cụ thể xem có dễ hiểu hơn không nhé!!

Áp dụng chia để trị vào các bài toán

Thuật toán sắp xếp nhanh Quick Sort

Thuật toán sắp xếp nhanh Quick Sort là một thuật toán áp dụng phương pháp Chia để trị.

Bước 1(chia): Thuật toán quicksort chia mảng cần sắp xếp array[1..n] thành 2 nửa dựa vào 1 phần tử có vị trí đúng.
Bước 2(trị): Sắp xếp mảng làm sao cho những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau(Trường hợp sắp xếp tăng dần, giảm thì ngược lại). Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1.
Bước 3: Bằng việc lặp các bước giải quyết các bài toán con trên ta sẽ thu được kết quả là mảng sẽ được sắp xếp.

Mình có một bài viết riêng về thuật toán sắp xếp nhanh Quick Sort, bạn đọc thêm nhé: Thuật toán sắp xếp nhanh (Quick Sort)

Chương trình sắp xếp nhanh Quick Sort

#include <stdio.h>
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int left = low;
    int right = high - 1;
    while(true){
        while(left <= right && arr[left] < pivot) left++; // Tìm phần tử >= arr[pivot]
        while(right >= left && arr[right] > pivot) right--; // Tìm phần tử <= arr[pivot]
        if (left >= right) break; // Đã duyệt xong thì thoát vòng lặp
        swap(arr[left], arr[right]); // Nếu chưa xong, đổi chỗ.
        left++; // Vì left hiện tại đã xét, nên cần tăng
        right--; // Vì right hiện tại đã xét, nên cần giảm
    }
    swap(arr[left], arr[high]); //Đổi chỗ phần từ left với pivot, khi đó pivot đứng đúng vị trí
    return left; // Trả về chỉ số sẽ dùng để chia đổi mảng
}
  
/* Hàm giải thuật quicksort */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
         và là phần tử chia mảng làm 2 mảng con trái & phải */
        int pi = partition(arr, low, high);
  
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
  
int main()
{
    int arr[] = {1, 8, 3, 9, 4, 5, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
 
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân cũng là một thuật toán được ứng dụng phương pháp chia để trị, thuật toán tìm kiếm nhị phân được ứng dụng trên mảng đã được sắp xếp.

Bước 1(Chia): Danh sách ban đầu sẽ được chia thành 2 nửa.

Bước 2: (Trị): Trong mỗi bước, so sánh phần tử cần tìm với phần tử nằm ở chính giữa danh sách. Nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc. Nếu chúng không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa trái hoặc nửa phải của danh sách.
Bước 3: Bằng việc lặp ta sẽ tìm được kết quả.

Mình cũng có một bài viết riêng về tìm kiếm nhị phân, bạn đọc thăm khảo thêm nhé: Thuật toán tìm kiếm nhị phân trong C/C++

Chương trình tìm kiếm nhị phân trên mảng sắp xếp

#include <stdio.h>
 
// Hàm tìm kiếm nhị phân 
int binarySearch(int arr[], int n, int x) {
  int r = n - 1; // chỉ số phần tử cuối
  int l = 0; // Chỉ số phần tử đầu tiên
  while (r >= l) {
    int mid = (l+r)/2; //vị trí ở giữa
  
    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
      return mid;
  
    // Nếu arr[mid] > x, cập nhật lại right
    if (arr[mid] > x)
      r = mid - 1;
    // Nếu arr[mid] < x, cập nhật lại left
    if (arr[mid] < x)
      l = mid + 1;
  }
  
  // Nếu không tìm thấy
  return -1;
}
  
int main(void) {
  int arr[] = {2,3,4,10,40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;
  int result = binarySearch(arr, n, x);
  if (result == -1)
     printf("Khong tim thay phan tu %d trong mang",x);
  else
    printf("%d xuat hien tai chi so %d", x, result);
  return 0;
}

Thuật toán sắp xếp trộn Merge Sort

Thuật toán sắp xếp trộn Merge Sort cũng là một thuật toán áp dụng phương pháp chia để trị.

Bước 1(Chia): Danh sách ban đầu sẽ được chia thành 2 nửa.

Bước 2(Trị): Khi mảng đã được chia tới mức nhỏ nhất là chỉ còn một phần tử ta trộn 2 mảng con với nhau theo đúng thứ tự phần tử.

Bước 3: Bằng việc lặp ta sẽ tìm được kết quả.

Mình cũng có một bài viết riêng về sắp xếp trộn Merge Sort, bạn đọc thăm khảo thêm nhé: Thuật toán sắp xếp trộn (Merge Sort)

Chương trình sắp xếp trộn

#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    //Tạo 2 mảng tạm con
    int L[n1], R[n2];
 /* Copy dữ liệu sang các mảng tạm */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
  
    i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
    j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai
    k = l; // Khởi tạo chỉ số bắt đầu của mảng lưu kết quả
/* Trộn hai mảng tạm vừa rồi vào mảng arr*/
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
//Lấy phần còn lại của dãy L cho vào cuối dãy arr nếu còn.
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 //Lấy phần còn lại của dãy R cho vào cuối dãy arr nếu còn.
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
  
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
     //Tìm chỉ số nằm giữa mảng để chia mảng thành 2 nửa:
        int m = l+(r-l)/2;
 
     // Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
 
     //Gọi hàm trộn
        merge(arr, l, m, r);
    }
}
 // Hàm xuất mảng 
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
    printf("%d ", A[i]);
    printf("\n");
}
  
  
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
  
    
    mergeSort(arr, 0, arr_size - 1);
    printf("\nSorted array:\n");
    printArray(arr, arr_size);
return 0;
}

[Xem tất cả bài viết chủ đề C/C++ tại đây]

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x