Ebook Sáng tạo trong thuật toán và lập trình
Một bài toán tin được hiểu là
khó nếu ta sử dụng thuật giải mới nảy sinh trong đầu khi vừa biết nội
dung bài toán thì hoặc là ta thu được kết quả sai hoặc là lời giải thu
được sẽ không hữu hiệu theo nghĩa chương trình đòi hỏi quá nhiều bộ nhớ
hoặc/và chạy quá lâu. Những thuật giải nảy sinh lập tức trong đầu như
vậy thường được gọi là thuật giải tự nhiên. Dĩ nhiên, khái niệm này chỉ
là tương đối. Nếu bạn đã nắm vững nhiều dạng thuật giải và đã từng
thử sức với nhiều bài toán khó thì đến một lúc nào đó các thuật giải tự nhiên của bạn sẽ đáng tin cậy. Đó cũng chính là mục đích của sự học tập và rèn luyện và cũng là ước mơ của người viết tập sách này.
thử sức với nhiều bài toán khó thì đến một lúc nào đó các thuật giải tự nhiên của bạn sẽ đáng tin cậy. Đó cũng chính là mục đích của sự học tập và rèn luyện và cũng là ước mơ của người viết tập sách này.
Để
đọc sách không đòi hỏi bạn phải có tri thức gì đặc biệt. Để tiếp thu tốt
và đóng góp cho việc hiệu chỉnh và cải tiến nội dung cuốn sách chỉ cần
bạn biết sử dụng một trong các ngôn ngữ lập trình: Pascal trong môi
trường Turbo hoặc Free Pascal hoặc C#.
Các
kĩ thuật lập trình được minh hoạ qua những bài toán cụ thể tương đương
với trình độ nâng cao của học sinh và sinh viên. Hình thức phát biểu bài
toán suy cho cùng là không quan trọng. Các kĩ thuật lập trình và phương
pháp xây dựng thuật giải cho những bài toán thường được dùng rộng rãi
trong quá trình thiết kế và cài đặt các phần mềm ứng dụng trong thực
tiễn, cho nên việc sớm làm chủ các tri thức này mới thật sự là cần
thiết. Chính vì vậy mà chúng tôi cho rằng nội dung cuốn sách có thể phù
hợp với các bạn học sinh, sinh viên các trường đại học và những bạn đọc
muốn tự hoàn thiện tri thức trong lĩnh vực giải thuật và lập trình.
Thiết nghĩ cuốn sách cũng có thể được dùng làm tài liệu tham khảo để dạy
ở các lớp chuyên tin của các trường phổ thông. Nội dung sách gồm hai
phần. Phần thứ nhất giới thiệu vắn tắt về bản chất các phương pháp và kĩ
thuật lập trình và các đề toán để các bạn thử sức. Phần thứ hai trình
bày và phân tích chi tiết lời giải cùng với những bình luận và xuất xứ
của các bài toán.
Trong
tập sách này cũng cung cấp toàn văn các chương trình viết bằng ngôn ngữ
lập trình Pascal và C# để bạn đọc tiện so sánh với lời giải của mình.
Cả hai phần đều đề cập đến nội dung của tám chương như sau.
Chương
thứ nhất trình bày sơ đồ chung để giải một bài toán tin. Các bài tập ở
chương này hầu hết thuộc loại dễ giải. Chương thứ hai giới thiệu các kĩ
thuật sinh dữ liệu một cách tự động nhằm phục vụ cho việc kiểm thử
(test) chương trình. Chương thứ ba trình bày các kĩ thuật quản lí bàn
phím và màn hình. Chương thứ tư đề cập đến cách thức tổ chức dữ liệu cho
một bài toán tin.
Ba chương tiếp theo giới thiệu ba trong số các phương pháp khá phổ biến thường được vận dụng trong thiết kế thuật giải. Đó là phương pháp tham lam, phương pháp quay lui và quy hoạch động. Các phương pháp này đều là không vạn năng theo nghĩa không thể dùng chúng để giải mọi bài toán tin. Trong thực tế, một phương pháp vạn năng như vậy là không hữu hiệu. Tuỳ theo nội dung bài toán mà ta chọn phương pháp phù hợp. Đó cũng là điểm khó, đòi hỏi ở bạn đọc một quá trình tìm tòi và tích luỹ kinh nghiệm.
Ba chương tiếp theo giới thiệu ba trong số các phương pháp khá phổ biến thường được vận dụng trong thiết kế thuật giải. Đó là phương pháp tham lam, phương pháp quay lui và quy hoạch động. Các phương pháp này đều là không vạn năng theo nghĩa không thể dùng chúng để giải mọi bài toán tin. Trong thực tế, một phương pháp vạn năng như vậy là không hữu hiệu. Tuỳ theo nội dung bài toán mà ta chọn phương pháp phù hợp. Đó cũng là điểm khó, đòi hỏi ở bạn đọc một quá trình tìm tòi và tích luỹ kinh nghiệm.
Riêng chương cuối cùng của cuốn sách, chương thứ tám giới thiệu một số bài toán tin để bạn đọc tự phát hiện phương pháp giải.
Những
nội dung trong tập sách này được tập hợp và chỉnh lí từ các bài giảng
về thuật toán và lập trình, từ các cuốn sách Tìm đường trong mê cung,
Bắn tàu trên biển và từ các bài viết của tác giả đăng trong tạp chí Tin
học và nhà trường và một số lời giải hay của các bạn học sinh.
Lần
xuất bản này chúng tôi trình bày thêm các bài giải viết trong môi trường
ngôn ngữ C# để các bạn sinh viên cùng tham khảo. Hi vọng rằng trong các
dịp khác chúng tôi sẽ cung cấp thêm các phương án giải với bạn đọc. Tuy
nhiên, suy cho cùng, môi trường lập trình chỉ mang tính minh hoạ. Khi
đã biết thuật toán, việc thể hiện thuật toán đó trong môi trường lập
trình cụ thể chắc chắn là việc làm quen thuộc của bạn đọc.
Xin
được chân thành cảm ơn các em học sinh, sinh viên, các thầy cô giáo, bạn
bè và đồng nghiệp đã chia sẻ kinh nghiệm và trợ giúp tài liệu, nhận xét
và bình luận để hình thành nội dung cơ bản của cuốn sách.
Chúng
tôi hi vọng sẽ tiếp tục nhận được những ý kiến phê bình của bạn đọc về
nội dung, chất lượng và hình thức trình bày để có thể định hướng cho các
tập tiếp theo.
Hà Nội, Lễ Hội Đạp Thanh – 2008
N.X.H
Hà Nội, Lễ Hội Đạp Thanh – 2008
N.X.H
Mục lục:
Tập 1
Chương I GIẢI MỘT BÀI TOÁN TINBài 1.1. Số thân thiện
Bài 1.2. Số cấp cộng
Bài 1.3. Số cấp nhân
Bài 1.4. Mảng ngẫu nhiên
Bài 1.5. Chia mảng tỉ lệ 1:1
Bài 1.6. Chia mảng tỉ lệ 1:k
Chương II SINH DỮ LIỆU VÀO VÀ RA
Bài 2.1. Sinh ngẫu nhiên theo khoảng
Bài 2.2. Sinh ngẫu nhiên tăng
Bài 2.3. Sinh hoán vị ngẫu nhiên
Bài 2.4. Sinh ngẫu nhiên đều
Bài 2.5. Sinh ngẫu nhiên tỉ lệ
Bài 2.6. Sinh ngẫu nhiên tệp tăng
Bài 2.7. Sinh ngẫu nhiên tệp cấp số cộng
Bài 2.8. Sinh ngẫu nhiên mảng đối xứng
Bài 2.9. Số độ cao h
Bài 2.10. Tệp các hoán vị
Bài 2.11. Đọc dữ liệu từ tệp vào mảng biết hai kích thước
Bài 2.12. Đọc dữ liệu từ tệp vào mảng biết một kích thước
Bài 2.13. Đọc dữ liệu từ tệp vào mảng đối xứng
Bài 2.14. Đếm tàu
Bài 2.15. Sắp đoạn
Chương III BÀN PHÍM VÀ MÀN HÌNH
Bài 3.1. Bảng mã ASCII
Bài 3.2. Bộ Tú lơ khơ
Bài 3.3. Hàm GetKey
Bài 3.4. Trò chơi 15
Bài 3.5. Bảng nhảy
Chương IV TỔ CHỨC DỮ LIỆU
Bài 4.1. Cụm
Bài 4.2. Bài gộp
Bài 4.3. Chuỗi hạt
Bài 4.4. Sắp mảng rồi ghi tệp
Bài 4.5. abc – sắp theo chỉ dẫn
Bài 4.6. Xâu mẫu
Chương V PHƯƠNGPHÁP THAM LAM
Bài 5.1. Băng nhạc
Bài 5.2. Xếp việc
Bài 5.3. Xếp ba lô
Bài 5.4. Cây bao trùm ngắn nhất
Bài 5.5. Trộn hai tệp
Chương VI PHƯƠNGPHÁP QUAY LUI
Bài 6.1. Tám Hậu
Bài 6.2. Từ chuẩn
Bài 6.3. Tìm đường trong mê cung
Chương VII QUY HOẠCH ĐỘNG
Bài 7.1. Chia thưởng
Bài 7. 2. Palindrome
Bài 7.3. Cắm hoa
Bài 7.4. Tìm các đường ngắn nhất
Chương VIII SUY NGẪM
Bài 8.1. Lát nền
Bài 8.2. Chữ số cuối khác 0
Bài 8.3. Hình chữ nhật tối đại trong ma trận 0/1
Bài 8.4. Ma phương
Bài 8.5. Tháp Hà Nội cổ
Bài 8.6. Tháp Hà Nội xuôi
Bài 8.7. Tháp Hà Nội ngược
Bài 8.8. Tháp Hà Nội thẳng
Bài 8.9. Tháp Hà Nội sắc màu (Hà Nội Cầu vồng)
Tập 2
CHƯƠNG 1 CÁC BÀI TOÁN VỀ ĐOẠN THẲNGBài 1.1 Đoạn rời 1
Bài 1.2 Đoạn gối 1
Bài 1.3 Đoạn gối 2
Bài 1.4 Đoạn gối 3
Bài 1.5 Đoạn bao nhau 1.
Bài 1.6 Đoạn bao nhau 2
Bài 1.7 Phủ đoạn 1
Bài 1.8 Xanh đỏ tím vàng 1
Bài 1.9 Xanh đỏ tím vàng 2
Bài 1.10 Phủ đoạn 2
Bài 1.11 Đoạn rời 2
Bài 1.12 Ghép hình chữ nhật
Bài 1.13 Xanh đỏ
Bài 1.14 Xếp đoạn
Bài 1.15 Các hình chữ nhật
Bài 1.16 Các tam giác vuông cân
CHƯƠNG 2 CÁC HÀM NEXT.
Bài 2.1 Số sát sau cùng độ cao
Bài 2.2 Số sát sau cùng chữ số
Bài 2.3 Các hoán vị.
Bài 2.4 Tổ hợp
Bài 2.5 Số Kapreka
Bài 2.6 Khóa vòng
Bài 2.7 Trả tiền
Bài 2.8 Dãy Farey
Bài 2.9 Qúy Mùi
Bài 2.10 Tổng đoạn
Bài 2.11 Đoạn không giảm dài nhất
Bài 2.12 Đoạn đơn điệu dài nhất.
Bài 2.13 Lũy thừa 2, 3 và 5.
CHƯƠNG 3 TRÒ CHƠI
Bài 3.1. Bốc sỏi A
Bài 3.2. Bốc sỏi B
Bài 3.3. Bốc sỏi C
Bài 3.4. Chia đoạn
Bài 3.5. Bốc sỏi D
Bài 3.6. Bốc sỏi E
Bài 3.7. Bốc sỏi F
Bài 3.8. Chia Hình chữ nhật
Bài 3.9. Bốc sỏi G
Bài 3.10. Chia Hình hộp
Bài 3.11. Trò chơi NIM
Bài 3.12. Cờ bảng
Bài 3.13. Cờ đẩy
Bài 3.14. Bốc sỏi H
CHƯƠNG 4 CÁC THUẬT TOÁN SẮP ĐẶT
4.1 Cờ tam tài
4.2 Lưới tam giác đều
4.3 Dạng biểu diễn của giai thừa
4.4 Xếp sỏi
4.5 Dãy các hoán vị
4.6 Bộ bài
4.7 Thuận thế
4.8 Các nhà khoa học
4.9 Chín chiếc đồng hồ
4.10 Số duy nhất
Tập 3
CHƯƠNG 1 CÁC THUẬT TOÁN TRÊN STRING1.1 Xâu kí tự
1.2 Về tổ chức dữ liệu vào/ra
1.3 Data
1.4 Xâu con chung
1.5 Đoạn chung
1.6 Đoạn lặp
1.7 Từ điển
1.8 TEFI
1.9 E xiếc
CHƯƠNG 2 XỬ LÍ DÃY LỆNH VÀ BIỂU THỨC
2.1 Val
2.2 Xâu thu gọn
2.3 Robot
2.4 Hàm nhiều biến
2.5 Files
2.6 Gen
2.7 Tối ưu hóa chương trình
2.8 Mức của biểu thức
2.9 Tháp
2.10 Mi trang
2.11 Xếp thẻ
2.12 Xếp xe
CHƯƠNG 3 CẶP GHÉP
3.1 Chị Hằng
3.2 Domino
3.3 Thám hiểm
3.4 Show
3.5 Cặp ghép cực đại: Chị Hằng 2
CHƯƠNG 4 CÁC PHÉP LẬT VÀ CHUYỂN VỊ
4.1 Lật xâu
4.2 Lật số nguyên
4.3 Sân bay vũ trụ
4.4 Cân
4.5 Biprime
4.6 Chuyển bi
4.7 Lát nền 2
4.8 Test
4.9 Giải mã
CHƯƠNG 5 LUYỆN TẬP TỪ CÁC ĐỀ THI
5.1 Số nguyên tố cùng độ cao
5.2 Số nguyên tố cùng số bít 1
5.3 Cắt hình
5.4 Tổng nhỏ nhất
5.5 Lò cò
5.6 Chuyển tin
5.7 Mã BW
5.8 Tam giác Pascal
5.9 Sơn mô hình
5.10 Nhúng mô hình
5.11 Số sát sau nhị phân
5.12 Hàm f(n)
5.13 Hàm h(n)
5.14 Rhythm
5.15 Cóc
5.16 Trả tiền
5.17 Game
5.18 Robots
hay lắm. cảm ơn vì tinh thần share
Trả lờiXóahay day thu xem da
Trả lờiXóakhông có tập 4 và 5 ak
Trả lờiXóa