Có bao nhiêu loại thuật toán trong Python?

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

  1. Tìm trung điểm để chia mảng đã cho thành hai nửa

giữa m = [l+r]/2

  1. Gọi mergeSorting cho nửa đầu

Sắp xếp hợp nhất cuộc gọi [ar, l, m]

  1. Gọi mergeSorting cho nửa thứ hai

Gọi mergeSorting[ar, m+1, r]

  1. 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 –

4 loại thuật toán là gì?

Giới thiệu về các loại thuật toán . thuật toán tham lam. thuật toán đệ quy. thuật toán quay lui. Brute Force algorithm. Greedy algorithm. Recursive algorithm. Backtracking algorithm.

Có bao nhiêu loại thuật toán?

Có bảy loại thuật toán lập trình khác nhau. .
thuật toán sắp xếp
thuật toán tìm kiếm
băm
Lập trình năng động
Hàm mũ bằng cách bình phương
Kết hợp chuỗi và phân tích cú pháp
Thuật toán kiểm tra tính nguyên thủy

Có thuật toán nào trong Python không?

Khoa học dữ liệu thực tế sử dụng Python . Các thuật toán thường được tạo độc lập với các ngôn ngữ cơ bản, tôi. e. một thuật toán có thể được thực hiện bằng nhiều ngôn ngữ lập trình. Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Thuật toán là gì và các loại của nó?

Thuật toán là một quy trình từng bước để giải một bài toán. Một thuật toán tốt phải được tối ưu hóa về mặt thời gian và không gian. Các loại vấn đề khác nhau đòi hỏi các loại kỹ thuật thuật toán khác nhau để giải quyết theo cách tối ưu nhất

Chủ Đề