Thuật toán là một chuỗi các bước mô tả cách giải quyết vấn đề. Mọi chương trình máy tính kết thúc bằng một kết quả về cơ bản đều dựa trên một Thuật toán. Tuy nhiên, các thuật toán không chỉ giới hạn để sử dụng trong các chương trình máy tính; . Dựa trên cách thức hoạt động của chúng, chúng ta có thể chia Thuật toán thành nhiều loại. Chúng ta hãy xem xét một số trong những điều quan trọng
Các loại thuật toán
Có nhiều loại Thuật toán, nhưng các loại Thuật toán cơ bản là
Bắt đầu khóa học phát triển phần mềm miễn phí của bạn
Phát triển web, ngôn ngữ lập trình, kiểm thử phần mềm và những thứ khác
Gói phát triển phần mềm tất cả trong một[hơn 600 khóa học, hơn 50 dự án]
Giá
Xem khóa học
600+ Khóa học trực tuyến. hơn 50 dự án. Hơn 3000 giờ. Giấy chứng nhận có thể kiểm chứng. Truy cập Trọn đời
4. 6 [84.023 xếp hạng]
1. thuật toán đệ quy
Đây là một trong những Thuật toán thú vị nhất vì nó gọi chính nó với giá trị đầu vào nhỏ hơn mà nó nhận được sau khi giải quyết các đầu vào hiện tại. Nói một cách đơn giản hơn, Đó là một Thuật toán tự gọi lại chính nó cho đến khi vấn đề được giải quyết
Các vấn đề như Tháp Hà Nội hoặc DFS của Đồ thị có thể được giải quyết dễ dàng bằng cách sử dụng các Thuật toán này
Ví dụ: đây là đoạn mã tìm giai thừa bằng Thuật toán đệ quy
Sự thật[y]
Nếu y là 0
trả lại 1
return [y*Fact[y-1]] /* đây là nơi xảy ra đệ quy*/
2. Thuật toán chia để trị
Đây là một cách hiệu quả khác để giải quyết nhiều vấn đề. Trong thuật toán Chia để trị, chia thuật toán thành hai phần; . Sau đó, trong phần thứ hai, những vấn đề nhỏ hơn này được giải quyết và sau đó được cộng lại với nhau [kết hợp] để tạo ra giải pháp cuối cùng của vấn đề
Sắp xếp hợp nhất và sắp xếp nhanh có thể được thực hiện bằng thuật toán chia để trị. Đây là mã giả của thuật toán sắp xếp hợp nhất để cung cấp cho bạn một ví dụ
Hợp nhấtSắp xếp[ar[], l, r]
Nếu r > l
- Tìm trung điểm để chia mảng đã cho thành hai nửa
giữa m = [l+r]/2
- Gọi mergeSorting cho nửa đầu
Sắp xếp hợp nhất cuộc gọi [ar, l, m]
- Gọi mergeSorting cho nửa thứ hai
Gọi mergeSorting[ar, m+1, r]
- Hợp nhất các nửa được sắp xếp ở bước 2 và 3
Hợp nhất cuộc gọi[ar, l, m, r]
3. Thuật toán lập trình động
Các thuật toán này hoạt động bằng cách ghi nhớ kết quả của lần chạy trước và sử dụng chúng để tìm kết quả mới. Nói cách khác, một thuật toán lập trình động giải quyết các vấn đề phức tạp bằng cách chia chúng thành nhiều bài toán con đơn giản và sau đó nó giải từng bài toán đó một lần rồi lưu trữ chúng để sử dụng trong tương lai
Dãy Fibonacci là một ví dụ điển hình cho thuật toán Lập trình động, bạn có thể thấy nó hoạt động trong mã giả
Fibonacci[N] = 0 [với n=0]
= 0 [với n=1]
= Fibonacci[N-1]+Finacchi[N-2] [với n>1]
4. thuật toán tham lam
Các thuật toán này được sử dụng để giải quyết các vấn đề tối ưu hóa. Trong thuật toán này, chúng tôi tìm thấy một giải pháp tối ưu cục bộ [không quan tâm đến bất kỳ hậu quả nào trong tương lai] và hy vọng tìm được giải pháp tối ưu ở cấp độ toàn cầu
Phương pháp không đảm bảo rằng chúng tôi sẽ có thể tìm thấy một giải pháp tối ưu
Thuật toán có 5 thành phần
- Cái đầu tiên là một tập hợp ứng cử viên mà từ đó chúng tôi cố gắng tìm ra giải pháp
- Chức năng lựa chọn giúp chọn ứng viên tốt nhất có thể
- Một chức năng khả thi giúp quyết định xem ứng viên có thể được sử dụng để tìm giải pháp hay không
- Một hàm mục tiêu gán giá trị cho một giải pháp có thể hoặc cho một giải pháp một phần
- Hàm giải pháp cho biết khi nào chúng tôi đã tìm ra giải pháp cho vấn đề
Mã hóa Huffman và thuật toán Dijkstra là hai ví dụ điển hình trong đó thuật toán Tham lam được sử dụng
Trong mã hóa Huffman, Thuật toán đi qua một tin nhắn và tùy thuộc vào tần số của các ký tự trong tin nhắn đó; . Để thực hiện mã hóa Huffman, trước tiên chúng ta cần xây dựng cây Huffman từ các ký tự đầu vào rồi duyệt qua cây để gán mã cho các ký tự
5. Thuật toán vét cạn
Đây là một trong những thuật toán đơn giản nhất trong khái niệm. Thuật toán brute force lặp lại một cách mù quáng tất cả các giải pháp có thể để tìm kiếm một hoặc nhiều giải pháp có thể giải quyết một hàm. Hãy nghĩ về bạo lực như sử dụng tất cả các tổ hợp số có thể để mở một két sắt
Dưới đây là một ví dụ về Tìm kiếm tuần tự được thực hiện bằng cách sử dụng vũ phu
Thuật toán S_Search [A[0. n], X]
A[n] ← X
tôi ← 0
Trong khi A[i] ≠ X làm
tôi ← tôi + 1
nếu i < n trả về i
khác trở lại -1
6. Thuật toán quay lui
Quay lui là một kỹ thuật để tìm giải pháp cho một vấn đề theo cách tiếp cận gia tăng. Nó giải quyết các vấn đề theo cách đệ quy và cố gắng giải quyết vấn đề bằng cách giải quyết từng phần của vấn đề tại một thời điểm. Nếu một trong các giải pháp không thành công, chúng tôi sẽ xóa giải pháp đó và quay lại để tìm giải pháp khác
Nói cách khác, thuật toán quay lui giải quyết một vấn đề con và nếu nó không giải quyết được vấn đề, nó sẽ hoàn tác bước cuối cùng và bắt đầu lại để tìm giải pháp cho vấn đề
Vấn đề N Queens là một ví dụ điển hình để xem thuật toán Quay lui đang hoạt động. Bài toán N quân Hậu nói rằng có N quân Hậu trong một bàn cờ, và chúng ta phải sắp xếp chúng sao cho không quân hậu nào có thể tấn công bất kỳ quân hậu nào khác trên bàn cờ sau khi đã tổ chức
Bây giờ chúng ta hãy xem thuật toán SolveNQ và Kiểm tra các hàm hợp lệ để giải quyết vấn đề
CheckValid[Bàn cờ, hàng, cột]
Bắt đầu
Nếu có một Nữ hoàng ở bên trái của cột hiện tại, hãy trả về false
Nếu quân hậu ở đường chéo phía trên bên trái, thì trả về false
Nếu quân hậu ở đường chéo phía dưới bên trái, thì trả về false
Trả về đúng
Chấm dứt
SolveNQ[Bảng, Cột]
Bắt đầu
Nếu tất cả các cột đầy, thì trả về true
Đối với mỗi hàng có mặt trong bàn cờ
Làm
Nếu, CheckValid[bảng, x, cột], thì
Đặt quân hậu tại ô [x, cột] trên bàn cờ
Nếu SolveNQ[bảng, cột+1] = True, thì trả về true
Mặt khác, loại bỏ quân hậu khỏi ô [ x, cột] khỏi bàn cờ
Xong
Trả về sai
Chấm dứt
Phần kết luận
Các thuật toán đứng đằng sau hầu hết những điều ấn tượng mà máy tính có thể làm được và đây là cốt lõi của hầu hết các tác vụ điện toán. Giỏi hơn với các thuật toán sẽ giúp bạn trở thành một lập trình viên thành công, nhưng bạn sẽ trở nên hiệu quả hơn
Bài viết được đề xuất
Đây là hướng dẫn về các loại thuật toán. Ở đây chúng tôi thảo luận chi tiết về 6 loại thuật toán quan trọng nhất với các chức năng của chúng. Bạn cũng có thể xem qua các bài viết được đề xuất khác của chúng tôi để tìm hiểu thêm –