MỤC LỤC
I. Bài toán (Đề 24)
II. Phân tích bài toán
III. Xây dựng giải thuật
a. Tư tưởng giải thuật 5
b. Phương án thực hiện 5
IV. Đánh giá giải thuật xây dựng được
1
Hoµng Anh TuÊn -
CH21CNTT Vinh
BÀI TẬP LỚN MÔN HỌC
PHÂN TÍCH ĐÁNH GIÁ THUẬT TOÁN
I. Bài toán (Đề 24)
Người ta may sẵn n cái áo với các kích thước vai V(1), V(2), …, V(n) cho
n học sinh. Các học sinh này được đánh số từ 1 tới n và có kích thước vai là
p(1), p(2), …, p(n). Nếu học sinh i được nhận áo j thì độ lệch vai cho trường
hợp này sẽ là |V(i)-p(j)|. Một phương án phân phối áo cho các học sinh 1, 2, n
được mô tả như một hoán vị π
1
, π
2
, , π
n
với hàm ý học sinh i nhận được áo π
i
.
Độ lệch của phương án này được định nghĩa bằng
max {|V(i) – p(
π
i
)|, i=1,2, ,n}

− Trường hợp 3:
Trường hợp 3
− Trường hợp 4:
Trường hợp 4
− Trường hợp 5: Là trường hợp suy biến của các trường hợp trên.
3
Hoµng Anh TuÊn -
CH21CNTT Vinh
1
n
Ma
p
Ma
v
Mi
p
Mi
v
Size
1
n
Ma
v
Ma
p
Mi
p
Mi
v
Size

số từ 1 đến n theo thứ tự đó. (1)
− Sắp xếp n cái áo theo thứ tự không giảm của kích thước vai, đánh
số từ 1 đến n theo thứ tự đó. (2)
− Lần lượt phát áo cho học sinh theo quy tắc: Học sinh thứ 1 được
nhận áo thứ 1… Học sinh thứ n nhận áo thứ n. (3)
Rõ ràng phương án phân phối áo như trên là thoả mãn yêu cầu đầu bài, với
độ lệc có thể là |Mip-Miv| hoặc |Map-Mav| tuỳ từng trường hợp. Như vậy chúng
ta có thể tìm ra một lời giải cho bài toán theo cách trên. Nhưng giải thuật này có
những hạn chế là:
− Một là: Việc sắp xếp học sinh và áo theo một trật tự nào đó là một
vấn đề khó khăn và tốn kém (O(n
2
)). Giả sử ta phải phân phối
khoảng 10000 chiếc áo cho 10000 học sinh. Thông thường để sắp
xếp học sinh và áo như trên chúng ta thường dùng phương pháp sắp
xếp chèn hoặc chọn. Khi đó, trường hợp xấu nhất ta phải dùng đến
4
Hoµng Anh TuÊn -
CH21CNTT Vinh
1
n
Ma
p
Ma
v
Mi
v
Mi
p
Size


Mi
p
Ma
v
Ma
p
. Các trường hợp khác tương tự.
 B1: Tìm các giá trị Ma
v
, Ma
p
, Mi
v
, Mi
p
. Trong đó
5
Hoµng Anh TuÊn -
CH21CNTT Vinh
* Ma
v
- Là giá trị lớn nhất của vai áo
* Mi
v
- Là giá trị nhỏ nhất của vai áo
* Ma
p
- Là kích thước lớn nhất của vai học sinh
* Mi

+d. Chứa học sinh có cỡ vai bé nhất Mip
i
(có thể được
xác định nhờ bước xác định đoạn trước). Vấn đề ở đây là xác định
kích cỡ lớn nhất Mav
i
của những cái áo trong đoạn này. Mav
i
có thể
được xác định bằng cách duyệt hết các cái áo chưa được phân nhóm
xem cỡ vai của cái áo nào gần với cỡ vai Map
i
nhất nhưng vẫn nhỏ
hơn Map
i
thì đó chính là Mav
i
6
Hoµng Anh TuÊn -
CH21CNTT Vinh
1
n
Ma
v
Mi
p
Mi
v
Size
Ma

càng lớn.
7
Hoµng Anh TuÊn -
CH21CNTT Vinh