200 bài toán kinh điển trong lập trình

250 bài tập kỹ thuật lập trình C [230 bài tập chính thức, 20 bài tập bổ sung] trong tập sách này được chọn lọc từ các bài tập thực hành môn Ngôn ngữ lập trình C và Lập trình Cấu trúc dữ liệu bằng ngôn ngữ C cho sinh viên Ðại học và Cao đẳng chuyên ngành Công nghệ Thông tin. Các bài tập đã được sắp xếp theo một trình tự nhất định, nhằm đảm bảo cho người đọc nắm vững một cách có hệ thống các kiến thức cần thiết của kỹ thuật lập trình nói chung và ngôn ngữ lập trình C nói riêng; chuẩn bị nền tảng cho các môn học có liên quan. Mặc dù cố gắng duyệt qua các vấn đề cơ bản của ngôn ngữ lập trình C, nhưng tập sách này được viết với mục tiêu củng cố và nâng cao khả năng làm việc với ngôn ngữ C. Khác với các sách bài tập khác, các bài tập trong tập sách này đều có hướng dẫn giải chi tiết. Khi hướng dẫn giải bài tập, chúng tôi cố gắng:-Thể hiện một góc nhìn riêng về kỹ thuật lập trình bằng ngôn ngữ C, chú ý đến những đặc điểm của ngôn ngữ C. Nói cách khác, chúng tôi chú ý đến lập trình theo phong cách của C.-Phân tích quá trình tư duy khi giải quyết vấn đề, củng cố các kiến thức toán học cũng như lập trình cơ bản, nhằm làm nổi bật vai trò của ngôn ngữ lập trình như một công cụ hỗ trợ mang tính thực tế cao.-Lập trình thật ngắn gọn và rõ ràng giúp người đọc hiểu rõ vấn đề. Nâng cao kỹ năng lập trình. Người đọc sẽ thấy thú vị và bất ngờ với một số kỹ thuật giải quyết vấn đề.-Theo chuẩn ANSI/ISO C89 phù hợp với nhà trường ở Việt nam, chuẩn mới nhất là ANSI/ISO C11 [ISO/IEC 9899:2011].-Các bài giải của 250 bài tập và các phương án giải khác đã được kiểm tra bằng Cppcheck 1.72 [cppcheck.sourceforge.net]. Chúng tôi tin rằng tập sách này sẽ giúp người đọc thật sự củng cố và nâng cao kiến thức lập trình với ngôn ngữ C. Mặc dù đã dành rất nhiều thời gian và công sức cho tập sách, phải hiệu chỉnh nhiều lần và chi tiết, nhưng tập sách không thể nào tránh được những sai sót và hạn chế. Chúng tôi thật sự mong nhận được các ý kiến góp ý từ bạn đọc để tập sách có thể hoàn thiện hơn. Xin chân thành cảm ơn anh Lê Gia Minh đã xem và đóng góp nhiều ý kiến quý giá cho tập sách. Cảm ơn bạn Nguyễn Ðình Song Toàn đã khuyến khích tôi học C. Cảm ơn các anh Thân Văn Sử, Lê Mậu Long, Nguyễn Minh Nam, tôi đã học tập được rất nhiều kinh nghiệm từ các anh.

Bài toán tháp Hà Nội có lẽ không còn xa lạ với sinh viên CNTT tại Việt Nam. Bài toán này thường xuyên được sử dụng để giảng dạy về đệ quy và lập trình trong các khóa học về Toán học và Khoa học Máy Tính.

Tháp Hà Nội là một bài toán quen thuộc và thú vị trong lĩnh vực toán học và lập trình. Nó mô phỏng việc di chuyển đĩa từ một cọc này sang một cọc khác, tuân theo một số quy tắc nhất định. Bài toán này mang tính logic cao và yêu cầu sử dụng phương pháp đệ quy để giải quyết một cách hiệu quả.

Chắc chắn bạn đã từng nghe về bài toán tháp Hà Nội, một thách thức kinh điển khi nói đến đệ quy trong lập trình. Trong bài viết này, chúng ta sẽ cùng nhau khám phá cách giải quyết bài toán này bằng phương pháp đệ quy, một kỹ thuật mạnh mẽ và linh hoạt mà chúng ta thường gặp trong lập trình.

Hãy cùng bắt đầu và khám phá sự kỳ diệu của đệ quy thông qua bài toán tháp Hà Nội.

[*] Nếu chưa nắm rõ "Đệ Quy là gì?" thì bạn hãy tham khảo bài viết dưới đây của 200Lab nhé.

Đệ Quy là gì? Có bao nhiêu loại Đệ Quy cơ bản?

Đệ quy là một khái niệm rất quan trọng trong cấu trúc dữ liệu và giải thuật nói riêng, và trong ngành khoa học máy tính nói chung. Chúng ta cùng tìm hiểu về đệ quy trong bài viết này nhé.

1. Giới thiệu bài toán tháp Hà Nội

1.1. Lịch sử hình thành bài toán Tower of Hanoi

Bài toán tháp Hà Nội có nguồn gốc từ một truyền thuyết Ấn Độ và đã được biết đến rộng rãi do nhà toán học người Pháp, Édouard Lucas, giới thiệu vào năm 1883 trong quyển sách "Récréations Mathématiques".

Truyền thuyết kể về một ngôi đền cổ ở Ấn Độ, nơi có ba cây cột đá và 64 chiếc đĩa vàng khác kích cỡ. Các linh mục ở đền thờ phải chuyển toàn bộ các đĩa từ một cột sang cột khác, tuân theo quy tắc không bao giờ đặt đĩa lớn hơn lên đĩa nhỏ hơn. Truyền thuyết nói rằng, khi toàn bộ các đĩa được chuyển đến cột mới, thế giới sẽ kết thúc.

Édouard Lucas đã lấy cảm hứng từ truyền thuyết này để tạo ra bài toán tháp Hà Nội, đặt tên theo tên thủ đô của Việt Nam vào thời đó.

1.2. Mô tả bài toán Tháp Hà Nội

Bài toán tháp Hà Nội được mô tả cụ thể như sau:

Cho 3 cây đinh A, B và C và n chiếc đĩa có kích thước khác nhau. Ban đầu, các chiếc đinh được đặt ở cột A, theo thứ tự lớn nhất ở dưới cùng, nhỏ dần khi đến chiếc đĩa cuối cùng.

Mục tiêu của bài toán là di chuyển toàn bộ chiếc đĩa từ chiếc đinh A sang chiếc đinh C, sử dụng chiếc đinh B làm trung gian, tuân thủ các quy tắc sau:

• Chỉ có 3 đinh để di chuyển, không có chiếc đinh thứ 4 nào.
• Một lần chỉ được di chuyển một đĩa, và chỉ được di chuyển chiếc đĩa nằm trên đỉnh của đinh, không được di chuyển đĩa nằm giữa.
• Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn, tuy nhiên không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất.

2. Cấu Trúc bài toán tháp Hà Nội

2.1. Các yếu tố trong bài toán tháp Hà Nội

Bài toán tháp Hà Nội gồm hai yếu tố cơ bản: đĩa và cây đinh [cột]. Dưới đây là chi tiết về từng yếu tố:

• Đĩa

Số lượng: Bài toán có n đĩa, số lượng đĩa có thể thay đổi tùy thuộc vào phiên bản cụ thể của bài toán. Thông thường, để dễ hình dung và giải quyết bài toán, con số lý tưởng là 3.

Kích thước: Mỗi đĩa có một kích thước duy nhất và không đĩa nào giống đĩa nào khác. Đĩa được sắp xếp theo thứ tự giảm dần từ trên xuống dưới trên cây đinh ban đầu.

Di Chuyển: Chỉ có một đĩa có thể được di chuyển tại một thời điểm, và đĩa chỉ có thể được đặt lên một đĩa lớn hơn hoặc một cây đinh trống.

• Đinh [Cột]

Số lượng: Có tổng cộng ba cây đinh, thường được gọi là A, B và C.

Chức Năng: Cây đinh có chức năng giữ đĩa và hỗ trợ việc di chuyển những chiếc đĩa giữa các.

2.2. Quy tắc của bài toán Tower of Hanoi

Dưới đây là quy tắc của bài toán:

1. Di chuyển một đĩa: Trong một lần di chuyển, chỉ được phép di chuyển duy nhất chiếc đĩa trên cùng của mỗi đinh.
2. Thứ tự các đĩa: Không được đặt đĩa có kích thước lớn hơn lên trên đĩa có kích thướng nhỏ hơn.

2.3. Mục tiêu của bài toán Tower of Hanoi

Bài toán tháp Hà Nội chủ yếu dựa vào sự di chuyển hợp lệ của các đĩa giữa các cây đinh, đồng thời tuân thủ các quy tắc, để đạt được mục tiêu di chuyển tất cả các đĩa từ cây đinh A sang cây đinh C.

3. Hướng giải bài toán bài toán tháp Hà Nội

Để giải được bài toán này, chúng ta có ba bước :

1. Di chuyển n-1 đĩa ở trên cùng ở chiếc đinh ban đầu đến chiếc đinh trung gian.
2. Di chuyển chiếc đĩa lớn nhất ở dưới cùng của chiếc đinh đầu tiên đến chiếc đinh đích
3. Di chuyển n-1 chiếc đĩa ở đinh trung gian sang đinh đích

Dưới đây là cách giải bài toán tháp Hà Nội với số đĩa là hai.

Với số đĩa là 2, công việc của chúng ta rất đơn giản, là di chuyển từng chiếc đĩa một với các bước giải đã nêu trên.

Vậy, với số đĩa lớn hơn 2, làm thế nào để có thể chuyển n-1 chiếc đĩa sang chiếc đinh trung gian.

Từ hình ảnh trên, vấn đề của chúng ta là cần di chuyển cả 2 chiếc đĩa trên cùng ở chiếc đinh A sang chiếc đinh B. Để có thể di chuyển 2 chiếc đinh này từ A sang B, ta sử dụng lại bài toán đã làm ở trường hợp 2 chiếc đĩa, khi đó, chúng ta có :

• Di chuyển chiếc đĩa trên cùng ở đinh A sang đinh C
• Di chuyển chiếc đĩa thứ hai sang cột B
• Di chuyển chiếc đĩa ở cột C, là chiếc đĩa nhỏ nhất, sang cột B
  Khi số lượng đĩa lớn hơn, chung ta cần chia nhỏ bài toán

Các bước tiếp theo diễn ra như sau :

• Di chuyển chiếc đĩa cuối cùng ở đinh A sang đinh C
• Di chuyển chiếc đĩa trên cùng ở đinh B sang đinh A
• Di chuyển chiếc đĩa còn lại ở đinh B sang đinh C
• Cuối cùng, di chuyển chiếc đinh nhỏ nhất ở đinh A sang đinh C
  Cách giải còn lại với trường hợp số đĩa bằng 3

Giải quyết bài toán lớn bằng một bài toán nhỏ hơn là biểu hiện rất rõ ràng cho việc chúng ta có thể xử lý bài toán này bằng đệ quy.

Chúng ta sẽ đi sâu hơn về cách giải bài toán tháp Hà Nội ở chương tiếp theo.

4. Cách giải quyết bài toán tháp Hà Nội bằng Đệ Quy

Sau khi biết được các vấn đề và mục tiêu của bài toán, chúng ta có thể phân tích và xử lý bài toán tháp Hà Nội bằng phương pháp đệ quy.

Cách làm đệ quy yêu cầu chúng ta xác định được 2 thứ, base case và recursion case.

4.1. Base case của bài toán tháp Hà Nội

Với bài toán này, base case chính là trường hợp mà ta di chuyển trực tiếp chiếc đĩa từ đinh ban đầu đến chiếc đinh đích, mà không cần sử dụng đến chiếc đinh trung gian.

Để có thể làm được điều này, số lượng đĩa mà chúng ta cần di chuyển là một chiếc, ứng với n = 1.

Sau đây là đoạn mã viết bằng C++ của base case:

void TowerOfHanoi[int numberOfDisks, char sourcePeg, char auxiliaryPeg, char targetPeg] {
    if [numberOfDisks == 1] {
        cout