ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN HỌC

ĐỒ ÁN MÔN HỌC
ĐỀ TÀI
SẮP XẾP LỊCH THI ĐẤU TENNIS BẰNG THUẬT
TOÁN CHIA ĐỂ TRỊ
Sinh viên thực hiện: Khổng Thanh Dũng
Lớp: 11CNTT2
Giảng viên hướng dẫn: TH.S.Lê Thị Bích Hồng
Đà Nẵng, 2013
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
2
MỤC LỤC
MỞ ĐẦU 3
CHƯƠNG 1 CƠ SỞ LÝ THUYẾT 4
1.1.2. Chiến thuật 4
1.1.3. Phương pháp 4
1.1.4. Mô tả giải thuật chung 5
1.3.2.các tính chất của O, Ω, ⱺ 8
1.3.3. Phân tích tiệm cận 8
1.3.4. Các cách đánh giá thuật toán 9
1.3.5. Các kiểu phân tích 9
1.3.6. Độ phức tạp thời gian 9
2.2. GIẢI QUYẾT VẤN ĐỀ 10
2.3. GIẢI THUẬT 10
2.4. THIẾT KẾ DỮ LIỆU CHO BÀI TOÁN 12
2.5. LẬP LỊCH THI ĐẤU 12
2.6. ĐỘ PHỨC TẠP CỦA GIẢI THUẬT 13
2.7. NHẬN XÉT 13

- Mở đầu.
- Chương I: Cơ sở lý thuyết.
- Chương II: Bài toán sắp xếp lịch thi đấu thể thao.
- Kết luận.
- Tài liệu tham khảo
- Phụ lục.
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
4
CHƯƠNG 1 CƠ SỞ LÝ THUYẾT
1.1. KỸ THUẬT CHIA ĐỂ TRỊ
1.1.1. Khái niệm
- Chia để trị ( Divide and conquer) là phương pháp thiết kế được sử dụng rộng rãi
và quan trọng. Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ
thuật chia để trị. Kỹ thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn,
thực hiện lời giải cho từng bài toán nhỏ này và từ đó xây dựng thuật toán cho bài
toán lớn tổng hợp. Ví dụ cho thuật toán này là Sắp xếp trộn hoặc Tìm kiếm nhị
phân. Chia để trị là chìa khóa để thiết kế nhiều giải thuật quan trọng, là cơ sở của
quy hoạch động.
1.1.2. Chiến thuật
Chiến thuật của thuật toán chia để trị gồm các bước sau:
a. Chia bài toán thành nhiều bài toán nhỏ hơn.
b. Trị (giải) mỗi bài toán nhỏ, trừ khi bài toán đủ nhỏ để có lời giải. Dùng đệ
quy để thực hiện điều này.
c. Nếu cần thì tổ hợp các lời giải của các bài toán nhỏ để nhận được lời giải
của bài toán gốc.
Nói là “nếu cần” ở bước 3 vì như bài toán tìm kiếm nhị phân bằng đệ quy chẳng
hạn thì bài toán lớn được thu gọn thành đúng một bài toán nhỏ, vì vậy không cần
phải tổ hợp các lời giải.
1.1.3. Phương pháp

For (i=1 ; I <=m ; i++)
D&C(Ri) ;
Tổng hợp kết quả ;
}
}
1.2. CÁC BÀI TOÁN ÁP DỤNG KỸ THUẬT CHIA ĐỂ TRỊ
1.2.1. Tìm max, min trong dãy
Chia mảng A gồm hai nửa, tìm giá trị lớn nhất của mỗi nửa bằng đệ quy.
Trả về giá trị lớn nhất trong hai giá trị lớn nhất của mỗi nửa.
max(i,j)
{
if (j-i≤1) return A[i]>A[j]?A[i]:A[j];
else {
m1=max(i,(i+j)/2)
m2=max((i+j)/2+1,j);
return m1>m2? m1:m2;
}
}
1.2.2. Sắp xếp nhanh
Thuật toán QuickSort sắp xếp hai danh sách con bằng đệ quy để kết quả là
toàn bộ danh sách được sắp xếp.
qsort (low, high)
{
i=low; j=high;
x=A[(low+high)/2];
do{
while (A[i]<x) i++;
while (A[j]>x) j ;
if (i<=j){
swap(A[i],A[j]);

mergesort(m, V);
merge (h, m, U, V, A); }
}
1.2.4. Tìm kiếm nhị phân
Cho mảng n phần tử đã được sắp xếp tăng dần và một phần tử x. Tìm x có
trong mảng hay không? Nếu có x trong mảng thì cho biết vị trí đầu tiên của x trong
mảng, ngược lại cho kết quả trả về bằng 0.
int RecBinarySearch(int a[max],int First,int Last,int x)
{
if(First>Last)
return (0);
int Mid=(First+Last)/2;
if(x==a[Mid])
return (Mid);
if(x<a[Mid])
return RecBinarySearch(a,First,Mid-1,x);
else
return RecBinarySearch(a,Mid+1,Last,x);
}
//=======================================================
int BinarySearch(int a[max],int n,int x)
{
return(RecBinarySearch(a,0,n-1,x));
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
7
}
1.2.5. Bài toán tháp Hà Nội (Brahma)
Có n đĩa kích thước nhỏ dần xếp chồng lên nhau trên một cọc (được gọi là
cọc nguồn, cọc A), đĩa lớn ở dưới, đĩa nhỏ ở trên. Ngoài cọc nguồn còn có 2 cọc

nc[os] ;
//chuyen dia nho nhat
cn++;
s=cmin; t=(s+d)%3;
printf("%10ld - chuyen dia 1: %d >%d\n",cn,s,t);
nc[t]++; c[t][nc[t]]=1; cmin=t;
nc[s] ;
// tim os & ot hop le
os=0; while (os==t) os++;
ot=3-os-t;
if (c[os][nc[os]]>c[ot][nc[ot]]){
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
8
temp=os; os=ot; ot=temp;
}
}
printf("cn = %ld", cn);
getch();
}
1.3. ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
1.3.1. Định nghĩa
Một chương trình máy tính thường được cài đặt dựa trên một thuật toán để
giải bài toán hay vấn đề đặt ra. Một đòi hỏi đương nhiên là thuật toán phải đúng.
Thuật ngữ phân tích thuật toán đề cập đến một quá trình tìm ra một đánh giá về
thời gian và không gian cần thiết để thực hiện thuật toán. Ðộ phức tạp của thuật
toán được thể hiện qua khối lượng thời gian và không gian để thực hiện thuật toán.
Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, … của máy
tính để thuật toán có thể làm việc được. Việc xem xét độ phức tạp về không gian
của thuật toán phụ thuộc phần lớn vào cấu trúc dữ liệu được sử dụng trong cài đặt

1.3.4. Các cách đánh giá thuật toán
Phân tích các thuật toán nhằm cải tiến chúng nếu có thể, và chọn ra một số thuật
toán tốt cho một bài toán. Chúng ta sẽ dùng các tiêu chuẩn sau:
1. Tính đúng đắn.
2. Tống số việc thực hiện.
3. Tổng không gian sử dụng.
4. Đơn giản, rõ ràng.
5. Tối ưu.
1.3.5. Các kiểu phân tích
Trường hợp xấu nhất: Lấy thời gian ứng với khả năng xấu nhất xảy ra. T(n) là thời
gian lớn nhất với tất cả các dữ liệu nhập kích thước n.
Trường hợp trung bình: Thời gian chạy với phân bố nào đó trên dữ liệu nhập,
thường là phân bố đồng bộ. T(n) là thời gian trung bình của tất cả các dữ liệu nhập
với kích thước n.
Xác xuất: thời gian chạy với dữ liệu nhập ngẫu nhiên. Lập biểu thức thời gian chạy
và tính xác xuất nhận được nó.
1.3.6. Độ phức tạp thời gian
Việc tính độ phức tạp dựa vào các quy tắc sau:
Phép gán O(1)
Vào/ra hàm O(1)
Lệnh if thời gian kiểm tra cộng O( max{ hai nhánh } )
Lệnh lặp Tổng tất cả thời gian của tất cả các bước lặp
Tổng hợp chúng bằng cách dùng các quy tắc tính tổng và nhân. Trừ các thuật toán
đệ quy.
Quy tắc tổng: Nếu g
1
(n)=O(f
1
(n)) và g
2

1
(n).g
2
(n)=O(f
1
(n).f
2
(n))
* Một số lớp độ phức tạp
- Độ phức tạp hằng số: O(1).
- Độ phức tạp logarit: O(log n).
- Độ phức tạp tuyến tính: O(n).
- Độ phức tạp n log n: O(n log n).
- Độ phức tạp đa thức: O(n
b
).
- Độ phức tạp mũ: O(b
n
), trong đó b > 1.
- Độ phức tạp giai thừa: O(n!) = O(n
n
).
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
10
CHƯƠNG 2 BÀI TOÁN SẮP XẾP LỊCH THI ĐẤU THỂ
THAO TENNIS
Kỹ thuật chia để trị không những chỉ có ứng dụng trong thiết kế giải thuật
mà còn trong nhiều lĩnh vực khác của cuộc sống. Chúng ta sẽ xét ví dụ sau để thấy
rõ hơn về sức mạnh của kỹ thuật “chia để trị”.

Ô(1,2) =1;
* Lịch thi đấu cho 4 VĐV
Xuất phát từ lịch thi đấu cho hai VĐV ta có thể xây dựng lịch thi đấu cho 4 VĐV
là một bảng gồm 4 dòng 3 cột như sau:
- Lịch thi đấu cho hai VĐV 3 và 4 trong ngày thứ nhất
Ô(3,1)= 4 = Ô(1,1) +2; Ô(4,1) = 3 = Ô(1,2) +2;
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
11
- Bây giờ để hoàn thành lịch thi đấu chúng ta lấy góc trên bên trái của bảng lắp vào
cho góc dưới bên phải và lấy góc dưới bên trái lắp cho góc trên bên phải
* Lập lịch thi đấu cho 8 VĐV :
Lịch thi đấu cho 8 VĐV gồm một bảng gồm 8 dòng và 7 cột
+ Góc trên bên trái chính là lịch thi đấu trong 3 ngày đầu của 4 VĐV từ 1 đến 4
+ Các ô ở góc dưới bên trái chính bằng các ô tương ứng ở góc bên trái cộng 4,
đây chính là lịch thi đấu cho 4 VĐV 5, 6, 7, 8 trong 3 ngày đầu.
+ Chúng ta hoàn thành việc sắp lịch bằng cách lắp đầy góc dưới bên phải bởi
góc dưới bên trái và góc trên phải bởi góc dưới bên trái
Quá trình lập lịch thi đấu thể thao được mô tả như sau:
Bảng 2.1
Ý tưởng: Chúng ta sẽ áp dụng kỹ thuật chia để trị vào bài toán: Chúng ta hãy lập lịch
thi đấu cho nửa (n/2) số vận động viên đầu tiên. Bằng việc sử dụng lời gọi đệ qui chúng ta đưa
bài toán về trường hợp chỉ có 2 VĐV. Chúng ta minh họa bằng trường hợp n=8. Lịch thi đấu
cho 4 người đầu tiên của danh sách chiếm nửa trái trên của ma trận (4 hàng, 3 cột). Phần nửa trái
dưới (4 hàng, 3 cột) của ma trận là lịch thi đấu của 4 VĐV còn lại (từ 5 đến 8). Phần này thu
được từ nửa trái trên bằng cách cộng 4 vào mỗi phần tử tương ứng của ma trận. Để điền nốt các
phần còn lại của ma trận chúng ta chỉ cần xác định lịch thi đấu giữa cácVĐV với số thấp (≤n/2)
với các VĐV với số cao (≥n/2). Để làm việc này chúng ta xếp các VĐV từ 1 đến n/2 đấu lần
lượt với các VĐV số cao vào ngày 4. Các ngày còn lại thu được từ ngày 4 bằng cách hoán vị
vòng quanh các VĐV với số thứ tự cao.

Theo cách giải quyết vấn đề và giải thuật nêu trên thì ta nhận thấy rằng kiểu dữ liệu
phù hợp với bài toán nhất là kiểu mảng hai chiều.
+ Với số liệu nhập vào n đối thủ (n=2
k
), các phần tử đều có cùng kiểu dữ
liệu thì với kiểu dự liệu mảng hai chiều sẽ in ra một ma trận thỏa mãn n dòng và
(n-1) cột đúng như yêu cầu của xuất ra của bài toán
+ Với giải thuật của bài toán thì kiểu mảng hoàn toàn phù hợp VD: cách
tính Ô(3,1),Ô(4,1) của bài toán sẽ tương ứng với chỉ số hàng và cột của ma trận mà
ta thành lập, cách gọi đệ quy
+ Cấu trúc mảng hai chiều sẽ dễ dàng cài đặt trên ngôn ngữ lập trình C++ và
còn rất dễ hiểu.
2.5. LẬP LỊCH THI ĐẤU
//Mang A duoc khai bao truoc
void XepLichThiDau(int y){
int i,j;
if(y==2){
A[1][1]=2;
A[2][1]=1;
}
else{
int temp=y/2;
XepLichThiDau(temp);
for(i=1;i<=temp;i++)
for(j=1;j<=temp-1;j++){
A[i+temp][j]=A[i][j]+temp;
}
for(i=1;i<=temp;i++)
for(j=temp;j<=y-1;j++){
int x=i+j;

}
Vd: Ô(4,1)=Ô(2+2,1)+2=1+2=3
2.6. ĐỘ PHỨC TẠP CỦA GIẢI THUẬT
Gọi T(n) là thời gian thực hiện n VĐV thì T(n/2) thời gian thực hiện xếp lịch thi
đấu cho n/2 VĐV.
Nếu n bằng 2 tức là có hai VĐV, tức là trường hợp cơ sở chương trình chỉ thực
hiện một lệnh duy nhất đưa kết quả ra màn hình.
Ngoài ra còn tốn thời gian cho trường chương trình tốn chia n thành hai nữa bằng
nhau và thời gian thực hiện chương trình là log n
Phương trình đệ quy tính độ phức tạp của thuật toán được tìm thấy là:
1 nếu n = 2 ;
T(n) = T(n/2) + log n nếu n > 2;

Áp dụng phương pháp truy hồi ta có:
T(n) = [T(n/4) + log
2
(n/2)] + log
2
n
= [T(n/8) + log
2
(n/4)] +log
2
(n/2) + log
2
n
Ta có nghiệm thuần n
log
2
2

14
KẾT LUẬN
1. Kết quả đạt được
Sau thời gian nghiên cứu và tìm hiểu đề tài, cùng với sự hướng dẫn tận tình của
thầy cô và sự giúp đỡ của bạn bè. Hôm nay, đề tài đã được hoàn thành và đạt được
một số kết quả như sau:
 Em đã được đi sâu vào tìm hiểu về kỹ thuật “chia để trị” để áp dụng trong
thực tế thật dể dàng.
 Hiểu và cài đặt thuật toán đã được yêu cầu bằng ngôn ngữ C++ biết cách sử
dụng các thao tác và các hàm trong C++.
 Chương trình chạy ổn định, giao diện thân thiện với người dùng và dễ sử
dụng
 Chương trình được thiết kế dưới dạng các chương trình con độc lập nhau
nên dễ dàng kiểm tra và sửa chữa khi yêu cầu chỉnh sửa.
2. Hạn chế
Mặc dù có cố gắng để hoàn thành đề tài, nhưng đây là lần đầu tiên tìm hiểu sâu
về thuật toán nên vẫn còn thiếu nhiều kinh nghiệm trong kỹ thuật lập trình cũng
như trong cách tổ chức dữ liệu.
 Có thể giao diện còn chưa đáp đầy đủ các chức năng người sử dụng yêu cầu.
 Chương trình chỉ áp dụng với số lượng VĐV là n = 2
k
.
3. Hướng phát triển
 Thiết kế giao diện thân thiện với người sử dụng
 Cải tiến chương trình đầy đủ và hoàn thiện hơn
 Phát triển chương trình sang các ngôn ngữ khác như Turbo, Visual Basic,
Java,…để được hổ trợ nhiều hơn.
TÀI LIỆU THAM KHẢO
[1]. Nguyễn Văn Linh (2003), “Giải thuật “, Đại học Cần Thơ.
[2]. Đỗ Xuân Lôi (2009), “ Cấu trúc dữ liệu và giải thuật”, NXB Đại học Quốc

if(y==(int)pow((int)2,(int)i))
t=1;
return t;
}
//Ham xep lich thi dau
void XepLichThiDau(int y){
int i,j;
if(y==2){
A[1][1]=2;
A[2][1]=1;
}
else{
int temp=y/2;
XepLichThiDau(temp);
for(i=1;i<=temp;i++)
for(j=1;j<=temp-1;j++){
A[i+temp][j]=A[i][j]+temp;
}
for(i=1;i<=temp;i++)
for(j=temp;j<=y-1;j++){
int x=i+j;
if(x>y) x=x-temp;
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
16
A[i][j]=x;
A[x][j]=i;
}
}
}

if(f==NULL)
// f=fopen("lichthidau.txt","r");
f=fopen("lichthidau.txt","w");
int i, j, k;
fprintf(f," ");
for(k=1;k<n;k++) fprintf(f,"%5d",k);
fprintf(f,"\n ");
Đồ án môn học 11CNTT2 Khổng Thanh Dũng
Sắp xếp lịch thi đấu Tennis bằng thuật toán chia để trị
17
for(k=1;k<n;k++) fprintf(f," ");
for(i=1;i<=n;i++){
fprintf(f,"\n");
fprintf(f,"%d|",i);
for(j=1;j<n;j++)
fprintf(f,"%5d",A[i][j]);
}
fclose(f);

}
main(){
XepLichMenu();
ghifile();
getch();
}
Đồ án môn học 11CNTT2 Khổng Thanh Dũng