Một vài kỹ thuật lập trình potx

Một vài kỹ thuật lập trình

Ngày gửi bài: 19/01/2006

So luot doc: 1318

Bài viết này là lược dịch từ chương 10 ″Algorithm Design Techniques″ của quyển sách

nổi tiếng ″Data Structure and Algorithms″ của các tác giả Aho A.V., Hopcroft J.E. và

Ullman J.D. Tiêu đề do người biên soạn bài viết tự đặt.

Các bạn trẻ thân mến.

Thuật toán, kỹ thuật lập trình luôn là một điều bí ẩn và hấp dẫn đối với các bạn trẻ, các

bạn học sinh và sinh viên đang ngồi trên ghế nhà trường. Nhiều bài toán khó, đa dạng

tưởng chừng như không thể tìm được lời giải lại ẩn chứa bên trong những thuật toán đơn

giản, tuyệt đẹp đến không ngờ. Cuốn sách ″Data Structure and Algorithms″ của các tác

giả Aho A.V., Hopcroft J.E. và Ullman J.D đã ra đời cách đây 20 năm nhưng giờ đây đọc

lại vẫn thấy rất mới mẻ và chứa đựng nhiều ý tưởng hay. Đặc biệt chương ″Một vài kỹ

thuật thiết kế thuật toán″ chứa đựng nhiều ý tưởng xác định cho toàn bộ định hướng

nghiên cứu và giải quyết bài toán của ngày hôm nay. Nhân dịp số báo đặc biệt Tết Quí

Mùi, chúng tôi chân trọng giới thiệu với bạn đọc, đặc biệt là các bạn học sinh, sinh viên

chuyên tin lược dịch của chương này. Trong quá trình biên soạn, chúng tôi đã thay đổi

chút ít cho phù hợp với đối tượng của độc giả Tin học & Nhà trường. Trong khi trình bày

thuật toán các tác giả đã sử dụng khá nhiều kỹ thuật phân tích đánh giá độ phức tạp, đối

với các bạn lần đầu làm quen với những khái niệm này có thể hoàn toàn bỏ qua chúng mà

không ảnh hưởng gì đến việc đọc các phần khác của bài viết. Chúc các bạn một năm mới

với nhiều sáng tạo mới, và mong rằng những ý tưởng của bài viết này được các bạn tiếp

nhận và áp dụng sáng tạo trong công việc của mình.

1. Thuật toán Chia để Trị (Divide & Conquer)

Có lẽ thuật toán được sử dụng nhiều nhất, quan trọng nhất là kỹ thuật ″Chia để Trị″. Kỹ

thuật này sẽ chia bài toán hiện thời thành N bài toán nhỏ hơn, thực hiện lời giải cho từng

bài toán nhỏ này và từ đó xây dựng thuật toán cho bài toán lớn tổng hợp. Ví dụ cho các

thuật toán này là Sắp xếp Trộn(1) hoặc Tìm kiếm Nhị phân(2) mà các bạn đã đã được biết

trong chương trình Tin học Cơ bản.

Để minh họa rõ hơn cho kỹ thuật này chúng ta hãy xét một ví dụ quen thuộc đó là bài

toán ″Tháp Hà Nội″. Giả sử có 3 cọc A, B, C. Ban đầu tại A đặt một số đĩa với thứ tự trên

nhỏ dưới to như hình vẽ.