CTDL và giải thuật - Giải thuật chia để trị

Cho một dãy gồm n số nguyên và một số nguyên x. Hãy đếm xem trong dãy có bao nhiêu phần tử có giá trị x.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    5
    1 2 3 2 4
    2

    2

    Với a = [1, 2, 3, 2, 4] và x = 2 thì kết quả mong muốn là 2.
     
  • Test mẫu 2:
    Input Output

    4
    1 3 4 2
    5

    0


    Với a = [1, 3, 4, 2] và x = 5 thì kết quả mong muốn là 0.

Lý thuyết.

Giới thiệu giải thuật chia để trị (Divide and Conquer).

Phương pháp chia để trị (Divide and Conquer) là một phương pháp quan trọng trong việc thiết kế các giải thuật. Ý tưởng của phương pháp này khá đơn giản và rất dễ hiểu: Khi cần giải quyết một bài toán, ta sẽ tiến hành chia bài toán đó thành các bài toán con nhỏ hơn. Tiếp tục chia cho đến khi các bài toán nhỏ này không thể chia thêm nữa, khi đó ta sẽ giải quyết các bài toán nhỏ nhất này và cuối cùng kết hợp giải pháp của tất cả các bài toán nhỏ để tìm ra giải pháp của bài toán ban đầu.

Nếu bạn còn nhớ thì hai giải thuật sắp xếp Quick Sort và Merge Sort cũng là hai thuật toán điển hình áp dụng giải thuật chia để trị.

Các bước trong giải thuật chia để trị.

Bước 1: Chia nhỏ (Divide/Break)

Trong bước này, chúng ta chia bài toán ban đầu thành các bài toán con. Mỗi bài toán con nên là một phần của bài toán ban đầu. Nói chung, bước này sử dụng phương pháp đệ qui để chia nhỏ các bài toán cho đến khi không thể chia thêm nữa. Khi đó, các bài toán con được gọi là "atomic – nguyên tử", nhưng chúng vẫn biểu diễn một phần nào đó của bài toán ban đầu.

Bước 2: Giải bài toán con (Conquer/Solve)

Trong bước này, các bài toán con được giải.

Bước 3: Kết hợp lời giải (Merge/Combine)

Sau khi các bài toán con đã được giải, trong bước này chúng ta sẽ kết hợp chúng một cách đệ qui để tìm ra giải pháp cho bài toán ban đầu.

Hạn chế của giải thuật chia để trị (Devide and Conquer)

Giải thuật chia để trị tồn tại hai hạn chế, đó là:

  • Làm thế nào để chia tách bài toán một cách hợp lý thành các bài toán con, bởi vì nếu các bài toán con được giải quyết bằng các thuật toán khác nhau thì sẽ rất phức tạp.

  • Việc kết hợp lời giải các bài toán con được thực hiện như thế nào.

Hướng dẫn bài tập.

Bài này có rất nhiều phương án giải quyết, hãy thử làm nó theo cách chia để trị.

Chúng ta sẽ chia dãy thành các phần nhỏ hơn, cho đến khi các dãy chỉ còn một phần tử.

int count(int a[], int l, int r, int x){
	if (l == r){
		if (a[l] == x) return 1;
		else return 0;
	} else {
		int m = (l+r)/2;
		return count(a, l, m, x) + count(a, m+1, r, x);
	}
}

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int a[100001];
int count(int a[], int l, int r, int x){
	if (l == r){
		if (a[l] == x) return 1;
		else return 0;
	} else {
		int m = (l+r)/2;
		return count(a, l, m, x) + count(a, m+1, r, x);
	}
}
int main(){
	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	cin >> x;
	cout << count(a, 0, n-1, x);
	return 0;
}