C++ algorithm: Những thuật toán cơ bản trong C++
Thuật toán là một chuỗi các bước có trình tự rõ ràng để giải quyết một vấn đề. Trong lập trình C++, thuật toán đóng vai trò quan trọng trong việc phát triển phần mềm hiệu quả và tối ưu. Do đó, việc hiểu được các c++ algorithm cơ bản là nền tảng cho bất kỳ ai muốn bước vào thế giới lập trình.
Khái quát về thuật toán C++
C++ là một ngôn ngữ lập trình hướng đối tượng và được sử dụng rộng rãi trong các ứng dụng khoa học máy tính, game và hệ thống nhúng. Với sự phát triển của công nghệ, việc tối ưu hóa và xử lý dữ liệu trở thành một yếu tố quan trọng trong lập trình và đây chính là lý do tại sao thuật toán lại trở nên cực kỳ quan trọng trong lập trình C++.
Trong C++, thuật toán được sử dụng để giải quyết các vấn đề liên quan đến xử lý dữ liệu, từ việc sắp xếp các phần tử trong một danh sách đến việc tìm kiếm các giá trị trong một tập hợp dữ liệu lớn. Vì vậy, hiểu và áp dụng các thuật toán cơ bản là điều cần thiết đối với một lập trình viên C++.
Khái niệm cơ bản về cấu trúc dữ liệu trong C++
Trước khi tìm hiểu về thuật toán, chúng ta cần nắm rõ khái niệm cấu trúc dữ liệu. Cấu trúc dữ liệu là cách thức tổ chức và sắp xếp dữ liệu trong bộ nhớ máy tính. Trong C++, có nhiều loại cấu trúc dữ liệu khác nhau, mỗi loại có ưu điểm và ứng dụng riêng. Dưới đây là những cấu trúc dữ liệu mà bất kỳ lập trình viên nào cũng phải biết:
Mảng (Array)
Mảng là một tập hợp các phần tử có cùng kiểu dữ liệu. Mỗi phần tử có một chỉ số duy nhất để truy cập và thay đổi giá trị của nó.
Array được sử dụng để lưu trữ các dữ liệu có cùng loại và kích thước cố định. Điều này giúp việc truy xuất và xử lý dữ liệu trở nên dễ dàng và nhanh chóng.
Ví dụ: Mảng số nguyên gồm 5 phần tử.
| Chỉ số | Giá trị |
|---|---|
| 0 | 10 |
| 1 | 5 |
| 2 | 7 |
| 3 | 3 |
| 4 | 9 |
>>> Xem thêm: Solve Reverse Array with the best solution
Danh sách liên kết (Linked List)
Linked List là một tập hợp các phần tử được liên kết với nhau thông qua các con trỏ, mỗi phần tử trong danh sách chứa dữ liệu và một con trỏ đến phần tử tiếp theo trong danh sách. Điều này cho phép lập trình viên thêm, xóa và sắp xếp các phần tử trong danh sách một cách linh hoạt.
Cây (Tree)
Tree là một cấu trúc dữ liệu phân cấp, gồm một nút gốc và các nút con. Mỗi nút có thể có nhiều nút con khác và chỉ có một nút cha. Cây được sử dụng để lưu trữ dữ liệu theo cấu trúc phân cấp, ví dụ như cây gia phả, cây thư mục trên máy tính.
Đồ thị (Graph)
Graph là một tập hợp các đỉnh và các cạnh nối chúng. Điều này cho phép biểu diễn các mối quan hệ giữa các đối tượng trong thế giới thực. Đồ thị được sử dụng trong nhiều lĩnh vực như mạng máy tính, kế hoạch dự án, tối ưu hóa đường đi.
Bảng băm (Hash Table)
Hash Table là một cấu trúc dữ liệu sử dụng hàm băm để lưu trữ và truy xuất dữ liệu nhanh chóng. Hàm băm sẽ chuyển đổi khóa của dữ liệu thành một chỉ số duy nhất và lưu trữ dữ liệu tại vị trí đó trong bảng. Điều này giúp việc truy xuất dữ liệu trở nên nhanh chóng và hiệu quả.
Ví dụ: Bảng băm có 5 khóa và 5 giá trị tương ứng.
| Khóa | Giá trị |
|---|---|
| 1 | A |
| 2 | B |
| 3 | C |
| 4 | D |
| 5 | E |
Hàng đợi (Queue)
Queue là một cấu trúc dữ liệu theo nguyên tắc vào trước, ra trước (FIFO – First In First Out). Các phần tử được thêm vào hàng đợi sẽ được lấy ra theo thứ tự chúng được thêm vào. Hàng đợi được sử dụng trong nhiều ứng dụng như xử lý tác vụ đồng bộ, quản lý tiến trình.
Ví dụ: Hàng đợi có 5 phần tử và phần tử đầu tiên được lấy ra trước.
Ngăn xếp (Stack)
Stack là một cấu trúc dữ liệu theo nguyên tắc vào sau, ra trước (FILO – First In Last Out). Các phần tử được thêm vào ngăn xếp sẽ được lấy ra theo thứ tự ngược lại so với thứ tự chúng được thêm vào. Ngăn xếp được sử dụng trong nhiều ứng dụng như xử lý biểu thức toán học, gọi hàm.
Ví dụ: Ngăn xếp có 5 phần tử và phần tử cuối cùng được lấy ra trước.
Nhiều vị trí tuyển dụng C++ đãi ngộ tốt trên TopDev
Thuật toán sắp xếp trong C++
Thuật toán sắp xếp sắp xếp các phần tử của một tập hợp theo một trật tự xác định. Các thuật toán sắp xếp phổ biến trong C++ bao gồm: sắp xếp nổi bọt, sắp xếp chọn, sắp xếp chèn, sắp xếp nhanh, sắp xếp trộn.
Sắp xếp nổi bọt (Bubble Sort)
Bubble Sort nổi bọt là thuật toán sắp xếp đơn giản nhất trong các thuật toán sắp xếp. Thuật toán này hoạt động bằng cách so sánh và hoán đổi các phần tử liền kề nhiều lần cho đến khi danh sách được sắp xếp.
Ý tưởng:
- Lặp qua từng phần tử trong danh sách.
- So sánh phần tử hiện tại với phần tử tiếp theo.
- Nếu phần tử hiện tại lớn hơn phần tử tiếp theo, hoán đổi chúng.
- Lặp lại quá trình cho đến khi danh sách được sắp xếp.
Độ phức tạp: O(n^2)
Ví dụ: Sắp xếp mảng số nguyên theo thứ tự tăng dần.
| Bước | Mảng trước khi sắp xếp | Mảng sau khi sắp xếp |
|---|---|---|
| 1 | [5, 3, 8, 2, 1] | [3, 5, 2, 1, 8] |
| 2 | [3, 5, 2, 1, 8] | [3, 2, 1, 5, 8] |
| 3 | [3, 2, 1, 5, 8] | [2, 1, 3, 5, 8] |
| 4 | [2, 1, 3, 5, 8] | [1, 2, 3, 5, 8] |
Sắp xếp chọn (Selection Sort)
Selection Sort là thuật toán sắp xếp bằng cách tìm kiếm phần tử nhỏ nhất trong danh sách và đưa nó về vị trí đầu tiên sau đó, tìm kiếm phần tử nhỏ nhất trong danh sách còn lại và đưa nó về vị trí thứ hai. Quá trình này được lặp lại cho đến khi danh sách được sắp xếp.
Ý tưởng:
- Lặp qua từng phần tử trong danh sách.
- Tìm kiếm phần tử nhỏ nhất trong danh sách còn lại.
- Đưa phần tử nhỏ nhất về vị trí đầu tiên của danh sách.
- Lặp lại quá trình cho đến khi danh sách được sắp xếp.
Độ phức tạp: O(n^2)
Ví dụ: Sắp xếp mảng số nguyên theo thứ tự tăng dần.
| Bước | Mảng trước khi sắp xếp | Mảng sau khi sắp xếp |
|---|---|---|
| 1 | [5, 3, 8, 2, 1] | [1, 3, 8, 2, 5] |
| 2 | [1, 3, 8, 2, 5] | [1, 2, 8, 3, 5] |
| 3 | [1, 2, 8, 3, 5] | [1, 2, 3, 8, 5] |
| 4 | [1, 2, 3, 8, 5] | [1, 2, 3, 5, 8] |
Sắp xếp chèn (Insertion Sort)
Insertion Sort là thuật toán sắp xếp bằng cách chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp. Ban đầu, phần đã sắp xếp chỉ có một phần tử đầu tiên của danh sách. Sau đó, bạn lặp qua từng phần tử trong phần chưa sắp xếp và chèn nó vào đúng vị trí trong phần đã sắp xếp.
Ý tưởng:
- Chia danh sách thành hai phần: phần đã sắp xếp và phần chưa sắp xếp.
- Lặp qua từng phần tử trong phần chưa sắp xếp.
- Chèn phần tử hiện tại vào đúng vị trí trong phần đã sắp xếp.
- Lặp lại quá trình cho đến khi danh sách được sắp xếp.
Độ phức tạp: O(n^2)
Ví dụ: Sắp xếp mảng số nguyên theo thứ tự tăng dần.
| Bước | Mảng trước khi sắp xếp | Mảng sau khi sắp xếp |
|---|---|---|
| 1 | [5, 3, 8, 2, 1] | [5, 3, 8, 2, 1] |
| 2 | [5, 3, 8, 2, 1] | [3, 5, 8, 2, 1] |
| 3 | [3, 5, 8, 2, 1] | [3, 5, 8, 2, 1] |
| 4 | [3, 5, 8, 2, 1] | [2, 3, 5, 8, 1] |
| 5 | [2, 3, 5, 8, 1] | [1, 2, 3, 5, 8] |
Sắp xếp nhanh (Quick Sort)
Quick Sort là thuật toán sắp xếp đệ quy dựa trên nguyên tắc chia để trị. Thuật toán này hoạt động bằng cách chọn một phần tử gọi là “pivot” và chia danh sách thành hai phần: các phần tử nhỏ hơn pivot và các phần tử lớn hơn pivot. Sau đó, đệ quy sắp xếp các phần tử nhỏ hơn và lớn hơn pivot cho đến khi danh sách được sắp xếp.
Ý tưởng:
- Chọn một phần tử làm pivot.
- Chia danh sách thành hai phần: các phần tử nhỏ hơn pivot và các phần tử lớn hơn pivot.
- Đệ quy sắp xếp các phần tử nhỏ hơn và lớn hơn pivot.
- Kết hợp các phần tử đã sắp xếp với pivot để tạo thành danh sách đã sắp xếp.
Độ phức tạp: O(nlogn)
Ví dụ: Sắp xếp mảng số nguyên theo thứ tự tăng dần.
| Bước | Mảng trước khi sắp xếp | Mảng sau khi sắp xếp |
|---|---|---|
| 1 | [5, 3, 8, 2, 1] | [1, 3, 2, 5, 8] |
| 2 | [1, 3, 2] | [1, 2, 3] |
| 3 | [5, 8] | [5, 8] |
Sắp xếp trộn (Merge Sort)
Merge Sort là thuật toán sắp xếp đệ quy dựa trên nguyên tắc chia để trị. Thuật toán này hoạt động bằng cách chia danh sách thành hai phần bằng nhau, đệ quy sắp xếp từng phần và kết hợp chúng lại để tạo ra danh sách đã sắp xếp.
Ý tưởng:
- Chia danh sách thành hai phần bằng nhau.
- Đệ quy sắp xếp từng phần.
- Kết hợp các phần đã sắp xếp để tạo ra danh sách đã sắp xếp.
Độ phức tạp: O(nlogn)
Ví dụ: Sắp xếp mảng số nguyên theo thứ tự tăng dần.
| Bước | Mảng trước khi sắp xếp | Mảng sau khi sắp xếp |
|---|---|---|
| 1 | [5, 3, 8, 2, 1] | [1, 2, 3, 5, 8] |
| 2 | [5, 3] | [3, 5] |
| 3 | [8, 2, 1] | [1, 2, 8] |
| 4 | [3, 5] | [3, 5] |
| 5 | [1, 2, 8] | [1, 2, 8] |
Xem thêm: Tổng hợp các thuật toán sắp xếp c++ tại đây
Thuật toán tìm kiếm trong C++
Thuật toán tìm kiếm là thuật toán tìm kiếm một giá trị cụ thể trong một tập hợp. Các thuật toán tìm kiếm trong C++ phổ biến bao gồm: tìm kiếm tuần tự, tìm kiếm nhị phân.
Tìm kiếm tuần tự (Linear Search)
Linear Search là thuật toán tìm kiếm bằng cách lặp qua từng phần tử trong danh sách cho đến khi tìm thấy giá trị cần tìm hoặc hết danh sách.
Ý tưởng:
- Lặp qua từng phần tử trong danh sách.
- So sánh phần tử hiện tại với giá trị cần tìm.
- Nếu phần tử hiện tại bằng giá trị cần tìm, trả về vị trí của phần tử.
- Nếu hết danh sách mà không tìm thấy giá trị cần tìm, trả về -1.
Độ phức tạp: O(n)
Ví dụ: Tìm kiếm giá trị 5 trong mảng số nguyên.
| Bước | Mảng | Giá trị cần tìm | Kết quả |
|---|---|---|---|
| 1 | [3, 8, 2, 5, 1] | 5 | 3 |
| 2 | [3, 8, 2, 5, 1] | 5 | 4 |
Tìm kiếm nhị phân (Binary Search)
Tìm kiếm nhị phân là thuật toán tìm kiếm bằng cách chia đôi danh sách và so sánh giá trị cần tìm với phần tử ở giữa danh sách. Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, tiếp tục tìm kiếm trong nửa đầu của danh sách. Ngược lại, tìm kiếm trong nửa sau của danh sách.
Ý tưởng:
- Chia đôi danh sách.
- So sánh giá trị cần tìm với phần tử ở giữa danh sách.
- Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, tiếp tục tìm kiếm trong nửa đầu của danh sách.
- Ngược lại, tìm kiếm trong nửa sau của danh sách.
- Lặp lại quá trình cho đến khi tìm thấy giá trị cần tìm hoặc hết danh sách.
Độ phức tạp: O(logn)
Ví dụ: Tìm kiếm giá trị 5 trong mảng số nguyên đã được sắp xếp.
| Bước | Mảng | Giá trị cần tìm | Kết quả |
|---|---|---|---|
| 1 | [1, 2, 3, 5, 8] | 5 | 3 |
| 2 | [1, 2, 3] | 5 | -1 |
Thuật toán đệ quy trong C++
Thuật toán đệ quy là thuật toán dựa trên nguyên tắc chia để trị. Nó hoạt động bằng cách gọi lại chính nó với các bài toán con nhỏ hơn cho đến khi đạt được kết quả cuối cùng.
Ví dụ: Tính giai thừa bằng đệ quy
Giai thừa của một số nguyên dương n được định nghĩa là tích của các số từ 1 đến n. Ví dụ: 5! = 1 2 3 4 5 = 120.
Ý tưởng:
- Nếu n = 0 hoặc n = 1, trả về 1.
- Ngược lại, tính giai thừa của n – 1 và nhân với n.
Độ phức tạp: O(n)
Ví dụ: Tính giai thừa của 5.
| Bước | Giá trị n | Kết quả |
|---|---|---|
| 1 | 5 | 120 |
| 2 | 4 | 24 |
| 3 | 3 | 6 |
| 4 | 2 | 2 |
| 5 | 1 | 1 |
Thuật toán tham lam trong C++
Thuật toán tham lam là thuật toán tìm kiếm giải pháp tốt nhất tại mỗi bước để đạt được kết quả cuối cùng tốt nhất. Nó không đảm bảo tìm ra giải pháp tối ưu nhưng thường cho kết quả gần với giải pháp tối ưu.
Ví dụ: Tìm số tiền ít nhất để trả lại
Giả sử bạn có các loại tiền sau: 1 đô la, 5 đô la, 10 đô la, 20 đô la, 50 đô la, 100 đô la. Hãy tính số tiền ít nhất cần trả lại khi khách hàng thanh toán một khoản tiền bất kỳ.
Ý tưởng:
- Lặp qua từng loại tiền theo thứ tự lớn đến nhỏ.
- Trừ số tiền cần trả lại với số tiền hiện có.
- Đếm số lượng tiền đã trừ.
- Lặp lại cho đến khi số tiền cần trả lại bằng 0.
Độ phức tạp: O(n)
Ví dụ: Trả lại 75 đô la.
| Bước | Số tiền cần trả lại | Số tiền hiện có | Số lượng tiền đã trừ |
|---|---|---|---|
| 1 | 75 | 100 | 1 |
| 2 | 25 | 50 | 1 |
| 3 | 5 | 20 | 1 |
Thuật toán chia để trị trong C++
Thuật toán chia để trị là thuật toán dựa trên nguyên tắc chia bài toán thành các bài toán con nhỏ hơn, giải quyết từng bài toán con và kết hợp kết quả để đạt được kết quả cuối cùng.
Ví dụ: Tìm số lớn nhất trong mảng số nguyên
Ý tưởng:
- Chia mảng thành hai nửa.
- Đệ quy tìm số lớn nhất trong mỗi nửa.
- So sánh số lớn nhất của hai nửa với nhau và trả về số lớn hơn.
Độ phức tạp: O(nlogn)
Ví dụ: Tìm số lớn nhất trong mảng [5, 8, 2, 1, 9].
| Bước | Mảng | Số lớn nhất |
|---|---|---|
| 1 | [5, 8, 2] | 8 |
| 2 | [5] | 5 |
| 3 | [8, 2] | 8 |
| 4 | [1, 9] | 9 |
| 5 | [8, 9] | 9 |
Thuật toán động trong C++
Thuật toán động là thuật toán tối ưu hóa bằng cách lưu trữ và sử dụng lại các kết quả tính toán trước đó.
Ví dụ: Tìm số Fibonacci thứ n
Dãy Fibonacci là dãy số bắt đầu từ 0 và 1, các số tiếp theo được tính bằng cách cộng hai số trước đó. Ví dụ: 0, 1, 1, 2, 3, 5, 8, …
Ý tưởng:
- Sử dụng một mảng để lưu trữ các số Fibonacci đã tính toán.
- Nếu số Fibonacci thứ n đã được tính toán trước đó, trả về giá trị đã tính.
- Ngược lại, tính số Fibonacci thứ n bằng cách cộng hai số Fibonacci trước đó và lưu vào mảng.
Độ phức tạp: O(n)
Ví dụ: Tính số Fibonacci thứ 6.
| Bước | Số Fibonacci đã tính | Kết quả |
|---|---|---|
| 1 | [0, 1] | 8 |
| 2 | [0, 1, 1] | 8 |
| 3 | [0, 1, 1, 2] | 8 |
| 4 | [0, 1, 1, 2, 3] | 8 |
| 5 | [0, 1, 1, 2, 3, 5] | 8 |
Thuật toán đồ thị trong C++
Thuật toán đồ thị là thuật toán dùng để tìm kiếm và xử lý các đồ thị. Các thuật toán đồ thị phổ biến trong C++ bao gồm: Dijkstra, Prim, Kruskal, …
Ví dụ: Thuật toán Dijkstra
Thuật toán Dijkstra được sử dụng để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số dương.
Ý tưởng:
- Khởi tạo một mảng lưu khoảng cách từ đỉnh xuất phát đến các đỉnh khác.
- Khởi tạo một hàng đợi ưu tiên lưu các đỉnh chưa được duyệt theo thứ tự khoảng cách tăng dần.
- Lặp cho đến khi hàng đợi ưu tiên trống:
- Lấy ra đỉnh có khoảng cách nhỏ nhất trong hàng đợi.
- Duyệt qua các đỉnh kề với đỉnh hiện tại và cập nhật khoảng cách nếu có đường đi ngắn hơn.
- Thêm các đỉnh đã duyệt vào mảng lưu khoảng cách.
- Trả về mảng lưu khoảng cách.
Độ phức tạp: O(ElogV) (E là số cạnh, V là số đỉnh)
Ví dụ: Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh khác trong đồ thị sau.
| Bước | Đỉnh được duyệt | Khoảng cách từ A |
|---|---|---|
| 1 | A | 0 |
| 2 | B | 3 |
| 3 | C | 6 |
| 4 | D | 7 |
| 5 | E | 9 |
| 6 | F | 11 |
Ứng dụng của thuật toán trong khoa học máy tính
Thuật toán là một công cụ quan trọng trong khoa học máy tính và có rất nhiều ứng dụng trong thực tế. Dưới đây là một số ví dụ về ứng dụng của thuật toán trong khoa học máy tính.
- Trong lĩnh vực xử lý ảnh, thuật toán được sử dụng để nhận diện khuôn mặt, phân loại ảnh, nén ảnh, …
- Trong lĩnh vực trí tuệ nhân tạo, thuật toán được sử dụng để xây dựng các mô hình học máy và học sâu.
- Trong lĩnh vực tìm kiếm và khai thác dữ liệu, thuật toán được sử dụng để phân tích dữ liệu, dự đoán xu hướng và tìm kiếm thông tin.
- Trong lĩnh vực trò chơi, thuật toán được sử dụng để xây dựng các trò chơi điện tử và trí tuệ nhân tạo để chơi các trò chơi.
- Trong lĩnh vực mạng máy tính, thuật toán được sử dụng để quản lý và tối ưu hóa mạng.
- Trong lĩnh vực tài chính, thuật toán được sử dụng để dự đoán giá cổ phiếu, quản lý rủi ro và tối ưu hóa các giao dịch.
- Trong lĩnh vực y tế, thuật toán được sử dụng để phân tích dữ liệu bệnh nhân, dự đoán kết quả điều trị và phát hiện bệnh.
- Trong lĩnh vực điều khiển tự động, thuật toán được sử dụng để điều khiển các thiết bị và hệ thống tự động.
- Trong lĩnh vực robot, thuật toán được sử dụng để điều khiển và lập kế hoạch cho các robot di chuyển và thực hiện các tác vụ.
- Trong lĩnh vực truyền thông, thuật toán được sử dụng để mã hóa và giải mã thông tin.
Kết luận
Trên đây là một số khái niệm cơ bản về thuật toán trong ngôn ngữ lập trình C++, cùng với các ví dụ và ứng dụng thực tế của chúng. Hiểu và áp dụng tốt các thuật toán sẽ giúp chúng ta giải quyết các vấn đề phức tạp trong khoa học máy tính một cách hiệu quả. Hy vọng bài viết của TopDev đã giúp bạn có cái nhìn tổng quan về thuật toán trong C++ và có những điều chỉnh phù hợp trong công việc của mình.
Bài viết chỉ mang tính chất tham khảo
Nội dung được tổng hợp bởi AI và điều chỉnh bởi Ban Biên tập TopDev
Cập nhật tin tuyển dụng IT lương cao tại TopDev
- B BenQ RD Series – Dòng Màn Hình Lập Trình 4k+ Đầu Tiên Trên Thế Giới
- F Framework nào tốt nhất cho dự án của bạn? – Checklist chi tiết
- K Kinh nghiệm xử lý responsive table hiệu quả
- S Stackoverflow là gì? Bí kíp tận dụng Stack Overflow hiệu quả
- 7 7 kinh nghiệm hữu ích khi làm việc với GIT trong dự án
- B Bài tập Python từ cơ bản đến nâng cao (có lời giải)
- B Bảo mật API là gì? Một số nguyên tắc và kỹ thuật cần biết
- H Hướng dẫn cài đặt và tự học lập trình Python cơ bản từ A-Z
- C Chinh Phục Phân Tích Dữ Liệu Với Pandas Trong Python: Hướng Dẫn Từng Bước
- D Display CSS là gì? Cách khai báo và sử dụng thuộc tính display trong CSS