Thuật toán giúp tự động sắp xếp thời khóa biểu THPT cho học sinh và giáo viên. Chất lượng của thời khóa biểu được đánh giá dựa trên nhiều ràng buộc cứng và mềm dựa trên dữ liệu thực tế. Đây là thuật toán được cài đặt hỗ trợ cho bài báo khoa học của học viên cao học Nguyễn Hồ Thiên Đăng và TS. Phan Tấn Quốc.

Cấu trúc tập tin

Chương trình chính: main.cpp

Input Files:

(Dữ liệu mẫu - Trường THPT Ngô Quyền, Q.7, TP.HCM)

PC_HK1.txt PC_HK2.txt(Danh sách phân công của học kì I và II).

cấu trúc file:      
vd: PC001 10A Anh GV1024 3 2

Output Files:

• TKB của lớp: TKB_lop.txt
• TKB của gv: TKB_gv.txt
• Vi phạm của lớp: VP_lop.txt
• Vi phạm của gv: VP_gv.txt
• Vi phạm chi tiết: VP_chitiet.txt
• Vi phạm tổng: VP_tong.txt
• Số liệu về điểm vi pham (Cải Thiện 2): `main.cpp`0

Tiêu chí đánh giá chất lượng

Chất lượng của một thời khóa biểu thể hiện qua thời khóa biểu của các lớp học và thời khóa biểu của mỗi giáo viên. Việc đánh giá chất lượng một thời khóa biểu là công việc khó khăn và thông thường giáo viên sẽ đánh giá dựa vào thông tin thời khóa biểu có vi phạm các ràng buộc của bài toán

• 1. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM Tải tài liệu tại kết bạn zalo : 0973.287.149 Đà Nẵng, 2013 ĐẠ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
• 2. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 2 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T MỤC LỤC MỞ ĐẦU .......................................................................................................................3 CHƯƠNG 1 CƠ SỞ LÝ THUYẾT...........................................................................4 1.1. KỸ THUẬT CHIA ĐỂ TRỊ............................................................................4 1.1.1. Khái niệm.................................................................................................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.2. CÁC BÀI TOÁN ÁP DỤNG KỸ THUẬT CHIA ĐỂ TRỊ. ...........................5 1.2.1. Tìm max, min trong dãy. .............................................................................5 1.2.2. Sắp xếp nhanh..............................................................................................5 1.2.3. Sắp xếp trộn.................................................................................................6 1.2.4. Tìm kiếm nhị phân.......................................................................................6 1.2.5. Bài toán tháp Hà Nội (Brahma)...................................................................7 1.3. ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN. .................................8 1.3.1. Định nghĩa................................................................................................8 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 CHƯƠNG 2 BÀI TOÁN SẮP XẾP LỊCH THI ĐẤU THỂ THAO TENNIS ........10 2.1. ĐẶT VẤN ĐỀ. .....................................................................................................10 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 KẾT LUẬN..............................................................................................................14 TÀI LIỆU THAM KHẢO ...........................................................................................14 PHỤ LỤC.....................................................................................................................15 Chương trình sắp xếp lịch thi đấu thể thao Tennis. .................................................15
• 3. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 3 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T MỞ ĐẦU 1. Lý do, mục đích chọn đề tài Kỹ thuật “chia để trị” là vấn đề quan trọng trong phân tích và thiết kế giải thuật, nó đã được nghiên cứu từ lâu và có nhiều ứng dụng trong nhiều ngành khoa học nói Chung và khoa học máy tính nói riêng. Nhiều giải thuật đã được phát triển để giải được rất nhiều bài toán, có thể nói rằng “chia để trị” là kỹ thuật quan trọng nhất và được áp dụng rộng rãi nhất để thiết kế các giải thuật có hiệu quả hiện nay.. Trong đó bài toán sắp xếp lịch thi đấu là một chủ đề khá thú vị, là chủ đề mang tính chất thực tế trong cuộc sống và được ứng dụng rất rộng rãi. 2. Mục tiêu cần đạt được của đề tài Đề tài này được thực hiện nhằm đạt được mục tiêu là hiểu rõ, sâu sắc hơn về thuật toán chia để trị, ứng dụng của thuật toán vào một số bài toán. Tìm hiểu ứng dụng quan trọng của nó trong chia lịch thi đấu thể thao trong Tennis. 3. Cơ sở lý thuyết - Toán học - Mảng - Danh sách liên kết. 4. Đối tượng và phạm vi nghiên cứu - Ngôn ngữ lập trình C++. - Thuật toán chia để trị và bài toán chia lịch thi đấu Tennis. 5. Phương pháp nghiên cứu - Tìm hiểu thông tin trên mạng internet, sách, báo, tạp chí… - Thông qua sự hướng dẫn của thầy cô giáo và nghiên cứu những tài liệu tham khảo liên quan. 6. Cấu trúc đề tài - 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.
• 4. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 4 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T 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 a) Quá trình Kỹ thuật chia để trị gồm 2 quá trình: - Phân tích bài toán đã cho thành bài toán cơ sở. - Tổng hợp kết quả từ bài toán cơ sở để có lời giải của bài toán ban đầu. Tuy nhiên đối với một số bài toán, thì quá trình phân tích đã chứa đựng việc tổng hợp kết quả do đó nếu chúng ta đã giải xong các bài toán cơ sở thì bài toán ban đầu cũng đã được giải quyết. Ngược lại, có những bài toán mà quá trình phân tích thì đơn giản nhưng việc tổng hợp kết quả lại rất phức tạp. b) Ý tưởng Ta có thể tóm tắt ý tưởng chính của phương pháp này như sau: - Chia bài toán đã cho thành một số bài toán con có kích thước nhỏ hơn. - Giải các bài toán con (kích thước giảm đến trường hợp tầm thường hay còn gọi là bài toán cơ sở). - Tổng hợp kết quả để được bài toán ban đầu. Thông thường ta nhận được các bài toán con trong quá trình phân chia có cùng dạng với bài toán ban đầu, chỉ có cỡ là nhỏ hơn. Trong trường hợp như thế thuật toán tìm được có thể biểu diễn một cách tự nhiên bởi thủ tục đệ quy. Vì vậy để hiểu rõ hơn về kỹ thuật chia để trị ta cũng sẽ có một số tìm hiểu về đệ quy ở phần sau.
• 5. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 5 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T 1.1.4. Mô tả giải thuật chung Nếu gọi D & C(R) với R là miền dữ liệu là hàm thể hiện cách giải bài toán theo phương pháp chia để trị ta có thể viết: Void D&C (R){ If (R đủ nhỏ) giải bài toán; Else{ Chia r thành R1,…..Rn ; 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) j--; if (i<=j){ swap(A[i],A[j]); i++; j--; } } while (i<=j); if (low
• 6. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 6 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T } 1.2.3. Sắp xếp trộn Sắp xếp trộn bằng cách trộn hai mảng con đã sắp xếp thành mảng kết quả. Ví dụ, để sắp xếp một mảng gồm 16 phần tử, có thể chia mảng này thành hai mảng con, mỗi mảng gồm 8 phần tử, sắp xếp hai mảng con rồi trộn chúng lại thì có được mảng kết quả. Cùng cách này, mỗi mảng con kích thước 8 được chia thành hai mảng con kích thước 4, sắp xếp chúng và trộn lại. Cuối cùng, kích thước các mảng con là 1 thì đã sắp xếp tầm thường. Thủ tục này gọi là “sắp xếp trộn”. Cho mảng kích thước n, để đơn giản giả sử n là số mũ của 2, sắp xếp trộn bao gồm các bước sau: 1. Chia mảng thành hai mảng con kích thước n/2. 2. Trị (giải) mỗi mảng con bằng cách sắp xếp chúng. Trừ khi kích thước mảng con đủ nhỏ, dùng đệ quy để thực hiện điều này. 3. Tổ hợp các lời giải của các mảng con bằng cách trộn chúng vào một mảng. mergesort (n, A[ ]) { if (n>1) { h=[n/2], m = n - h; chép A[1..h] vào U[1..h]; chép A[h+1..n] vào V[1..m]; mergesort(h, U); 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
• 7. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 7 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T } 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 trống khác, được gọi là cọc đích và cọc trung gian (cọc B và cọc C). Hãy chuyển các đĩa này từ cọc nguồn sang cọc đích (một trong 2 cột B hoặc C) tuân theo 2 quy tắc sau: Quy tắc 1: Mỗi lần chỉ được chuyển mỗi đĩa từ cọc này sang cọc khác và được dùng cọc thứ 3 làm cọc trung chuyển. Quy tắc 2: Không được xếp đĩa lớn trên đĩa nhỏ. void main() { Int n,i,j,s,t,d,os,ot,nc[3]={0},c[3][MAX]={0},cmin=0,temp;long cn=0; printf("n= "); scanf("%d",&n); nc[0]=n; c[0][nc[0]]=1; for (j=0; j<=n; j++) c[0][j]=n+1-j; c[0][n]=1; c[1][0]=n+1; c[2][0]=n+1; if (n%2==0) d=1; else d=2; //chuyen dia nho nhat cn++; s=cmin; t=(s+d)%3; printf("%10ld - chuyen dia 1: %d >%dn",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]]){ temp=os; os=ot; ot=temp; } while (nc[2]%dn",cn,c[os][nc[os]],os,ot); nc[ot]; c[ot][nc[ot]]=c[os][nc[os]]; nc[os]--; //chuyen dia nho nhat cn; s=cmin; t=(s+d)%3; printf("%10ld - chuyen dia 1: %d >%dn",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]]){
• 8. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 8 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T 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 thuật toán. 1.3.2. các tính chất của O, Ω, ⱺ Với tất cả các tính chất luôn giả sử f, g, h: N R* 1. Tính bắt cầu: Nếu f € O(g) và g € O(h) thì f € O(h). 2. f € O(g) nếu và chỉ nếu g € Ω(f). 3. Nếu f € ⱺ(g) thì g € ⱺ(f) 4. ⱺ xác định một quan hệ tương đương trên các hàm; mỗi tập ⱺ(f) là một lớp tương đương, gọi là lớp phức tạp. 5. O(f+g) = O(max(f,g)). 1.3.3. Phân tích tiệm cận Các công thức để tính thời gian chạy của chương trình thường phức tạp. Khi thiết kế thuật toán, mục đích chính của việc phân tích là nhận được một giác quan về xu hướng trong thời gian chạy của thuật toán. Chúng ta muốn biểu diễn các hàm phức tạp một cách đơn giản – lấy đặc tính tốc độ tăng cơ bản. Đây là mục đích của tiệm cân. Phân tích tiệm cận dựa vào hai giả thiết đơn giản, thỏa mãn hầu hết các trường hợp, nhưng không phải tất cả. Nhưng là quan trọng để hiểu các giả thiết này và các giới hạn của phân tích tiệm cận.  Kích thước dữ liệu nhập lớn. Chúng ta quan tâm hầu hết trong cách tăng thời gian chạy với giá trị n lớn.  Bỏ qua nhân tử bằng. Thời gian chạy của chương trình phụ thuộc vào các nhân tử hằng khác nhau trong cài đặt (mã lệnh, trình biên dịch, phần cứng…). Do đó sẽ bỏ qua các nhân tử hằng.
• 9. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 9 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T Kích thước nhập thường ký hiệu là n. Gía trị n có thể là kích thước mảng như thuật toán sắp xếp mảng, cũng có thể là một số như thuật toán tính n! , và cũng có thể nhiều kích thước nhập như thuật toán trên đồ thị (số đỉnh, số cạnh). 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 g1(n)=O(f1(n)) và g2(n)=O(f2(n)) thì: a) g1(n)+g2(n)=O(f1(n)+f2(n)) b) g1(n)+g2(n)=O(max{f1(n),f2(n)}) Quy tắc nhân: Nếu g1(n)=O(f1(n)) và g2(n)=O(f2(n)) thì g1(n).g2(n)=O(f1(n).f2(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(nb ). - Độ phức tạp mũ: O(bn ), trong đó b > 1. - Độ phức tạp giai thừa: O(n!) = O(nn ).
• 10. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 10 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T 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ị”. 2.1. ĐẶT VẤN ĐỀ Bài toán: Sắp xếp lịch thi đấu vòng tròn một lượt cho n đối thủ. Mỗi đối thủ phải thi đấu với n-1 đối thủ khác và mỗi đối thủ chỉ đấu nhiều nhất một trận mỗi ngày. Yêu cầu là xếp một lịch thi đấu sao cho số ngày thi đấu là ít nhất. 2.2. GIẢI QUYẾT VẤN ĐỀ Nếu n chẵn, ta có thể xếp n/2 cặp đấu với nhau mỗi ngày và số ngày thi đấu ít nhất sẽ là n-1 ngày. Ngược lại nếu n lẻ, thì n-1 chẵn, ta có thể xếp (n-1)/2 trận mỗi ngày và vì vậy chúng ta cần n ngày. Giả sử n = 2k thì n chẵn do đó ta cần ít nhất n - 1 ngày. Giả sử cần lập một lịch thi đấu Tennis cho n =2k vậnđộng viên (VĐV). Mỗi VĐV phải thi đấu với lần lượt n-1 VĐV khác, mỗi ngày thi đấu 1 trận. Như vậy n-1 là số ngày thi đấu tối thiểu phải có. Chúng ta cần lập lịch thi đấu bằng cách thiết lập ma trận có n hàng, n-1 cột. Giá trị số tạivị trí (i,j) (hàng i, cột j) chỉ ra VĐV cần thi đấu với VĐV i trong ngày thứj. 2.3. GIẢI THUẬT Lập lịch thi đấu cho hai VĐV thì dễ sắp xếp. Khó khăn chính là ở chỗ từ các lịch thi đấu cho hai VĐV, ta tổng hợp lại để được lịch thi đấu của 4 VĐV, đây chính là điều mà chúng ta đã nói ở chương I “có những bài toán mà quá trình phân tích thì đơn giản nhưng việc tổng hợp kết quả lại rất phức tạp” Chiến lược chia để trị như sau: thay vì xếp cho n VĐV, ta sẽ xếp cho n/2 VĐV sau đó dựa trên kết quả lịch thi đấu của n/2 VĐV ta xếp cho n VĐV. Quá trình phân chia sẽ dừng lại khi ta phải xếp lịch cho 2 VĐV. Việc xếp lịch cho 2 VĐV rất dễ dàng: ta cho 2 VĐV này thi đấu 1 trận trong 1 ngày. Bước khó khăn nhất chính là bước xây dựng lịch cho 4, 8, 16, … VĐV từ lịch thi đấu của 2 VĐV. * Lịch thi đấu của hai VĐV 1 và 2 trong ngày thứ nhất Ô(1,1) =2; Ô(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;
• 11. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 11 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T - 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 tahãylậplị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ủadanh sáchchiếmnửatrái trên của ma trận(4 hàng, 3 cột). Phầnnửatrá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òngquanhcácVĐVvớisốthứtựcao. Chú ý: Ở đây chúng ta chỉ xét trường hợp số đối thủ là chẵn ( n=2k ). Ở trường hợp n lẻ thì ta có (n-1) là số chẵn và ta có (n-1)/2 cặp thi đấu trong một ngày. Và do đó ta cần n ngày. 2 1 2 3 4 1 4 3 4 1 2 3 2 1 2 3 4 5 6 7 8 1 4 3 6 7 8 5 4 1 2 7 8 5 6 3 2 1 8 5 6 7 6 7 8 1 4 3 2 5 8 7 2 1 4 3 8 5 6 3 2 1 4 7 6 5 4 3 2 1 1 1 1 1 1 1 2 3 4 5 6 7 8 2 3 4 5 6 7 2 3 2 3 4 2 2 VĐV 4 VĐV 8 VĐV
• 12. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 12 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T 2.4. THIẾT KẾ DỮ LIỆU CHO BÀI TOÁN 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=2k ), 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; if(x>y) x=x-temp; A[i][j]=x; A[x][j]=i; } } } Phân tích: ` -Trường hợp có hai đội tham gia Thì ta có cách xếp Ô(1,1)=2;.Ô(2,1)=1 -Khi n>2 và n=2k thì ta chia đôi n (temp:=n/2) và gọi đệ quy trường hợp temp=n/2. -Ta dùng hai vòng for lồng nhau để lấy đối thủ i thi đấu với đối thủ j trong k (n=2k ) ngày đầu i chạy từ 1->temp j chạy từ 1->temp-1 table[i+temp,j]=table[i,j]+temp;
• 13. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 13 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T vd: Ô(3,1)=Ô(1+2,1)+2 =2+2=4; Trường hợp để lấy lịch cho bảng ở góc bên phải và trái i chạy từ 1 ->temp j chạy từ temp->n-1 { x:=i+j; if x>n then x:= x-temp; table[i,j]=x; table[x,j]=i; } 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) + log2(n/2)] + log2n = [T(n/8) + log2(n/4)] +log2(n/2) + log2n Ta có nghiệm thuần nlog 2 2 = n Do d(n) = log2n không phải hàm nhân nên ta tính nghiệm bằng xét trực tiếp nghiệm riêng k-1 k-1 ∑ log2nk-j = ∑ (k-j) j=0 j=0 Vậy T(n) = O(log2n). 2.7. NHẬN XÉT Ưu điểm: Quá trình chia để trị để xây dựng lịch thi đấu sẽ dẫn đến bài toán cơ sở là sắp xếp lịch thi đấu cho hai VĐV. Hai VĐV này sẽ thi đấu một trận trong một ngày nên dễ dàng sắp xếp lịch thi đấu. Bài toán có tính ứng dụng thực tế cao. Nhược điểm: Thuật toán chỉ áp dụng để giải được các bài toán với số lượng VĐV là n=2k .
• 14. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 14 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T 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 = 2k . 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 gia Hà Nội. [3]. Phan Đoàn Ngọc Phương (2007), “Cấu trúc dữ liệu và giải thuật”, lưu hành nội bộ. [4]. Lê Minh Hoàng (1999-2005), “Giải thuật và lập trình”, Đại học Sư phạm Hà Nội. [5]. Nguyễn Hồng Chương “Cấu trúc dữ liệu ứng dụng và cài đặt C “ Nhà xuất bản thành phố Hồ Chí Minh. [6]. Đinh Mạnh Tường “ Cấu trúc dữ liệu và thuật toán” Nhà xuất bản khoa học và kỹ thuật. [7]. Phan Thanh Tao “Giáo trình phân tích và thiết kế giải thuật” Đại Học Sư Phạm Đà Nẵng.
• 15. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 15 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T PHỤ LỤC Chương trình sắp xếp lịch thi đấu thể thao Tennis.

  include

  include

  include

  include

  include FILE *f; int n; int a[100], b[100]; int A[100][100]; //XEP LICH THI DAU CHO n=2^k DAU THU //Ham kiem tra so dau thu co bang 2^k hay khong int KiemTra(int y){ int t=-1, i; for(i=1;iy) x=x-temp;

• 16. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 16 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T A[i][j]=x; A[x][j]=i; } } } //=================================================== ====== void XepLichMenu(){ printf("n========================================= =====================n"); printf("nNhap so nguoi (doi) thi dau (n=2^k) : "); scanf("%d",&n); while(KiemTra(n)!=1){ int temp; printf("nVui long nhap n=2^k : "); scanf("%d",&temp); n=temp; } XepLichThiDau(n); int i,j,k ; printf(" "); for(k=1;k-");
• 17. giá sinh viên – ZALO:0973.287.149-TEAMLUANVAN.COM 17 Tải tài liệu tại kết bạn zalo : 0973.287.149Đồ án môn học 11CNTT2 Khổng T for(i=1;i<=n;i++){ fprintf(f,"n"); fprintf(f,"%d|",i); for(j=1;j