GIẢI THUẬT
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Cấu trúc dữ liệu & Giải thuật

Danh sách các bài viết trong chuyên mục Cấu trúc dữ liệu & Giải thuật, đây là những bài viết mới nhất được cập nhật trong mục Giải thuật.

Để trở thành một lập trình viên chuyên nghiệp thì đòi hỏi bạn phải có tư duy lập trình vững chắc, hay còn gọi là background vững chắc, vì vậy hầu như các trường cao đẳng và đại học luôn cho học sinh học những ngôn ngữ như C, C++ trước để rèn luyện tư duy của họ.

Khi bạn đã biết về cú pháp và cách sử dụng các ngôn ngữ đó thì bạn phải tìm hiểu thêm về thuật toán và giải thuật, sau đó áp dụng nó để đưa vào bài toán lập trình cụ thể, điều này sẽ được trình bày trong chuỗi bài học này.

Thuật toán là gì? Giải thuật là gì?

Nếu định nghĩa chính xác thì rất là khó hiểu, vì vậy mình dùng lời văn đơn giản cho gần gũi với mọi người nhé.: Thuật toán trong tiếng anh có nghĩa là Algorithms, ngoài ra nó còn được gọi là giải thuật, là tập hợp những bước thực hiện để giải quyết một bài toán cụ thể.

Ví dụ để kiểm tra một số có chia hết cho 2 hay không thì ta sẽ áp dụng vào định nghĩa như sau: Một số chia hết cho 2 là số chẵn, và không chia hết cho 2 là số lẻ.

  • b = c thì P(x) có nghiệm bất kì
  • bc thì P(c) vô nghiệm

Khi viết một giải thuật bạn phải vẽ sơ đồ, hoặc bạn dùng lời văn cũng được, nhưng phải trình bay rõ ràng về input, output, cũng như là quy trình thực hiện.

Ví dụ: thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là các số thực), trong tập hợp các số thực có thể là một bộ các bước sau đây:

Input: a, b, c

Output: nghiệm

Quy trình:

  • Nếu a = 0
    • b = c thì P(x) có nghiệm bất kì
    • b ≠ c thì P(c) vô nghiệm
  • Nếu a ≠ 0
    • P(x) có duy nhất một nghiệm x = (c - b)/a

Trên là mình đưa ra một ví dụ ở trên wikipedia.

Tại sao cần học giải thuật và thuật toán

Để có tư duy lập trình tốt thì bạn phải học thuật toán thật nhiều, code thật nhiều, điều này sẽ giúp bạn phản xạ cực nhanh. Bản thân mình hiện đang làm PHP là chủ yếu, và do trước đây có học qua C, C++ nên khi tìm hiểu PHP mình cảm thấy rất dễ, bởi mình đã có một nền tảng để có thể tìm hiểu bất kì một ngôn ngữ nào khác.

Các bài toán đơn giản khi vào thực tế đôi khi lại rất quan trọng, nó sẽ giúp bạn xử lý cho một công đoạn nào đó trong chương trình của bạn. Như mình khi đang làm với PHP, mình xử lý vòng lặp cần bổ sung một chức năng nào đó với những lần lặp chẵn, tức là các lần thứ 0, 2, 4, 6 ... như vậy là mình sử dụng thuật toán kiểm tra số chẵn để xử lý.

Và để giúp bạn luyện tư duy, luyện khả năng code của mình thì trong chuỗi bài viết này mình sẽ giới thiệu các bài toán hay gặp nhất, hy vọng sẽ giúp ích cho các bạn.

1THUẬT TOÁN CĂN BẢN
1 Thuật toán kiếm tra số nguyên tố
2 Thuật toán tìm ước chung lớn nhất trong C/C++
3 Thuật toán tính lũy thừa nhanh trong C/C++
4 Thuật toán kiểm tra số chẵn hay lẽ
5 Thuật toán kiểm tra năm nhuận
6 Thuật toán kiểm tra số hoàn hảo trong C++
7 Thuật toán kiểm tra số chính phương C++
8 Danh sách liên kết là gì? Sự khác nhau giữa DSLK và mảng
2SẮP XẾP & TÌM KIẾM
9 Sắp xếp và tìm kiếm là gì?
10 Thuật toán tìm kiếm tuyến tính (Linear search)
11 Thụât toán tìm kiếm nhị phân (Binary Search)
12 Thuật toán tìm kiếm nội suy (Interpolation Search)
13 Thuật toán sắp xếp nổi bọt (Bubble Sort)
14 Thuật toán sắp xếp chèn (Insertion Sort)
15 Thuật toán sắp xếp chọn (Selection Sort)
16 Thuật toán sắp xếp trộn (Merge Sort)
17 Thuật toán sắp xếp nhanh (Quick Sort)
3GIẢI THUẬT ĐỆ QUY
18 Hàm đệ quy là gì? Hoạt động ra sao?
19 Đệ quy tuyến tính (Linear Recursion)
20 Đệ quy đuôi (Tail Recursion)
21 Đệ quy nhị phân (Binary Recursion)
22 Đệ quy đa tuyến (Exponential Recursion)
23 Đệ quy lồng (Nested Recursion)
24 Đệ quy tương hỗ (Mutual Recursion)
25 Bài toán tháp Hà Nội: Sử dụng đệ quy để giải
4DANH SÁCH LIÊN KẾT ĐƠN
26 Cấu trúc dữ liệu của danh sách liên kết đơn
27 Tạo Node mới trong danh sách liên kết đơn
28 Chèn Node vào danh sanh liên kết đơn
29 Xóa Node trong danh sách liên kết đơn
30 Tìm kiếm và sắp xếp trong danh sách liên kết đơn
31 Quản lý sinh viên sử dụng danh sách liên kết đơn
32 Bài tập thực hành với danh sách liên kết đơn
5DANH SÁCH LIÊN KẾT ĐÔI
33 Danh sách liên kết đôi là gì? Cấu trúc dữ liệu của nó
34 Tạo Node mới trong danh sách liên kết đôi
35 Duyệt danh sách liên kết đôi
36 Chèn Node vào danh sách liên kết đôi
37 Xóa Node trong danh sách liên kết đôi
38 Tìm kiếm phần tử k trong danh sách liên kết đôi
39 Gộp hai danh sách liên kết đôi
6CẤU TRÚC CÂY
Cây nhị phân
1 Cấu trúc cây nhị phân là gì? Hoạt động ra sao?
2 Thêm Node vào cây nhị phân tìm kiếm
3 Duyệt cây nhị phân tìm kiếm
4 Tìm kiếm Node trên cây nhị phân tìm kiếm
5 Xuất Node con và lá trong cây nhị phân tìm kiếm
6 Tìm Node MAX và MIN trong cây nhị phân tìm kiếm
7 Xóa Node khỏi cây nhị phân tìm kiếm
Cây đỏ đen
8 Cây đỏ đen là gì? Cấu trúc của Red-Black Tree
9 Thêm Node mới vào cây đỏ đen
10 Xóa Node khỏi cây đỏ đen
7NGĂN XẾP STACK
11 Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?
12 Cài đặt Stack bằng danh sách liên kết
13 Cài đặt Stack bằng mảng một chiều
14 Bài tập chuyển đổi cơ số bằng Stack
15 Bài tập kiểm tra số nguyên tố bằng Stack
8HÀNG ĐỢI QUEUE
16 Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue
17 Cài đặt hàng đợi Queue bằng danh sách liên kết
18 Cài đặt hàng đợi Queue bằng mảng một chiều
19 Tìm các số chẵn lẻ bằng Queue và Stack

Bài xem nhiều

Top