BÀI TẬP PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN
(Sử dụng các phương pháp: Quay lui, nhánh cận, tham lam, chia để trị và qui hoạch
động)
Yêu cầu chung với sinh viên:
1. Trình bày ý tưởng giải bài toán và phương pháp sử dụng (nói cách khác tại sao lại
sử dụng phương pháp đó)
2. Trình bày thuật toán (dạng mã giả) cho bài toán cùng ý nghĩa của các biến, thủ tục
sử dụng trong đó.
3. Đánh giá độ phức tạp của thuật toán (nếu sử dụng đệ qui thì phải trình bày hoặc
dùng phương pháp thế hoặc hoặc dùng định lý “chính” để tính độ phức tạp).
4. Mã hóa bằng ngôn ngữ C, C++ hoặc Java.
5. Đưa ra các ví dụ để test lại chương trình.
1. Cho xâu S (độ dài <10) chỉ gồm các kí tự ‘A’ đến ‘Z’. Các ký tự trong xâu S đôi một
khác nhau. Hãy liệt kê các hoán vị khác nhau của xâu S.
2. Cho số nguyên dương n (n<20), hãy liệt kê tất cả các xâu độ dài n chỉ gồm các kí tự
‘A’ hoặc ‘B’ mà không có 2 kí tự ‘B’ nào đứng cạnh nhau
3. Cho dãy số A gồm n (n<10) số nguyên a
1
, a
2
, a
n
và một số nguyên dương k (1<k<n).
Hãy đưa ra một cách chia dãy số thành k nhóm mà tổng các phần tử trong mỗi nhóm đó
bằng nhau.
4. Một xâu X =x
1
x
2
x
m

11. Cho bàn cờ n x n ô, hai quân tượng (trong cờ vua) gọi là chiếu nhau nếu chúng cùng
nằm trên một đường chéo (chính hoặc phụ). Cho K quân tượng. Hỏi có bao nhiêu các đặt
các quan tượng vào bàn cờ mà các quân tượng không chiếu nhau.
12. N-mino là hình thu được từ N hình vuông 1x1 ghép lại (cạnh kề nhau). Hai N-mino
được gọi là đồng nhất nếu chúng có thể đặt chồng khít lên nhau. Cho một số nguyên N
(1< N <8). Tính và vẽ ra tất cả các N-mino trên màn hình.
13. Cho bàn cờ vua 8x8, mỗi ô ghi một số nguyên dương. Hãy xếp 8 con hậu lên bàn cờ
sao cho không quan nào ăn con nào và tổng các số ghi trên các ô mà quân hậu đứng là
lớn nhất.
14. Một chiếc ba lô có thể chứa được một khối lượng w. Có n (n<20) đồ vật được đánh số
1, 2, , n. Đồ vật i có khối lượng là a
i
và giá trị c
i
. Cần chọn các đồ vật cho vào ba lô để
tổng qiá trị các đồ vật là lớn nhất.
15. Dominoes:
Mỗi con domino là một hình hộp vuông sáu mặt, chỉ trên đúng 2 mặt đối diện (trong số 3
cặp mặt đối diện) ghi các số từ 1 đến 6.
Có N con domino xếp theo hàng ngang sao cho một trong hai mặt có số ở trên. Gọi X là
tổng của các số ở mặt trên của các con domino và Y là tổng các số ở mặt dưới của các con
domino đó. Rõ ràng khi quay một con domino 180
o
thì X và Y sẽ thay đổi. Bài toán đặt ra
là: cần quay ít nhất bao nhiêu quân domino nhất để độ chên lệch giữa X và Y là bé nhất.
16. Một lưới MxN (M, N ≤ 10) ô, mỗi ô đặt một bóng đèn bật hoặc tắt. Trên mỗi dòng và
mỗi cột có một công tắc. Nếu tác động vào công tắc dòng i (i=1 M) hoặc công tắc cột j
(j=1 N) thì tất cả các bóng đèn trên dòng i hoặc cột j sẽ thay đổi trạng thái. Hãy tìm cách
tác động vào các công tắc để được nhiều đèn sáng nhất.
17. Có 16 đồng xu xếp thành bảng 4x4, mỗi đồng xu có thể úp hoặc ngửa. Tại mỗi bước

1
, p
2
, p
k
: đôi một khác nhau
- p
1
+ p
2
+ + p
k
= N
- S = p
1
* p
2
* * p
k
đạt

giá trị lớn nhất.
23. Cho số nguyên dương N, hãy tách N thành tổng ít nhất các số Fibonacci
24. Tìm K chữ số cuối cùng của M
N
(0<K<10, 0≤M, N≤10
9
).
25. Kiểm tra tính nguyên tố của số N (N≤10
9

phần tử còn lại, để nhận được một dãy con lồi dài nhất.
29. Palindrome: Một xâu được gọi là đối xứng nếu đọc từ trái qua phải cũng giống như
đọc từ phải qua trái. Cho một xâu gồm các ký tự ‘a’ đến ‘z’, hãy chèn vào xâu đó ít nhất
các kí tự để thu được một xâu đối xứng.
30. Stones: Có N đống sỏi, đống thứ i có A
i
viên sỏi. Ta có thể ghép hai đống sỏi kề nhau
thàh một đống và mật một chi phí bằng tổng số sỏi của hai đống. Hãy tìm cách ghép N
đống sỏi thành một đống với chi phí là nhỏ nhất.
31. Cắt hình 1: Có một hình chủ nhật MxN ô vuông, mỗi lần ta được cắt một hình chủ
nhật thành hai hình chủ nhật con theo chiều ngang hoặc chiều dọc và lại tiệp tục cắt các
hình chữ nhật con cho đến khi được hình vuông thì dừng lại. Hỏi có thể cắt hình chủ nhật
MxN thành ít nhất bao nhiêu hình vuông.
32. Cắt hình 2:
Cho một bảng số gồm M dòng, N cột, các giá trị của bảng A chỉ là 0 hoặc 1. Ta muốn cắt
bảng A thành các hình chữ nhật con sao cho các hình chữ nhật con có giá trị toàn bằng 1
hay toàn bằng 0. Một lần cắt là một nhát cắt thẳng theo dòng hoặc theo cột của một hình
chữ nhật thành hai hình chữ nhật riêng biệt. Cứ tiếp tục cắt cho đên khi hình chữ nhật có
các giá trị taòn ằng 1 hay toàn bằng 0. Hãy tìm cách cắt để số hình chữ nhật con nhận
được, có giá trị toàn là 1 hay toàn bằng 0, là nhỏ nhất.
33. TKSEG:
Cho dãy số A gồm N số nguyên và số nguyên K. Tìm dãy chỉ số 1≤ i
1
< i
2
< <i
3k
≤ N sao
cho:
S = (a

là một cáh xếp lần lượt các từ của văn bản vào các dòng, mỗi dòng có đội dài L, sao cho
tổng đội dài của cá từ trên cùng một dòng không vượt quá L. Ta gọi hệ số phạt của mỗi
dòng trong cách phân trang là hiệu số L-S, trong đó S là tổng độ dài của cá từ xếp trên
dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các
dòng.
Tìm cách phân trang với hệ số phạt nhỏ nhất.
37. Chọn số
Cho mảng A có kích thước NxN gồm các số nguyên không âm. Hãy chọn ra K số sao cho
mỗi dòng có nhiều nhất 1 số được chọn, mỗi cột có nhiều nhất 1 số được chọn để tổng K
số đó là lớn nhất.