Đối với người học lập trình nói chung, kết cấu dữ liệu và giải mã là giữa những môn đặc biệt và thường được dạy vào tầm khoảng năm 2 cùng năm 3 đại học. Cảm giác của rất nhiều người nếu chưa tự tin là dễ bị nản ngay từ quá trình đầu và từ từ sẽ trở ngại hơn để bắt nhịp. Đồng thời, học tập tốt cấu trúc dữ liệu cùng giải thuật để giúp cho các dòng code của chính mình trở đề nghị tối ưu hơn.

Bạn đang xem: Giải thuật và lập trình

Trong bài viết này, mình sẽ tổng hợp những kiến thức cơ bạn dạng cùng các kinh nghiệm của chính bản thân mình để giúp chúng ta đi đúng phía và cảm xúc sự thú vui của môn học này. Tất nhiên xung quanh ta vẫn có không ít cao thủ, việc trình làng các kỹ năng khó sẽ khiến mọi bạn bị ngợp phải trong phạm vi bài viết này, mình sẽ ra mắt các vụ việc cơ bạn dạng (ít nhất là trong các bài soát sổ trên trường). Hãy cùng tham khảo bài viết dưới đây:


Chuẩn bị hầu như gì để học thuật toán?

Đầu tiên, nhằm học được cấu trúc tài liệu và giải thuật (Từ giờ đến cuối nội dung bài viết mình sẽ gọi tắt là thuật toán), các bạn phải có khả năng tự học cao. Phải có công dụng tìm tìm tốt. Phần nhiều mọi trang bị cơ bản đều gồm trên google, trong khuôn khổ nội dung bài viết này mình sẽ gửi ra những vấn đề quan trọng, để các bạn follow theo keyword đó, tìm kiếm cho chính mình một nền tảng vững chắc.

Tiếp theo, chúng ta cần chọn cho chính mình một ngôn từ lập trình. Theo bản thân thì C/C++ là ngôn từ nên được sử dụng lúc học thuật toán vì:

Các kiểu dữ liệu trong ngữ điệu C/C++ được khái niệm rõ ràng, bao gồm kiểu truyền tham chiếu cùng tham trị tương đối hay.Tốc độ thực thi nhanh.Có nhiều sách, tài liệu tham khảo trên mạng internet về cấu trúc dữ liệu và giải thuật được viết bằng C/C++.

Tuy nhiên, nếu muốn hoặc có nền tảng những ngôn ngữ không giống (java, python,...) thì mọi tín đồ cũng rất có thể sử dụng nhằm học được vì theo bí quyết sau:

Cấu trúc tài liệu + giải thuật = Chương trình

Việc viết một chương trình, giải một vấn đề được phối kết hợp bởi 2 yếu ớt tố, lựa chọn một cấu trúc dữ liệu phù hợp, kế tiếp tìm ra phương hướng phối hợp mọi thứ bởi giải thuật để có thể giải được bài bác toán. Bởi đó bạn có thể lựa chọn ngôn ngữ yêu thích và bắt đầu.

Các vấn đề cần quan tâm

Trong phần này bản thân sẽ nói đến 7 vấn đề sau:

1. Độ phức hợp thuật toán (big O)

2. Sắp xếp và search kiếm nhị phân

3. Các phương thức sinh

4. Đệ quy, tảo lui

5. Cấu trúc dữ liệu stack, queue, dequeue

6. Quy hướng động

7. Đồ thị.

1. Độ tinh vi thuật toán (big O)

Khái niệm độ tinh vi thuật toán có thể hiểu dễ dàng và đơn giản là độ cấp tốc hay chậm trễ của thuật toán. Chữ O là ký hiệu được áp dụng cho độ tinh vi thuật toán. Các loại độ tinh vi thuật toán cơ bạn dạng có thể kể đến là:

*
*
*
*
*

Trong đó, n là bộc lộ kích thước đầu vào.

Lưu ý rằng nếu các bạn sử dụng 2 vòng lặp cùng cấp thì form size sẽ là 2*n, nhưng độ tinh vi thuật toán biểu diễn vẫn chính là O(n) vì tôi chỉ lấy giao động thôi.

Và nếu bạn của người tiêu dùng nói là 2 vòng lặp lồng nhau thì độ phức tạp sẽ là O(n^2) thì họ đôi khi nên xem xét kỹ rộng thuật toán. Như lấy ví dụ như sau:

int i = 0;int n = 1000;while (i ví như không xem xét thì có thể sẽ nhầm hàm này là O(N^2), nhưng thực tiễn độ phức hợp của nó là O(n). Bởi vì nếu như i

2. Bố trí và tra cứu kiếm nhị phân

a. Sắp tới xếp

Để rất có thể hiểu rõ các thuật toán chạy như nào, chúng ta nên tìm những source code bên trên mạng về và chạy thử, kế tiếp tự ngẫm xem những hàm của nó chạy như nào, các phép toán có công dụng gì. Trong số thuật toán thu xếp thì mình thấy có rất nhiều thuật toán như:

Bubble sortSelection sortInsertion sortQuick sortHeap sort...

Xem thêm: 10 Lợi Ích Tuyệt Vời Của Râu Bắp Có Tác Dụng Gì ? Cách Dùng Dược Liệu Râu Ngô

Ngoài ra còn tương đối nhiều thuật toán thu xếp khác nữa, tùy vào điều kiện môn học trên ngôi trường yêu mong gì thì mình học theo. Còn theo gớm nghiệm của bản thân mình thì để làm bài tập cùng code thuật toán thì học tập bubble sort (O(n)) và quick sort(~O(nlog(n))) thôi là đủ code được cả nghìn bài rồi. Đa số đều áp dụng quick sort hay dùng luôn luôn hàm sort trong thư viện( vào C++ là hàm sort trong tủ sách algorithm gồm độ tinh vi ~ O(nlog(n))).

Còn việc reviews nhiều thuật toán sort là tùy theo điều kiện rõ ràng thì từng thuật toán gồm những ưu điểm và điểm yếu riêng, vận dụng trong thực tế. Lấy ví dụ nhưinsertion sorthay sắp xếp chènthường được thực hiện trong bảng xếp hạng,đâylà thuật toán bố trí xử lý chèn thành phần đang xét vào vị trí thích hợp của dãy số đã bố trí phía trước sao cho dãy số vẫn luôn là dãy bố trí có sản phẩm công nghệ tự.

b. Tra cứu kiếm nhị phân

Ý tưởng chủ yếu của kiếm tìm kiếm hoàn toàn có thể biểu diễn dễ dàng bằng một câu hỏi như sau:

Có n các bạn được xếp thành một sản phẩm theo vật dụng tự độ cao tăng dần. Thầy giáo nhìn vào danh sách học sinh mà không tồn tại tên, chỉ bao gồm chiều cao, cho nên vì vậy cần tìm chúng ta có chiều cao là X vào hàng.

Bình thường thì biện pháp làm đơn giản và dễ dàng nhất là duyệt từ đầu hàng đến cuối hàng một cách lần lượt, khi đó chắc chắn sẽ tìm được bạn có chiều cao là X đó (độ phức tạp thuật toán sẽ là O(n)). Có một cách cấp tốc hơn để giải bài toán này, đó là ta sẽ nhìn vào người ở giữa dãy, nếu bạn đó có chiều cao bằng X thì ta sẽ tìm được luôn, còn nếu không thì ta sẽ biết chắc chắn người đó sẽ đứng ở nửa nào trong 2 nửa còn lại của hàng, qua đó lặp lại phương pháp bên trên đến khi tìm ra bạn đó, phía trên chính là ý tưởng chính của thuật toán tìm kiếm nhị phân với độ phức tạp chỉ còn O(nlog(n)).

*

3. Các cách thức sinh

Có thể bạn chưa biết, gần như tất cả các bài toán đều có thể giải bằng cách duyệt trâu từng trường hợp. Vì đó các phương pháp sinh là không thể thiếu lúc học thuật toán. Có 4 phương pháp sinh mà các bạn nhất định phải học:

Sinh nhị phânSinh hoán vịSinh tổ hợpSinh chỉnh hợp

Các bạn có thể tìm hiểu các thuật toán trên và submit trong trang sau nhé:

https://www.spoj.com/PTIT/problems/basic/

4. Đệ quy, xoay lui

Nói đơn giản thì đệ quy là hàm gọi lại chính nó, biểu diễn đối tượng được định nghĩa quy nạp theo các đối tượng con đồng dạng với nó. Sau đây là một số ví dụ của hàm sử dụng vòng lặp bình thường và hàm đệ quy:

int giaithua(int n) {int res=1;for (int i = 1; i Bây giờ hãy cùng mình xem qua một số cách viết hàm tính a^b ( với a khác 0). Tất nhiên với các bài toán giới hạn lớn thì a^b sẽ rất lớn, vị đó mình sẽ lấy phần dư mang lại mod nhé.

// dpt O(n)long long cal_pow(int a, int b, int mod) long long res=1;for (int i = 1; i > 1, mod);Qua đó các bạn có thể thấy các hàm đệ quy rất thú vị. Các phương pháp sinh ở trên, ngoài cách code chay sinh từng cấu hình thì cũng có thể sử dụng đệ quy để viết một cách gọn gàng hơn. Thuật toán cù lui cũng dựa trên tứ tưởng của hàm đệ quy như trên, suy mang lại cùng các thuật toán sinh được dùng để duyệt hết các cấu hình có thể, trong một số bài toán thì có thể sử dụng nhánh cận, cài cắm các đoạn xử lý loại bỏ các trường hợp không cần thiết để chương trình được tối ưu hơn.

Tạm kết

Mình tạm dừng phần 1 ở đây, trong bài viết sau mình sẽ nói tiếp các vấn đề cần niềm nở khác, các nguồn tài liệu và website mình giỏi dùng vào quá trình học. Các bạn đón coi nhé :))