Sáng tạo trong thuật toán và lập trình

T Ủ S Á C H T R I T H Ứ C D U Y T Â N




N G U Y Ễ N X U Â N H U Y













S Á N G T Ạ O

T R O N G T H U Ậ T T O Á N

V À

L Ậ P T R Ì N H





v ớ i n g ô n n g ữ P a s c a l v à C # T ậ p 1






T u y ể n c á c b à i t o á n T i n n â n g c a o

c h o h ọ c s i n h v à s i n h v i ê n g i ỏ i


M Ụ C L Ụ C






Chƣơng I
Lời nói

MỘT BÀI TOÁN TIN
i

1

Bài 1.1.
Số thân thiện
2

Bài 1.2.
Số cấp cộng
8

Bài 1.3.
Số cấp nhân
11

Bài 1.4.
Mảng ngẫu nhiên
13

Bài 1.5.
Chia mảng tỉ lệ 1:1
16

Bài 1.6.
Chia mảng tỉ lệ 1:k
21


Chƣơng II

SINH LIỆU VÀO VÀ RA

27

Bài 2.1.
Sinh ngẫu nhiên theo khoảng
27

Bài 2.2.
Sinh ngẫu nhiên tăng
29

Bài 2.3.
Sinh hoán vị ngẫu nhiên
31

Bài 2.4.
Sinh ngẫu nhiên đều
33

Bài 2.5.
Sinh ngẫu nhiên tỉ lệ
36

Bài 2.6.
Sinh ngẫu nhiên tệp tăng
40

Bài 2.7.
Sinh ngẫu nhiên tệp cấp số cộng
42

Bài 2.8.
Sinh ngẫu nhiên mảng đối xứng
43

Bài 2.9.
Số độ cao h
46

Bài 2.10.
Tệp các hoán vị
49

Bài 2.11.
Đọc dữ liệu từ tệp vào mảng biết hai kích thước
53

Bài 2.12.
Đọc dữ liệu từ tệp vào mảng biết một kích thước
56

Bài 2.13.
Đọc dữ liệu từ tệp vào mảng đối xứng
60

Bài 2.14.
Đếm tàu
62

Bài 2.15.
Sắp đoạn
65


Chƣơng III
Bài 3.1.

BÀN PHÍM VÀ MÀN HÌNH
Bảng mã ASCII

79
79

Bài 3.2.
Bộ Tú lơ khơ
80

Bài 3.3.
Hàm GetKey
88

Bài 3.4.
Trò chơi 15
90

Bài 3.5.
Bảng nhảy
95


Chƣơng IV

CHỨC DỮ LIỆU

107

Bài 4.1.
Cụm
107

Bài 4.2.
Bài gộp
112

Bài 4.3.
Chuỗi hạt
120



Bài 4.4.
Sắp mảng rồi ghi tệp
129

Bài 4.5.
abc - sắp theo chỉ dẫn
133

Bài 4.6.
Xâu mẫu
141


Chƣơng V
Bài 5.1.
PHÁP THAM LAM
Băng nhạc
153
153

Bài 5.2.
Xếp việc
158

Bài 5.3.
Xếp ba lô
165

Bài 5.4.
Cây bao trùm ngắn nhất
170

Bài 5.5.
Trộn hai tệp
177


Chƣơng VI
PHÁP QUAY LUI
193

Bài 6.1.
Tám Hậu
195

Bài 6.2.
Từ chuẩn
207

Bài 6.3.
Tìm đường trong mê cung
216


Chƣơng VII
QUY ĐỘNG
227

Bài 7.1.
Chia thưởng
228

Bài 7. 2.
Palindrome
235

Bài 7.3.
Cắm hoa
243

Bài 7.4.
Tìm các đường ngắn nhất
253


Chƣơng VIII
Bài 8.1.
SUY
Lát nền
267
267

Bài 8.2.
Chữ số cuối khác 0
276

Bài 8.3.
Hình chữ nhật tối đại trong ma trận 0/1
281

Bài 8.4.
Ma phương
291

Bài 8.5