Bài viết Cấu trúc dữ liệu và giải thuật là gì ?
thuộc chủ đề về Wiki How
thời gian này đang được rất nhiều bạn quan tâm đúng không nào !!
Hôm nay, Hãy cùng Hlink.Vn tìm hiểu
Cấu trúc dữ liệu và giải thuật là gì ? trong bài viết hôm nay nhé !
Các bạn đang xem bài viết : “Cấu trúc dữ liệu và giải
thuật là gì ?”
Đánh giá về Cấu trúc dữ liệu và giải thuật là gì ?
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. 
Theo lập trình khá muộn
những mình cũng đã tự tìm tòi học rất thường xuyên. Hôm nay mình
xin phép được chia sẻ bài viết với chủ đề “Cấu trúc dữ liệu và giải
thuật là gì ?” . Mình nghỉ rằng chủ đề của mình sẽ có khá thường
xuyên bạn nhập môn lập trình tìm kiếm và xem . 
Mình cho rằng cấu trúc dữ
liệu và giải thuật được xem như là 2 yếu tố quan trọng nhất trong
lập trình, đúng như câu nói nổi tiếng của Niklaus Wirth:
Programs (Chương trình) = Data Structures (Cấu trúc dữ liệu) + Algorithms (Giải thuật)
Vì sao ?Vì nắm vững
các cấu trúc dữ liệu và các giải thuật là cơ sở để tiếp cận với
việc thiết kế và xây dựng phần mềm cũng như dùng các công cụ lập
trình hiện đại.
1. Giới thiệu về giải thuật
✅ Mọi người cũng xem : soi kính ở công ty điện tử là gì
a. Định nghĩa
Mục tiêu của công nghệ phần mềm là gì ?
Một danh mục trước khi được tạo ra nó phải trải qua nhiều bước và công đoạn. Và ngay từ ban đầu người tạo ra một sản phẩm công nghệ sẽ phải có những mục tiêu:
- Tin cậy và chính xác (Reliability – correctness)
- Hữu dụng (utility)
- Đạt được những gì nhu cầu
- Đáp ứng đúng thời điểm
- Mềm dẻo (flexibility)
- có khả năng mang chuyển được (Portability), tức là có thể dễ dàng mang cài đặt sang một hệ thống khác.
- có khả năng tương thích
- Dễ bảo trì
- Dễ hiểu
- có thể sử dụng lại
- Hiệu quả (efficiency)
- Người lập trình (không mất quá thường xuyên công sức cho việc lập trình)
- Máy
- Thời gian
- Bộ nhớ
Để đạt được các mục tiêu này thì chắc chắn chúng ta phải viết các giải thuật và lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.Giải thuật
Giải thuật hay còn gọi là thuật toán – tiếng Anh là Algorithms: là một tập hợp hữu hạn các chỉ thị để được thực thi theo một thứ tự nào đó để thu được kết quả mong muốn. Nói chung thì giải thuật là độc lập với các ngôn ngữ lập trình, tức là một giải thuật có thể được triển khai trong nhiều ngôn ngữ lập trình khác nhéu.
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ể 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 hình 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 !
✅ Mọi người cũng xem : tivi cường lực là gì
Lập trình hướng giấy tờ và hướng đối tượng
-
Cả hai cách tiếp cận này đều đặn thực hiện theo phương pháp tinh chỉnh từng bước (stepwise refinement):
-
Tiếp cận hướng giấy tờ (Function Oriented):
- Tập trung vào các hàm và việc phân rã các hàm
- Các cấu trúc dữ liệu (ở mức ngôn ngữ lập trình) được định nghĩa sớm.
- Các cấu trúc dữ liệu khó có thể thay đổi ngay
-
Tiếp cận hướng đối tượng (Object Oriented)
- Tập trung vào các đối tượng trừu tượng
- Các cấu trúc dữ liệu trừu tượng được định nghĩa sớm
- Cấu trúc dữ liệu chi tiết mức ngôn ngữ chưa được định nghĩa
- Cấu trúc dữ liệu dễ thay đổi ngay hơn
✅ Mọi người cũng xem : trung tâm tư vấn du học tiếng anh là gì
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 đó. In kết quả lên
màn hình Vớ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 hồ sơ
- Xâ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ác
- Nhập dữ liệu
- Tính diện tích
- Tính chu vi
- Xây dựng hàm main() dùng các hàm ở trên
✅ Mọi người cũng xem : thép đã tôi thế đấy nghĩa là gì
Tiếp cận hướng đối tượng
class 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án
- Thuật toán dễ dàng, dễ hiểu
- Thuật toán dễ cài đặt
- Thuật toán cần ít bộ nhớ
- Thuật toán chạy nhanh
✅ Mọi người cũng xem : tâm huyết với nghề là gì
=> Khi cài đặt thuật toán chỉ để dùng một số ít lần thì ưu tiên tiêu chí 1 và 2
✅ Mọi người cũng xem : quyết tâm là gì
=> Khi cài đặt thuật toán mà sử dụng rất thường xuyên lần, trong thường xuyên chương trình khác nhéu: sắp xếp, tìm kiếm, đồ thị… thì ưu tiên tiêu chí 3 và 4
Các khía cạnh cần phân tích
- Bộ nhớ (Space) Xác định tổng dung lượng bộ nhớ rất 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)
✅ Mọi người cũng xem : nội thương là gì
2. Giả mã (Pseudocode)
Khi thống kê 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 cao
- nhiều cấu trúc hơn ngôn ngữ tự nhiên
- Kém chi tiết hơn chương trình
- 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: tổng giá trị lớn nhất của A Max <- A[0] for i <- 1 to n-1 do if A[i] > Max then Max <- A[i] return Max
✅ Mọi người cũng xem : quản lý nhân lực là làm gì
3. Đệ qui (Recursion)
Ở đây mình cho các bạn một vd trước.
✅ Mọi người cũng xem : tâm đố kỵ là gì
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ất
Là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 .
✅ Mọi người cũng xem : xót thương là gì
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ó.
Ví dụ tính giai thừa: n! = 1· 2· 3· ··· · (n-1)· n
// hàm đệ qui tính giai thừa int recursiveFactorial(int n) if (n == 0) return 1; // trường hợp cơ sở else return n * recursiveFactorial(n- 1);
Ví dụ: Cộng các phần tử của
một mảngCho mảng A có n phần tử
Thử
tính xem kết quả Ví dụ
dễ dàng cho đệ qui tuyến tính
Algorithm LinearSum(A, n): Input: Một mảng A có kiểu nguyên và số nguyên n ≥ 1, A có ít nhất n phần tử Output: Tổng của n số nguyên đầu tiên trong A if n = 1 then return A[0] else return LinearSum(A, n - 1) + A[n - 1]
Trên đây một số khái niệm và định nghĩa cơ bản của
giải thuật Có dễ hiểu không các bạn ? Mới đầu tìm hiểu nó mình đã
sang chấn tâm lý Bài chia sẻ này mình đã tham khảo các tài liệu
trên mạng và đúc kết được khi tham gia buổi talk của cô giáo Vũ Thị
Thanh Huyền Trưởng bộ môn CNTT Trường Cao đẳng thực hành FPT
Polytechnic ĐN. Mong mọi nguời bỏ qua sai xót và góp ý cho mình cải
thiện . mình xin phép
dừng bài viết ở đây! Cảm ơn mọi người đã theo dõi.
Phần tiếp theo:
Các câu hỏi về giải thuật toán là gì
Nếu có bắt kỳ câu hỏi thắc mắt nào vê giải thuật toán là gì hãy cho chúng mình biết nhé, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình cải thiện hơn trong các bài sau nhé
Trả lời