MỤC LỤC
MỤC LỤC.........................................................................................................................................1
CHƯƠNG 1:......................................................................................................................................2
THUẬT TOÁN CHIA ĐỂ TRỊ.........................................................................................................2
(Divide to Conquer)...........................................................................................................................2
1.1/ Đặt vấn đề:..............................................................................................................................2
1.1.2) Sơ đồ chung:...................................................................................................................2
1.2/ Thuật toán:..............................................................................................................................3
1.2.1) Ý tưởng:..........................................................................................................................3
1.2.2) Các bước giải:.................................................................................................................3
1.2.3. Sơ đồ thuật toán chia để trị:.............................................................................................3
CHƯƠNG 2:......................................................................................................................................4
ỨNG DỤNG CỦA THUẬT TOÁN CHIA ĐỂ TRỊ..........................................................................4
GIẢI BÀI TOÁN SẮP XẾP..............................................................................................................4
2.1/ Phát biểu bài toán:..................................................................................................................4
c. Đánh giá thuật toán:...............................................................................................................6
d. Chương trình sắp xếp dãy bằng Mergesort:..........................................................................7
e. Ví dụ bài toán sắp xếp thực tế:...............................................................................................9
2.3.2. Quicksort.........................................................................................................................9
e. Ví dụ bài toán sắp xếp thực tế:.............................................................................................15


CHƯƠNG 1:
THUẬT TOÁN CHIA ĐỂ TRỊ
(Divide to Conquer)
1.1/ Đặt vấn đề:
Trong khoa học máy tính, chia để trị là một mô hình thiết kế thuật toán quan trọng
dựa trên đệ quy với nhiều phân nhánh. Thuật toán chia để trị hoạt động bằng cách chia bài
toán thành nhiều bài toán nhỏ hơn thuộc cùng thể loại, cứ như vậy lặp lại nhiều lần, cho
đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp. 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.

nhiều lần, cho đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp.
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.
1.2.2) Các bước giải:
Giả sử chúng ta có thuật toán α để giải bài toán kích thước dữ liệu vào n với thời
gian bị chặn bởi cn2 (c: hằng số). Xét thuật giải β để giải chính bài toán đó bằng cách:
- Bước 1: Chia bài toán cần giải thành 3 bài toán con với kích thước n/2.
- Bước 2: Giải 3 bài toán bằng thuật toán α.
- Bước 3: Tổng hợp lời giải của 3 bài toán con để thu được lời giải của bài toán.
3. Đánh giá thuật toán: Tính đúng đắn của thuật toán β
Giả sử bước 3 đòi hỏi thời gian dn(d: hằng số).
Gọi:
T α(n) = thời gian của thuật toán α.
T β(n) = thời gian của thuật toán β.
Ta có:
T α(n) = cn2 (theo giả thuyết)
T β(n) = 3.T α(n/2) + dn = ¾.cn2 + dn.
Nếu:
dn < c. n2/4 hay n > 4. d/c thì thuật toán β nhanh hơn thuật toán α.
Do 4.d/c là hằng số nên với n đủ lớn ta luôn có n > 4. d/c.
Điều đó cho thấy việc sử dụng thuật toán β để giải bài toán đặt ra bằng cách chia nó
thành các bài toán con có kích thước càng ngày càng nhỏ đến khi thu được bài toán con
kích thước n0 < 4.d/c sẽ thu được hiệu quả cao.
1.2.3. Sơ đồ thuật toán chia để trị:
procedure Divide_and_Conquer(n);
{
if n ≤ n0 then Giải bài toán một cách trực tiếp;
else
{
Chia bài toán thành r bài toán con có kích thước n/k;

và sau đó trộn chúng lại (chú ý duy trì tính thứ tự). Để làm được điều này chúng ta cần
một giải thuật hiệu quả cho việc trộn hai mảng đã được sắp U và V thành một mảng mới T
mà kích thước của mảng T bằng tổng kích thước của hai mảng U và V.

4


Array

Split

Sub Array

Sub Array

Split

SubArr
ay

Split

SubArr
ay

SubArr
ay

Sort



Stored SubArray

Combine

Store Array

Hình vẽ 2: Quy trình sắp xếp bằng phương pháp chia để trị
Vấn đề này có thể thực hiện tốt hơn nếu ta thêm vào các ô nhớ có sẵn ở cuối của
mảng U và V các giá trị đứng canh (giá trị lớn hơn tất cả các giá trị trong U và V) .
b. Giải thuật:
Procedure merge(U[1..m+1],V[1..n+1],Ta[1..m+n]);
(*Trộn 2 mảng U[1..m+1] và V[1..n+1] thành mảng T[1..m+n]); U[m+1],V[n+1]
được dùng để chứa các giá trị cầm canh*)
{ i:=1;j:=1;
U[m+1]:= ∞ ; V[n+1]:= ∞ ;
For (k=1;k
nhanh hơn heapsort một ít nhưng nó cần nhiều hơn bộ nhớ cho các mảng trung gian U và
V. Ta nhớ lại heapsort có thể sắp xếp tại chỗ (in-place), và cảm giác nó chỉ sử dụng một ít
biến phụ mà thôi. Theo lý thuyết mergesort cũng có thể làm được như vậy tuy nhiên giá
thành có tăng một chút ít.
Khi giải bài toán theo thuật giải chia để trị chúng ta hết sức chú ý đến việc tạo ra các
bài toán con, nếu không nó có thể tạo ra những thảm hại mà không thể lường trước được.
6


Giải thuật sau đây minh hoạ tính chất quan trọng này khi kích thước bài toán con là hỗn
độn:
Procedure badmergesort(T[1..n]);
{
If n đủ nhỏ then Insert(T) Else
{
Int U[1..n-1, V[1..2]; U[1..n-1]:= T[1..n-1]; V[1]:= T[n];
badmergesort(U);
badergesort(V);
merge(U,V,T);
}
}
Gọi t(n) là thời gian cần để sắp n phần tử với giải thuật badmergesort trên.
Rõ ràng là: t(n)=t(n-1)+ t(1) + g(n)
trong đó (n) ∈ Ρ(n).
Sự đệ qui này tạo ra (n) ∈ Ρ(n2), như vậy việc quên cân bằng kích thước của bài toán con
đã ảnh hưởng đáng kể đến hiệu quả của việc sử dụng giải thuật chia đểtrị.
d. Chương trình sắp xếp dãy bằng Mergesort:
#include <iostream>
#include <cmath>
#include <conio.h>

// Merge the remaining elements in right array
while ( i3