Đề tài: xếp lịch thi cho học sinh phổ thông trung học

Chương 1

TỔNG QUAN
I. LỜI MỞ ĐẦU
Trong thời đại ngày nay với sự phát triển nhanh chóng của công nghệ thông tin
thì việc giải bài toán lập trình là việc khá đơn giản, nhưng để tìm ra một phương
pháp tối ưu là điều rất khó. Khi phương pháp đồ thị ra đời đã góp phần giải
quyết các bài toán lập trình được tối ưu hơn, nhẹ nhàng hơn và hiện nay nó đã
trở thành một phương pháp phổ biến trong lĩnh vực lập trình.
Khi chúng ta áp dụng công nghệ thông tin vào ngành Giáo dục thì phương pháp
đồ thị đã cho thấy hiệu quả của nó trong các phần mềm hỗ trợ giáo dục như phần mềm
xếp thời khóa biểu, quản lý điểm, xếp lịch thi,…, đặc biệt là trong lĩnh vực sắp xếp lịch
thi cho sinh viên, học sinh hiện nay.
Đề tài xếp lịch thi cho học sinh phổ thông trung học là chương trình DeMo ứng
dụng phương pháp đồ thị. Đây là chương trình Demo sát thực tế dành cho các trường
trung học phổ thông giải quyết vấn đề lịch thi trong khi thời gian thi cuối kỳ đến. Đây
cũng là lý do để chúng ta chọn đề tài trong lĩnh vực này.
Đề tài yêu cầu xếp lịch thi trong một tuần (7 ngày) gồm bảy môn thi. Nhưng
phải xếp sao cho các môn do cùng một giáo viên giảng dạy không thi vào 2 ngày liên
tiếp nhau. Biết rằng mỗi giáo viên không quá 4 môn thi.

II. MỤC TIÊU ĐỀ TÀI
Trong bài toán sắp xếp lịch thi này, chúng ta sẽ sử dụng các ngôn ngữ lập trình
đã học và dựa vào các kiến thức của môn học Toán Rời Rạc chủ yếu là phần Lý Thuyết
Đồ Thị, từ đó ứng dụng để cài đặt các thuật toán tìm chu trình Hamilton, hay măt xích
Hamilton thỏa mãng mục đích đề tài.
Thông qua đề tài này, nhằm giúp cho sinh viên ngành CNTT nói riêng và sinh
viên ham thích nghiên cứu trong lĩnh vực Công nghệ nói chung hiểu biêt thêm về kiến
thức lý thuyết đồ thị và cách thức ứng dụng chúng vào chương trình làm giảm bớt phần

khó khăn trong việc tìm ra lời giải tối ưu cho các bài toán xuất phát từ thực tế.
Trong giới hạn đề tài này, chúng ta sẽ vận dụng các lý thuyết cơ bản về đồ thị
như đồ thị vô hướng, đồ thị có hướng, đường đi và chu trinh Hamilton để ứng dụng cài
đặt các thuật toán có liên quan đến đồ thị để vẽ đồ thị và chu trinh kiểm tra bậc của các
nút từ đó xác định chu trinh và chuyển đổi thành lịch thi trong tuần. Đây cũng là nội
dung chính của đề tài.

III. HƯỚNG GIẢI QUYẾT.
 Về lý thuyết: Tìm hiểu các khái niệm về đồ thị vô hướng, đồ thị có hướng, đường
đi và chu trình Hamilton…và các kiến thức về lập trình trên ngôn ngữ sử dụng để giải
quyết yêu cầu đề tài.
 Về chương trình: Sử dụng ngôn ngữ lập trình chính là Bordlandc C++ để viết
chương trình, cài đặt các thuật toán thực hiện các yêu cầu của đề tài, nghiên cứu và
cài đặt các thủ tục hàm đồ họa để hỗ trợ giao diện người dùng sử dụng phần mềm và
vẽ biểu diễn đồ thị, chu trình trên màn hình đồ họa.
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 1


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

 Kế hoạch thực hiện:
•
•
•
•
•

Tìm hiểu lý thuyết

Xây dựng giải thuật
Viết chương trình
Thiết kế giao diện
Viết báo cáo và hoàn chỉnh chương trình

GVHD : Ths. Lâm Thị Ngọc Châu.

1 tuần
2 tuần
2 tuần
1 tuần
2 tuần

Trang 2


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

Chương 2

NỘI DUNG
I. MÔ TẢ BÀI TOÁN.
Sử dụng phương pháp đồ thị thể hiện việc bố trí lịch thi cho học sinh phổ thông
trung học với bảy môn thi trong bảy ngày.
Yêu cầu phải bố trí lịch thi sao cho hai môn thi của cùng một giáo viên không
được rơi vào hai ngày liên tiếp nhau.
Biêt rằng không có giáo viên nào có nhiều hơn bốn môn thi.

II. GIẢI QUYẾT BÀI TOÁN.
A. Phương pháp

Ta sử dụng phương pháp đồ thị vào bài toán như sau:
Ta giả sử mỗi môn của bài toán là một nút trên đồ thị. Mỗi nút đều có cạnh nối
(đường nối) với các nút khác không cùng giáo viên giảng dạy từ đó ta sử dụng phương
pháp chèn xen kẽ lớn bé để tìm ra chu trình hay mắc xích và phát họa thành đồ thị.

Vi dụ:
Ta có bảy môn tương ứng với giáo viên giảng như sau:

STT

Môn

Giáo viên

1
2
3
4
5
6
7

Toán
Văn
Hóa
Sinh
Sử
Lý
Địa


Nguyễn văn Nhân
Đào Thanh Diều
Nguyễn văn Nhân
Trịnh Thùy Dương
Phan Thị Huỳnh Dao
Nguyễn văn Nhân
Nguyễn Thanh Sang

Nếu giả sử mỗi môn là một nút tương ứng với số thứ tự của chúng thì ta có chu
trình Hamilton là những đường được in đậm như hình sau.

GVHD : Ths. Lâm Thị Ngọc Châu.

3

Trang 3


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

2

4

1

5
6

7

Ví dụ chu trinh môn học

Theo đó ta có thể xếp lịch thi cho 7 môn thi này như sau:

Ngày thứ:

Môn

1
2
3
4
5
6
7

Toán
Địa
Hóa
Văn
Lý
Sử
Sinh

B. Lý thuyết
1. Đồ thị.
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này.
Ký hiệu: G = [V,U].
Trong đó: V: tập các đỉnh của đồ thị.
U: tập các canh của đồ thị.

Chúng ta có thể phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh
nối hai đỉnh nào đó của đồ thị. Có các loại đồ thị sau:

 Đồ thị có hướng
Đồ thị có hướng G = [V,U] bao gồm:
V: tập các đỉnh của đồ thị.
U: tập các cặp có thứ tự gồm hai phần tử khác nhau thuộc V gọi
là các cung, tức là (u,v) ≠ (v,u). Cung (u,v) được gọi là cung đi từ đỉnh u đến đỉnh v.
Ký hiệu: u → v.

Ví dụ:
GVHD : Ths. Lâm Thị Ngọc Châu.

Tập các đỉnh: V={ 1, 2, 3, 4, 5}
Tập các cạnh:
Trang 4
U={(1,2), (1,5), (2,5), (3,4), (3,1), (4,5).


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

 Đồ thị vô hướng
Đồ thị vô hướng G = [V,U] bao gồm:
V: tập các đỉnh của đồ thị.
U: tập các cặp không có thứ tự gồm hai phần tử khác nhau của V
gọi là các cạnh, tức là (u,v) = (v,u).

Ví dụ:
Tập các đỉnh: V={ 1, 2, 3, 4, 5}
Tập các cạnh:

U={(1,2), (1,3), (2,5), (3,4), (4,5)}.

Trong giới hạn của đề tài này, từ đây về sau khi nói đến đồ thị chúng ta sẽ hiểu đó
là đồ thị vô hướng.

2. Xích, đường đi và chu trình
a. Định nghĩa
Giả sử đồ thị thị G(X, E) là một đồ thị hay đa đồ thị vô hướng.
Dãy α các đỉnh của G(X, E):

α = [ x1, x2, … xi, xi+1, ..., xn-1, xn]
được gọi là một xích hay một dây chuyền, nếu với mọi i (i đi từ 1 đến n) cặp đỉnh xi,
xi+1 kề nhau.
Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ
thị vô hướng G = [V,U] là dãy: x0, x1, ……, xn-1, xn . Trong đó, u = x0, v = xn, (xi,
xi+1) ∈ U, (i = 0, 1, ……, n-1).
Chu trình là đường đi có đỉnh đầu trùng đỉnh cuối.
Ví dụ: Xét lại ví dụ trong đồ thị vô hướng.
 1, 2, 5, 4, 3 : là đường đi độ dài 4 từ đỉnh 1 đến đỉnh 3.
 1, 2, 5, 4, 3, 1 : là một chu trình.
 1, 2, 4, 3 : không là đường đi vì (2, 4) không là cạnh của đồ thị.
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 5


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

3.Tính liên thông
Đồ thị vô hướng G = [V,U] được gọi là liên thông nếu luôn tìm được đường đi giữa

hai đỉnh bất kỳ của nó.

4. Xích, đường đi và chu trình Hamilton
Xích α trong đồ thị vô hướng G=(X, E) được gọi là xích Hamilton, nếu nó đi
qua tất cả các dỉnh của G và qua mỗi đỉnh đúng một lần.nối cách khác xích Hamilton
là một xích sơ cấp, mà nó đi qua tất cả các đỉnh của đồ thị.
Trong đồ thị G:
Đường đi qua tất cả các đỉnh, mỗi đỉnh chỉ một lần, được gọi là đường đi
Hamilton.
Chu trình đi qua tất cả các đỉnh, mỗi đỉnh chỉ một lần (trừ đỉnh đầu trùng với đỉnh
cuối) được gọi là chu trình Hamilton.
Đồ thị có đường đi Hamilton được gọi là đồ thị bán Hamilton.
Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton.
2

3
1

2

3

6

5

1
5

4


Chu trình Hamilton : { 1, 2, 3, 4, 5, 1 }

Đường đi Hamilton: {1, 2, 3, 6, 5 , 4 }

b.Tính chất:
Cho đến nay, chưa tìm ra tiêu chuẩn để nhận biết một đồ thị có là đồ thị Hamilton
không. Phần lớn tìm được là các điều kiện đủ để một đồ thị là một đồ thị Hamilton.
1. Định lý Dirac (1952): Đơn đồ thị vô hướng G có n>2 đỉnh, mỗi đỉnh có bậc
không nhỏ hơn n/2 là đồ thị Hamilton.
2. Cho đồ thị hữu hướng G liên thông mạnh có n>2 đỉnh. Nếu mọi đỉnh có bán
bậc vào không nhỏ hơn n/2 và bán bậc ra không nhỏ hơn n/2 thì đồ thị đó là đồ
thị Hamilton.
3. Đồ thị vô hướng G, tồn tại k đỉnh sao cho nếu xoá đi k đỉnh này và các cạnh
liên thuộc của nó thì đồ thị nhận được sẽ có nhiều hơn k thành phần liên thông.
Lúc đó, khẳng định được đồ thị đó không có chu trình Hamilton.
4. Định lý Ore (1960) : Đơn đồ thị liên thông G có n đỉnh (n ≥ 3), nếu bất kỳ
hai cặp đỉnh không liền kề u và v có tổng các bậc không nhỏ hơn n (deg(u) +
deg(v) ≥ n) thì đồ thị đó là đồ thị Hamilton.

c. Một số định lý thường dùng:
Định lý 1:
Giả sử G = (X, E) là đồ thị vô hướng có n đỉnh.
GVHD : Ths. Lâm Thị Ngọc Châu.

4

Trang 6



Đề tài: xếp lịch thi cho học sinh phổ thông trung học

=>

a. nếu với mọi x, mọi y thuộc X (m(x) + m(y) >= n-1), thì G có xích Hamilton;
b. Nếu với mọi x, y thuộc X (m(x) + m(y) >= n), thì đồ thị G có chu trình
Hamilton.
1. Mọi đồ thị đầy đủ vô hướng với ít nhất hai đỉnh đều có xích Hamilton.
2. Mọi đồ thị đầy đủ vô hướng với ít nhất ba đỉnh đều có chu trình Hamilton.
3. Nếu bậc của mỗi đỉnh trong đồ thị vô hướng G không nhỏ hơn một nửa số
đỉnh, thì nó có chu trình Hamilton.

Định lý 2:
Trong đồ thị có hướng đầy đủ luôn luôn tồn tại đường Hamilton.

C. Phân tích và thiêt kế giải thuật
1. Phân tích
Như đã nối ở trên chúng ta xây dựng đồ thị G trong đó các đỉnh tương ứng với
các môn thi, mỗi cặp đỉnh được nối bằng một cạnh khi và chỉ khi chúng tương ứng với
hai môn thi thuộc hai giáo viên khác nhau. Đồ thị sau được mô tả trong trường hợp:
một thầy có bốn môn thi (tương ứng với các đỉnh A, B, D, E), một giáo viên có một
môn thi (tương ứng với đỉnh C).
Do mỗi giáo viên có số môn thi không vượt quá bốn, nên mỗi đỉnh kề với ít nhât
ba đỉnh. Do đó các đỉnh của đồ thị G có bậc không nhỏ hơn ba, nên tổng bậc của hai
đỉnh bất kỳ không nhỏ hơn 6, nên theo định lý 1 thị đồ thị G có xích (dây chuyền)
Hamilton (gồm các cạnh tô đậm).
Dựa vào xích Hamilton này ta lập được lịch thi theo yêu cầu bài toan, dưới đây
là hình minh họa đồ thị G :
B


C

A
D

G
E
F
Minh họa đồ thị G có xích Hamilton (không tồn tại chu trình)

Ta thấy rằng trong trường hợp này đồ thị không có chu trình Hamilton vì trong
trường hợp này ta thầy tổng bậc của đỉnh A và đỉnh B là 6 chỉ bằng số đỉnh trừ 1 nên
chỉ có xích Hamilton.
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 7


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

Ta xét thêm một ví dụ tiếp theo một giáo viên có 3 môn thi (A, B, C), 1 giáo
viên có 2 môn thi (đỉnh D, E) và 1 giáo viên có một môn thi (đỉnh F) và một giáo viên
có 1 môn thi (đỉnh G).

B
C
A
D

G

E

F

Minh họa đồ thị G có chu trình Hamilton.

Ta thấy trên đồ thị nút có bậc tối thiểu là bậc 4 nên tổng bậc hai đỉnh bất kỳ
không nhỏ hơn 8 lơn hơn số nút của đồ thị nên theo định lý 1 thì đồ thị có chu trình
Hamilton.

2. Thiết kế thuật toán.
Giả sử ta cho mỗi môn là một nút trong đồ thị mỗi nút là một cấu trúc kiểu
struct gồm các trường:
- Trường họ tên chuỗi chứa tên giáo viên giảng dạy.
- Trường môn chứa tên môn học.
- Trường màu chứa màu của nut để hỗ trợ sau này vẽ đồ thị và chu trình.
Tiếp theo ta khai báo một mảng cấu trúc gồm 7 phần tử mỗi phần tử của mảng
đại diện cho một môn học chứa 3 trường và có cùng kiểu vời mảng cấu trúc trên, mảng
này được sử dụng để chứa đựng các môn học theo thứ tự lịch thi và các phần tử của nó
có được là nhờ thao tác chèn các phần tử từ mảng cấu trúc được nhập ban đầu.
Vi du: Ta nhập mảng các môn học thêo thứ tự họ tên giáo viên và số môn học
như sau :

Stt
1
2
GVHD : Ths. Lâm Thị Ngọc Châu.

Giao viên
Lâm Thị Ngọc Châu

Lê Thành Nhân

Môn
Toán
Anh Văn
Trang 8


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

3
4
5
6
7

Lâm Thị Ngọc Châu
Pham Văn Minh
Lâm Thị Ngọc Châu
Phạm Văn Minh
Lâm Thị Ngọc Châu

Lý
Địa
Hóa
Sử
Sinh

Thì ta được mảng với tên môn như sau:


Toán

Anh Văn

Lý

Lâm Thị Ngọc Châu

Địa

Hóa

Lê Thành Nhân

Sử

Sinh

Phạm Văn Minh

Minh họa mảng cấu trúc

Sau khi tổ chức thành mảng cấu trúc ta tiến hành sấp xếp lại mảng theo giáo
viên giảng dạy với các môn có cùng giáo viên dạy đứng gần với nhau trong mảng Sau
đó ta mới tiến hành xếp lịch thi.
Để thực hiện điều này ta tiến hành theo 2 bước sau:
Bước 1: Gom nhóm các môn của cùng một giáo viên giảng dạy lại với nhau để
tiện cho việc sắp xếp sau này
Sau khi thực hiện thao tác này ta có hình ảnh của mảng như hình minh họa dưới
đây:


Toán

Lý

Hóa

Sinh

Lâm Thị Ngọc Châu

Anh Văn
Lê Thành Nhân

Sử

Địa

Phạm Văn Minh

Minh họa bước 1

Bước 2: Sau khi được mảng như trên ta tiến hành xếp lịch thi theo cách chèn
xen kẻ lớn bé tức là chèn xen kẻ giữa các môn của giáo viên dạy nhiều môn nhất với
các môn của giáo viên dạy ít môn nhất, bằng cách lấy các phần tử của mảng đã có chèn
vào mảng cấu trúc mới ( mảng cấu trúc mới có kiểu giống mảng ban đầu ) theo
nguyên tắc chèn xen kẽ lớn bé theo số lượng môn học của từng giáo viên sau khi thực
hiện tháo tác này ta được mảng sau:

Mảng ban đầu


Toán

Lý

Hóa

GVHD : Ths. Lâm Thị Ngọc Châu.

Sinh

Anh Văn

Sử

Địa
Trang 9


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

Toán

Anh Văn

Lý

Địa

Hóa


Sử

Sinh

Mảng mới đã được xếp lịch
Minh họa bước 2

Ta phân tích bước 2 như sau:
Ta chèn từng phần tử của mảng đầu tiên vào mảng mới (gọi là mảng lịch thi).
Ta thấy giáo viên Lâm Thị Ngọc Châu giảng dạy 4 môn thi và cũng là giáo viên giảng
dạy nhiều môn nhất. Ta lấy một trong 4 môn của giáo viên này chèn vào mảng lịch thi
trong trường hợp này là môn học đầu tiên trong 4 môn của giáo viên Lâm Thị Ngọc
Châu tức môn Toán được chèn vào mảng lịch thi.
Mảng ban đầu

Toán

Lý

Hóa

Sinh

Anh Văn

Sử

Địa


Toán
Mảng lịch thi
Minh họa thao tác chèn lớn

Tiếp theo ta xóa môn sinh trong mảng ban đầu và chèn môn học của giáo viên
dạy ít môn học nhất trong ví dụ này là giáo viên Lê Thành Nhân và môn học được chèn
vào mảng lịch thi là môn Anh Văn.
Mảng ban đầu

Toán

Lý

Toán

Anh Văn

Hóa

Sinh

Anh Văn

Sử

Địa

Mảng lịch thi
Minh họa thao tác chèn bé


Cứ tiếp tục như thế chèn giáo viên dạy nhiều môn nhất rồi giáo viên dạy ít môn
nhất rồi môn học của giáo viên dạy ít môn nhất nếu có hai giáo viên có số môn học
giảng dạy là bằng nhau và đồng thời là giáo viên có số môn ít nhất hoặc bé nhât trong
trường hợp đang xét thì ta chọn môn học có giáo viên giảng dạy không trùng môn có
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 10


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

giáo viên giảng dạy liền trước vị trí sắp chèn và cuối cùng ta được hình ảnh 2 mảng cấu
trúc như sau
Mảng ban đầu

Toán

Lý

Hóa

Sinh

Anh Văn

Sử

Địa

Toán


Anh Văn

Lý

Địa

Hóa

Sử

Sinh

Mảng cấu trúc
Minh họa thao tác chèn cuối cùng

Nếu lấy thứ tự của mảng là thứ tự ngày thi thì ta được bảng lịch thi sau:

Ngày thi Lê
thứThành NhânMôn Thi
1
Toán
2
Anh Văn
Lâm Thị Ngọc Châu
3
Lý
4
Địa
5

Hóa
6 Phạm Văn Minh Sử
7
Sinh
Minh họa lịch thi

Sau khi thực hiện các bước trên thì ta đã cơ bản giải quyết được bài toán thỏa
mãn yêu cầu của đề tài.

III. CÔNG CỤ LẬP TRÌNH.
Trong demo và báo cáo niên luận I này em thực hiện chương trình dựa trên
ngôn ngữ lập trình C, trong môi trường Turbo C 3.0, trong chương trình có sử dựng
một số hàm thư viện được C hỗ trợ.

IV. VIẾT CHƯƠNG TRÌNH.
1. Một số hàm mô phỏng giải thuật.
Như đã phân tích ở trên trong code chương trình ta khai báo một cấu trúc lịch
thi kiểu struct gồm 3 trường như sau:
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 11


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

struct lichthi
{
char hoten[50];
char mon[20];
int mau;

} ;
Giải thuật sắp xếp gom nhóm các môn học trong mảng lại gần với nhau. Trong
hàm sắp xếp có tham số đầu vào là mảng cấu trúc lịch thi mà các phần tử của nó là
những môn học đã được nhập. Nếu thấy hai phần tư có họ tên bằng nhau thì ta tiến
hành hoán chuyển vị trí của hai phần tử cho nhau và tăng phần tử mảng lên để việc sắp
xếp được nhanh hơn nếu không thì không chuyển đến phần tử kế tiếp.

void sapxep(struct lichthi lt[])
{
lichthi tam;
for(int i=0;i<7;i++)
for(int j=i+1;j<7;j++)
{ if (strcmp(lt[i].hoten,lt[j].hoten)==0)
{ tam=lt[i+1];
lt[i+1]=lt[j];
lt[j]=tam;
i++;
}
}
}
Tiếp theo ta viết thủ tục xếp lịch thi cho mảng vừa được sắp xếp bởi hàm trên
như hàm có dữ liệu đầu vào là 2 mảng cấu trúc lịch thi mảng lt[] chứa các môn đã được
sắp xếp bởi hàm trên mảng b[] là mảng lịch thi được dùng để chèn phần tử mảng.
Trong hàm có khai báo thêm một số tham số như max, min, lớn, nhỏ để lưu trữ số
môn học của giáo viên có số môn học nhiều nhất (max), số môn học của giáo viên có
số môn học ít nhât (min), lưu trữ vị trí của môn học có số đầu tiên của giáo viên dạy
nhiều môn học nhất (lon) và môn học cuối cùng của giáo viên dạy ít môn nhât (nho)
và một số biến chạy khác.

void lich(struct lichthi lt[],struct lichthi b[])

{
int max,min,lon,nho,t,c=7;
for(int i=0;i<7;i+=2)
{
max=-1;min=4;lon=-1;nho=-1;
//-----------tim so mon nhieu nhat-------------------for(int j=0;j{
t=0;
for(int d=0;dif(strcmp(lt[j].hoten,lt[d].hoten)==0)
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 12


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

t++;
if(max{
}

max=t;
lon=j;

}
//-----------chen phan tu lon nhat vao mang b--------b[i]=lt[lon];
for(j=lon;jlt[j]=lt[j+1];
c--;

//-----------tim giao vien day it mon nhat-----------for(j=c-1;j>=0;j--)
{
t=0;
for(int d=c-1;d>=0;d--)
if(strcmp(lt[j].hoten,lt[d].hoten)==0)
t++;
if((min>t)&&strcmp(lt[j].hoten,b[i].hoten)!=0)
{
min=t;
nho=j;
}
}
//-----------chen phan tu nho nhat vao mang b--------b[i+1]=lt[nho];
for(j=nho;jlt[j]=lt[j+1];
c--;
}
}
2. Một số thủ tục hàm đồ họa.
/*----------------khoi tao do hoa-----------------*/
void ktdh()
{
int Gd,Gm;
Gd=0;
initgraph(&Gd,&Gm,"");
if (graphresult()!=0)
exit(1);
}
/*--------Thu tuc in ra mot xau kieu chu 3D---------*/
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 13


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

void chu3d(int c,int h,int b,int mb,int mc, char
st[50])
{
int i;
for(i=1;i<=b;i++)
{
setcolor(mb);
outtextxy(c+i,h+i,st);
}
setcolor(mc);
outtextxy(c,h,st);
}
Thu tuc hien menu *------------Thu tuc hien
menu-------------------*/
void menu_con(int tt)
{
switch (tt)
{
case 1:
{
setfillstyle(0,0);
bar(230,180,500,332);
setcolor(15);
rectangle(230,180,500,250);

outtextxy(235,200,"- Gioi thieu tong quan bai
toan");
break;
}
case 2:
{
setfillstyle(0,0);
bar(230,180,500,332);
setcolor(15);
rectangle(230,190,500,270);
outtextxy(235,200,"- Thuc hien ct sx lich
thi");
break;
}
case 3:
{
setfillstyle(0,0);
bar(230,180,500,332);
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 14


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

thi");

setcolor(15);
rectangle(230,210,500,260);
setcolor(15);

outtextxy(235,220,"- Chay demo");
outtextxy(235,240,"- Thuc hien ct sx lich
break;
}
case 4:
{
setfillstyle(0,0);
bar(230,180,500,332);
setcolor(15);
rectangle(230,210,500,260);
outtextxy(235,220,"- Thoat chuong trinh");
outtextxy(235,240,"- Cho biet ngay hoan thanh

CT");
}

break;
}

}
*-----Doan CT chinh cua ve_menu----------*/
int i;
char *mang_mn[5];
mang_mn[1]=" 1. Gioi Thieu";
mang_mn[2]=" 2. Giai Quyet";
mang_mn[3]=" 3. Chay Demo";
mang_mn[4]=" 4. Thoat";
setcolor(6);
settextstyle(0,0,1);
for(i=1;i<=4;i++)

{
if (i==chon)
{
cua_so(70,150+i*30,220,180+i*30,4,8,15,13);
menu_con(i);
}
else
cua_so(70,150+i*30,220,180+i*30,4,15,2,4);
outtextxy(73,160+i*30,mang_mn[i]);
}
GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 15


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

}
Một số thủ tục hàm khác được trình bài trên đĩa.

Chương 3

CHƯƠNG TRÌNH DEMO
I. HƯỚNG DẪN CÀI ĐẶT CHƯƠNG TRÌNH

• Copy thư mục NIEN LUAN I từ đĩa CD vào ổ đĩa C.
• Cài đặt chương trình Bordland C++ vào ổ C (Chương trình có sẳn trong CD). Sau
khi cài xong Borland C++ nhấp vào biểu tượng của chương trình ở màn hình

GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 16


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

Desktop -> File -> Open -> Chọn đường dẫn đến file NIEN LUAN I -> CTRL
+F9 để chạy chương trình
Lưu ý: Khi khởi động Borland lên bạn vào Options -> Linker -> Libraries… ->
Đánh dấu vào Graphics library để khới động thư viện đồ họa

II. HƯỚNG DẪN SỬ DỤNG
-Click chọn BL.exe,chọn file->open->c:\nienluan1.cpp,nhấn CTR-F9 để
chương trình chính
-Dùng phím mủi tên chọn chỉ mục tương ứng trên menu đồ họa

vào

Chọn chỉ mục tương ứng,giả sử ta chọn chạy DEMO thì bắt đầu là nhập dữ liệu
vào

GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 17


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

sau đó enter để in ra sơ đồ lịch thi và nhấn phím bất kỳ để thoát khỏi chương trình
Note:

-Số màu hiển thị trên box là mã màu bạn nhập ban đầu
-Ngày thi thứ nhất mặc định bắt đầu từ box đầu tiên bên phải và các môn thi
lần lượt đi theo chiều mũi tên.

GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 18


Đề tài: xếp lịch thi cho học sinh phổ thông trung học

Kết quả sau khi sắp xếp

Chương 4

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
I. KẾT QUẢ ĐẠT ĐƯỢC
Sau bảy tuần 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, Niên Luận cơ bản đã được hoàn thành và đạt được
một số kết quả như sau:
 Hiểu và cài đặt được các 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, có
thể nhập dữ liệu trực tiếp từ bàn phím.
 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.

II. HẠN CHẾ
Mặc dù có cố gắng để hoàn thành Niên Luận 1, nhưng đây là lần đầu tiên viết một
chương trình hoàn chỉnh nên vẫn còn thiếu nhiều kinh nghiệm trong kỹ thuật lập trình

GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 19


Sai
Đúng
Chọn công
việc cần
thực hiện

Đề tài: xếp lịch thi cho học sinh phổ thông trung học

cũng như trong cách tổ chức dữ liệu. Mặt khác, do thời gian hạn chế nên chương trình vẫn
còn nhiều sai xót ngoài ý muốn.
 Đây là một chương trình được viết bằng ngôn ngữ C chạy trên nền hệ điều hành
MS – DOS nên chương trình không hỗ trợ tên File dài.
 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.

III. HƯỚNG PHÁT TRIỂN
 Thiết kế giao diện thân thiện với người sữ dung
 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, Visua Basic, Java,…để
được hổ trợ nhiều hơn.

TÀI LIỆU THAM KHẢO:
[1] Đặng Huy Ruận, Lý thuyết đồ thị và ứng dụng, Nhà xuất bản khoa học và kỹ
thuật - Hà nội 2000.
[2] Phạm văn Thiều, Đặng Hữu Thịnh. Toán rời rạc ứng dụng trong tin học. Nhà

xuất bản Khoa học và Kỹ thuật, Hà Nội - 1997
[3] KENNETH H. ROSEN. Discrete Mathematics and Its Applications. McGraw Hill, 1994.

GVHD : Ths. Lâm Thị Ngọc Châu.

Trang 20