BLOG CHIA SẺ

[Chia sẻ] Xếp hạng độ khó 10 bài toán kinh điển của sinh viên IT

11/11/2024 sachgayxoan.com

Hi các bạn,

Nếu các bạn đã/đang là sinh viên IT, trong những năm học các môn học cơ sở ngành, các bạn sẽ có dịp làm quen với rất nhiều bài toán khác nhau trong lĩnh vực CNTT. Dưới đây là tổng hợp của 10 bài toán kinh điển của sinh viên IT

A. Mức dễ

1. Bài toán tháp Hà Nội (Tower of Hanoi)

Giới thiệu: Đây là bài toán kinh điển về thuật toán cũng như lý thuyết lập trình mà gần như chắc chắn sinh viên IT nào cũng đã từng học qua. Bài toán là ví dụ kinh điển về việc áp dụng phương pháp đệ quy để giải quyết vấn đề

Mô tả: Di chuyển các đĩa từ cọc A sang cọc C thông qua cọc B theo quy tắc không đặt đĩa lớn lên trên đĩa nhỏ hơn.

Lý do xếp hạng: Bài toán này yêu cầu hiểu biết cơ bản về đệ quy, nhưng với các quy tắc rõ ràng và dễ áp dụng. Thuật toán đơn giản và có thể được giải thích dễ dàng qua cây đệ quy.

2. Bài toán Fibonacci

Giới thiệu: Đây là một bài toán nổi tiếng trong toán học và lập trình. Dãy Fibonacci được định nghĩa là một dãy số mà mỗi số trong dãy là tổng của hai số liền trước nó, với 2 số đầu tiên trong dãy là 0 và 1

Mô tả: Tính số Fibonacci thứ n, với công thức F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1.

Lý do: Bài toán cơ bản về đệ quy và quy hoạch động. Hầu hết các sinh viên IT năm 1 năm 2 sẽ đều được làm quen với bài toán này và phần lớn sẽ đều được dạy cách dùng phương pháp đệ quy để giải quyết. Khá là đơn giản, tương tự như bài toán Tháp Hà Nội. Tuy nhiên, 1 điểm khác biệt so với Tháp hà Nội, đó là bài toán Fibonacci là dịp để chúng ta thấy được nhược điểm về thời gian cũng như bộ nhớ của đệ quy, từ đó giới thiệu về phương pháp quy hoạch động – 1 phương pháp tối ưu hóa quan trọng mà các sinh viên IT cần nắm chắc

3. Bài toán số đối xứng

Giới thiệu: Palindrome Number – số đối xứng là một số mà khi viết ngược lại vẫn giữ nguyên giá trị. Ví dụ, các số 121, 1331, hay 9889 đều là những số đối xứng. Mở rộng ra thì 1 palindrome là một từ, số, cụm từ, hay chuỗi các biểu tượng mà khi đọc từ trái sang phải cũng giống như đọc từ phải sang trái.

Mô tả: Kiểm tra xem một chuỗi hoặc số có đối xứng (palindrome) hay không.

Lý do: Đây là 1 trong các bài toán lập trình cơ bản dành cho sinh viên IT. Để giải quyết bài toán, ta chỉ cần kiểm tra các phần tử của số hoặc chuỗi từ đầu đến cuối mà không yêu cầu bất kỳ thuật toán phức tạp nào. Bài toán là dịp để sinh viên thực hành thao tác cơ bản trên số hay chuỗi ký tự. Bài toán này được xếp vào mức dễ vì không yêu cầu nhiều về tư duy logic mà chỉ đơn giản là kiểm tra kỹ năng lập trình cơ bản

4. Bài toán sắp xếp

Giới thiệu: 1 bài toán kinh điển của 1 môn học kinh điển của sinh viên IT – cấu trúc dữ liệu và giải thuật

Mô tả: Sắp xếp một mảng theo thứ tự tăng dần hoặc giảm dần. Có rất nhiều các thuật toán sắp xếp khác nhau, từ đơn giản cho đến phức tạp. 1 vài trong số đó là những cái tên rất nổi tiếng mà gần như sinh viên IT nào cũng biết, như là Bubble sort (sắp xếp nổi bọt), insert sort (sắp xếp chèn) hay Quick sort (sắp xếp nhanh). Khi tìm hiểu về bài toán sắp xếp, sinh viên không chỉ được làm quen với các thuật toán sắp xếp, mà còn được làm quen với khái niệm độ phức tạp của thuật toán – thứ giúp chúng ta đánh giá được xem một thuật toán có tốt, có tối ưu hay không

Lý do: Các thuật toán sắp xếp, dù là với độ phức tạp nào đi nữa, thì cũng không quá khó để các bạn sinh viên năm 1, năm 2 có thể hiểu và tự thực hiện lại. Các thuật toán sắp xếp là những ví dụ tuyệt vời để sinh viên hiểu về cách xây dựng một thuật toán, cũng như thực hành về vòng lặp – kiến thức cơ bản của bất kì 1 ngôn ngữ lập trình nào

B. Mức trung bình

1. Bài toán ma phương (Magic Square)

Giới thiệu: Đây là 1 bài toán cổ điển liên quan đến việc sắp xếp các số vào 1 ma trận vuông sao cho tổng của các số trong mỗi hàng, mỗi cột và 2 đường chéo chính đều bằng nhau

Mô tả: Một ma phương cấp N (kích thước N x N) là một bảng vuông chứa N^2 số nguyên dương khác nhau (thường là từ 1 đến N^2), sao cho tổng các số trong mỗi hàng, mỗi cột và hai đường chéo chính đều bằng một số không đổi, gọi là hằng số ma phương (magic constant).

Lý do: Mặc dù không quá phức tạp về mặt thuật toán, bài toán này yêu cầu cách xử lý ma trận một cách chính xác và tuần tự để đảm bảo các tính chất của ma phương.

2. Bài toán tìm đường đi ngắn nhất

Giới thiệu: Đây là một trong những bài toán cơ bản và quan trọng trong lý thuyết đồ thị và các ứng dụng thực tiễn. Mục tiêu của bài toán là tìm con đường ngắn nhất giữa hai đỉnh trong một đồ thị sao cho tổng trọng số của các cạnh trên đường đi là nhỏ nhất.

Mô tả: Đầu vào

Một đồ thị có hướng hoặc đồ thị vô hướng, thường được biểu diễn dưới dạng tập hợp các đỉnh (vertices) và các cạnh (edges).

Các cạnh có thể được gán trọng số (weight), đại diện cho độ dài hoặc chi phí để đi qua cạnh đó.

Một đỉnh bắt đầu (source) và một đỉnh đích (destination).

Đầu ra: Một con đường từ đỉnh bắt đầu đến đỉnh đích sao cho tổng trọng số của các cạnh trên đường đi là nhỏ nhất.

Lý do: Bài toán yêu cầu hiểu rõ các thuật toán tìm đường trong đồ thị và áp dụng chúng một cách hiệu quả. Các thuật toán như Dijkstra hay Bellman-Ford khá phổ biến và dễ hiểu thường được áp dụng để giải quyết bài toán này

C. Mức khó

1. Bài toán 8 quân hậu (8-Queens problem)

Giới thiệu: Đây là 1 bài toán kinh điển trong lý thuyết tổ hợp, đồng thời được sử dụng rất nhiều trong các môn học lập trình hay thuật toán, như là 1 bài toán nâng cao. Bài toán yêu cầu đặt 8 quân hậu lên 1 bàn cờ vua tiêu chuẩn (kích thước 8×8) sao cho không có 2 quân hậu nào ăn được nhau

Mô tả: Bài toán mình vừa nói ở trên là trường hợp riêng phổ biến nhất, nổi tiếng nhất của 1 bài toán tổng quát hơn – bài toán N quân hậu: Đặt N quân hậu lên bàn cờ NxN sao cho không có quân hậu nào ăn nhau. Dành cho những bạn nào chưa biết, 1 quân hậu có thể ăn bất kì 1 quân nào khác nếu chúng năm trên cùng 1 hàng, 1 cột hoặc 1 đường chéo. Bài toán nổi tiếng này có khá nhiều biến thể, bao gồm:

Thay thế quân hậu bằng các quân cờ khác: Đặt các quân cờ khác nhau (hậu, xe, mã, tượng) sao cho không quân nào có thể ăn được quân khác

Thay thế bảng vuông bằng bảng chữ nhật: Thay vì một bàn cờ N x N, bài toán được mở rộng ra với một bàn cờ có kích thước N x M, và yêu cầu đặt quân hậu sao cho không quân nào ăn được quân khác.

Thêm ràng buộc bổ sung: Thêm các ràng buộc khác, chẳng hạn như các ô nhất định bị cấm không được đặt quân, hoặc phải đặt các quân hậu tại các vị trí đã cho trước.

Lý do: Đây là bài toán điển hình minh họa cho thuật toán quay lui (backtracking) và tổ hợp. Bản thân backtracking là thuật toán phát biểu thì dễ nhưng áp dụng hiệu quả thì khó. Việc tìm kiếm đáp án sẽ trở nên phức tạp hơn khi N tăng. Người ta cũng có thể dùng 1 vài các phương pháp khác, ví dụ như là Branch and Bound (Nhánh và Giới hạn): Giống với phương pháp quay lui nhưng áp dụng các chiến lược tối ưu hóa để giảm số lượng trường hợp cần phải kiểm tra. Tuy nhiên dù là với phương pháp nào đi nữa thì thời gian giải bài toán cũng tăng theo cấp số nhân khi N tăng lên.

2. Bài toán tô màu đồ thị (Map Coloring Problem)

Giới thiệu: Đây là bài toán trong lý thuyết đồ thị và tổ hợp. Mục tiêu của bài toán là tô màu các vùng (quốc gia, tỉnh, bang, v.v.) của một bản đồ sao cho không có hai vùng kề nhau nào được tô cùng một màu.

Mô tả:

Đầu vào: Một bản đồ bao gồm nhiều vùng (tức là các khu vực địa lý khác nhau), trong đó mỗi vùng kề nhau có một ranh giới chung.

Yêu cầu: Tìm một cách tô màu sao cho:

Mỗi vùng được tô một màu.

Hai vùng kề nhau không được tô cùng một màu (các vùng kề nhau có nghĩa là chúng có một ranh giới chung, không phải chỉ chạm nhau tại một điểm).

Mục tiêu là tìm ra số lượng màu nhỏ nhất sao cho tất cả các vùng trên bản đồ đều được tô màu hợp lệ theo quy tắc trên.

Lý do: Có rất nhiều cách khác nhau để có thể giải bài toán này, bao gồm thuật toán quay lui, thuật toán tham lam hay tìm kiếm đệ quy. Tuy nhiên mỗi thuật toán lại có những nhược điểm và hạn chế nhất định. Thách thức lớn nhất của bài toán này không đến từ việc sẽ rất mất thời gian để tìm ra đáp án với những trường hợp kích thước đồ thị lớn

3. Bài toán Người Bán Hàng (Traveling Salesman Problem – TSP)

Giới thiệu: Tìm lộ trình ngắn nhất qua tất cả các thành phố sao cho không đi qua một thành phố hai lần.

Mô tả:

Cho một tập hợp các thành phố và khoảng cách giữa mỗi cặp thành phố.

Người đưa thư cần xuất phát từ một thành phố, đi qua tất cả các thành phố còn lại đúng một lần, và sau đó quay trở lại thành phố xuất phát.

Yêu cầu: Tìm lộ trình sao cho tổng khoảng cách đi được là ngắn nhất.

Lý do: Đây là bài toán NP-hard, đòi hỏi giải pháp heuristic hoặc quy hoạch động cho các trường hợp lớn. Việc tìm giải pháp chính xác rất khó và phức tạp khi số thành phố lớn.

4. Sudoku

Giới thiệu: Sudoku là một trò chơi câu đố logic trên bảng có kích thước 9×9 ô, chia thành 9 vùng con 3×3. Nhiệm vụ của người chơi là điền các số từ 1 đến 9 vào các ô trống sao cho mỗi hàng, mỗi cột, và mỗi vùng con 3×3 đều chứa đủ các số từ 1 đến 9 mà không trùng lặp. Một số ô đã được điền trước làm manh mối, và mục tiêu là hoàn thành toàn bộ bảng theo các quy tắc trên. Sudoku có một lời giải duy nhất và độ khó thay đổi tùy theo số ô đã điền sẵn.

Lý do: Sudoku là một bài toán khó trong lập trình vì nó thuộc loại bài toán tìm kiếm ràng buộc, đòi hỏi việc điền các số phải thỏa mãn nhiều điều kiện đồng thời. Số lượng hoán vị lớn khiến không gian tìm kiếm trở nên phức tạp, và việc sử dụng thuật toán backtracking có thể tốn nhiều tài nguyên. Độ khó tăng lên khi số manh mối ít và việc đảm bảo tính duy nhất của lời giải cũng là một thách thức lớn trong việc lập trình giải Sudoku.

Cart