Giới thiệu về thuật toán chia để trị

[nguyennhathoang]

Ý TƯỞNG:
Chia để trị là một kỹ thuật thiết kế thuật toán bao gồm việc chia một bài toán cần giải ra thành những bài toán con nhỏ hơn có cùng một loại vấn đề, giải từng bài toán con đó một cách lần lượt và độc lập, sau đó kết hợp các lời giải con thu được nhờ cách đó để thu được lời giải của bài toán ban đầu.
KHÁI NIỆM:
Chia để trị là một trong những phương pháp thiết kế giải thuật cơ bản bao gồm các thao tác:

• Chia: Phân tích bài toán có N thành phần dữ liệu thành nhiều bài toán con có kích thước dữ liệu nhỏ hơn.
• Trị: Giải bài toán con bằng phương pháp đệ quy. Tuy nhiên nếu bài toán con đủ nhỏ, có thể giải quyết theo cách đơn giản.
• Tổng hợp: tổng hợp nghiệm của các bài toán con thành nghiệm của bài toán ban đầu.

GIẢI THUẬT CHIA ĐỀ TRỊ:

VÍ DU MINH HỌA:
Tìm phần tử lớn nhất đầu tiên bằng thuật toán chia đề trị:
Ý tưởng của thuật toán chia để trị gồm 3 thành phần:

• Chia: chia dãy n phần tử cần tìm phần tử lớn nhất thành 2 dãy con, mỗi dãy có n/2 phần tử. Tiếp tục chia dãy con đến khi dãy còn một phần tử.
• Trị: tìm phần tử lớn nhất của các dãy con bằng phương pháp đệ quy.
• Tổng hợp: so sánh các phần tử lớn nhất của các dãy con để tìm phần tử lớn nhất của dãy.

Mô Phỏng thuật toán:
- Đầu tiên nhập 1 mảng vào:

- Trả về kết quả giá trị lớn nhất

- Sơ đồ thuật toán tìm giá trị lớn nhất đầu tiên

- Sơ đồ khối của thuật toán TimMax(A,low,high)