Chào các bạn mình là viên năm cuối chuyên nghành Lập trình máy tính. Mình chỉ vừa chuyển nghành từ khách sạn, một chuyên nghành chả liên quan gì đến CNTT để trở thành một lập trình viên.
Cách viết một giải thuật ?Giống như tất cả các bạn mình cũng đã tìm kiếm để có thể trả lời cho câu hỏi này nhưng chả có bài viết nào nói về cách viết một giải thuật cả, bởi vì sẽ không có bất kỳ tiêu chuẩn nào cho trước để viết các giải thuật.Như bạn đã biết, các ngôn ngữ lập trình đều có các vòng lặp (do, for, while) và các lệnh điều khiển luồng (if-else), … Bạn có thể sử dụng những lệnh này để viết một giải thuật.Chúng ta viết các giải thuật theo cách thức là theo từng bước một. Viết giải thuật là một tiến trình và được thực thi sau khi bạn đã định vị rõ ràng vấn đề cần giải quyết. Từ việc định vị vấn đề, chúng ta sẽ thiết kế ra giải pháp để giải quyết vấn đề đó và sau đó là viết giải thuật.=> Chính các bạn đã và đang viết ra các giải thuật hằng ngày mà các bạn lại không biết thôi !
Ví dụ viết giải thuật:
Bài toán: Lập chương trình nhập vào tọa độ các đỉnh của 1 tam giác bất kỳ trong mặt phẳng. Tính diện tích và chu vi của tam giác đó.
Bạn đang xem: Cấu trúc dữ liệu và thuật toán
Xem thêm: 'Sở Kiều Truyện Sở Kiều Truyện Tập Cuối Trùng Phùng Sở Kiều Truyện Phần 2
In kết quả lên màn hìnhVới bài toán trên bạn sẽ lập từng bước như thế nào để giải bài toán? (Hãy dừng lại vài phút thử nghĩ xem nhé.) Tiếp cận hướng thủ tụcXây dựng các hàm:Định nghĩa cấu trúc dữ liệu biểu diễn một tam giácNhập dữ liệuTính diện tíchTính chu viXây dựng hàm main() sử dụng các hàm ở trênTiếp cận hướng đối tượngclass Tamgiac{ private: float xA, yA, xB,yB, xC, yC;public:void Nhap();float Dientich();float Chuvi();};
b. Phân tích các thuật toán
Tính hiệu quả của thuật toánThuật toán đơn giản, dễ hiểuThuật toán dễ cài đặtThuật toán cần ít bộ nhớThuật toán chạy nhanh=> Khi cài đặt thuật toán chỉ để sử dụng một số ít lần thì ưu tiên tiêu chí 1 và 2=> Khi cài đặt thuật toán mà sử dụng rất nhiều lần, trong nhiều chương trình khác nhau: sắp xếp, tìm kiếm, đồ thị… thì ưu tiên tiêu chí 3 và 4Các khía cạnh cần phân tíchBộ nhớ (Space)Xác định tổng dung lượng bộ nhớ cần thiết để lưu trữ toàn bộ dữ liệu đầu vào, trung gian và kết quả đầu ra.Ví dụ: Sắp xếp một dãy n phần tử.Bộ nhớ cần cho bài toán là: Bộ nhớ lưu biến n, lưu n phần tử của dãy, lưu các biến i, j, tg (nếu là thuật toán Bubble Sort)Thời gian chạy của thuật toán (Running time)2. Giả mã (Pseudocode)
Khi nghiên cứu về Cấu trúc dữ liệu và giải thuật các bạn sẻ được nghe về cụm từ "Giả mã", vậy nó là gì?Như tên của nó, không phải là mã thực dùng để biểu diễn thuật toán, xác định một tập hợp các bước cần được thi hành để có được đáp án bài toán, nó chỉ đưa ra các bước cần làm. Chúng ta phải dùng một ngôn ngữ lập trình khác để viết mã thực cho việc thực thi các bước này. Các bác chỉ cần nhớ những ý sau:Mô tả thuật toán ở mức trừu tượng caoNhiều cấu trúc hơn ngôn ngữ tự nhiênKém chi tiết hơn chương trìnhSử dụng nhiều ký hiệu để mô tảVí dụ:Algorithm arrayMax(A,n) Input: Mảng A có n số nguyên Output: Giá trị lớn nhất của A Max Max then Max
3. Đệ qui (Recursion)
Ở đây mình cho các bạn một vd trước.Một cuộc hành trình 1000 bước và việc thực hiện hành trình bắt đầu ở bước thứ nhấtLàm thế nào thế nào để hoàn thành cuộc hành trình này?Đó là thực hiện bước một bước và tạo ra cuộc hành trình mới có 999 bước, rồi thực hiện bước một bước (tức là bước thứ hai) và tạo ra cuộc hành trình mới có 998 bước,...Bạn có thấy rằng khi bạn bước 1000 bước thì bạn chỉ thực hiện bước một bước nhưng lặp đi lặp lại nó một 1000 lần .
Hàm (phương thức) đệ qui:Định nghĩa:
Đệ quy xảy ra khi người viết các phương thức (hàm) tự gọi (hoặc định nghĩa lại) chính nó.