Python - Thiết kế thuật toán
Thuật toán là một thủ tục từng bước, xác định một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để có được đầu ra mong muốn. 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ức là một thuật toán có thể được thực hiện bằng nhiều ngôn ngữ lập trình.
Từ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng:
Search - Thuật toán tìm kiếm một mục trong cấu trúc dữ liệu.
Sort - Thuật toán sắp xếp các mặt hàng theo một thứ tự nhất định.
Insert - Thuật toán chèn mục trong cấu trúc dữ liệu.
Update - Thuật toán cập nhật một mục hiện có trong cấu trúc dữ liệu.
Delete - Thuật toán xóa một mục hiện có khỏi cấu trúc dữ liệu.
Đặc điểm của một thuật toán
Không phải tất cả các thủ tục đều có thể được gọi là một thuật toán. Thuật toán phải có các đặc điểm sau:
Unambiguous- Thuật toán phải rõ ràng và không mập mờ. Mỗi bước (hoặc giai đoạn) của nó, và đầu vào / đầu ra của chúng phải rõ ràng và chỉ dẫn đến một ý nghĩa.
Input - Một thuật toán phải có 0 hoặc nhiều đầu vào được xác định rõ ràng.
Output - Một thuật toán phải có 1 hoặc nhiều đầu ra được xác định rõ và phải phù hợp với đầu ra mong muốn.
Finiteness - Thuật toán phải kết thúc sau một số bước hữu hạn.
Feasibility - Nên khả thi với các nguồn lực sẵn có.
Independent - Một thuật toán phải có hướng dẫn từng bước, điều này phải độc lập với bất kỳ mã lập trình nào.
Làm thế nào để viết một thuật toán?
Không có tiêu chuẩn được xác định rõ ràng để viết thuật toán. Đúng hơn, đó là vấn đề và phụ thuộc vào tài nguyên. Các thuật toán không bao giờ được viết để hỗ trợ một mã lập trình cụ thể.
Như chúng ta biết rằng tất cả các ngôn ngữ lập trình đều có chung các cấu trúc mã cơ bản như vòng lặp (do, for, while), điều khiển luồng (if-else), v.v. Những cấu trúc chung này có thể được sử dụng để viết một thuật toán.
Chúng tôi viết các thuật toán theo cách thức từng bước, nhưng không phải lúc nào cũng vậy. Viết thuật toán là một quá trình và được thực hiện sau khi miền vấn đề được xác định rõ. Đó là, chúng ta nên biết miền vấn đề mà chúng ta đang thiết kế một giải pháp.
Thí dụ
Hãy thử tìm hiểu cách viết thuật toán bằng cách sử dụng một ví dụ.
Problem - Thiết kế thuật toán cộng hai số và hiển thị kết quả.
step 1 − START
step 2 − declare three integers a, b & c
step 3 − define values of a & b
step 4 − add values of a & b
step 5 − store output of step 4 to c
step 6 − print c
step 7 − STOPCác thuật toán cho người lập trình biết cách viết mã chương trình. Ngoài ra, thuật toán có thể được viết dưới dạng:
step 1 − START ADD
step 2 − get values of a & b
step 3 − c ← a + b
step 4 − display c
step 5 − STOPTrong thiết kế và phân tích các thuật toán, thường phương pháp thứ hai được sử dụng để mô tả một thuật toán. Nó giúp nhà phân tích dễ dàng phân tích thuật toán bỏ qua tất cả các định nghĩa không mong muốn. Anh ta có thể quan sát những thao tác nào đang được sử dụng và quy trình đang diễn ra như thế nào.
Viết step numbers, Là tùy chọn.
Chúng tôi thiết kế một thuật toán để có được giải pháp của một vấn đề nhất định. Một vấn đề có thể được giải quyết bằng nhiều cách.
Do đó, nhiều thuật toán giải có thể được rút ra cho một vấn đề nhất định. Bước tiếp theo là phân tích các thuật toán giải pháp được đề xuất đó và triển khai giải pháp phù hợp nhất.