Các Thuật Toán Cơ Bản Cho Lập Trình Viên, 5 Thuật Toán Mà Mọi Lập Trình Viên Nên Biết
Trong những năm gần đây, nhu cầu tuyển dụng ngành lập trình nhiều nên rất nhiều bạn theo học ngành công nghệ thông và cũng rất nhiều bạn từ ngành khác chuyển sang. Do thời gian học ngắn hoặc thiếu tập trung trong quá trình học, các bạn gặp rất nhiều khó khăn khi đi phỏng vấn, nhất là phỏng vấn với thuật toán.
Bạn đang xem: Các thuật toán cơ bản
Trong chuỗi bài viết này, mình sẽ trình bày một cách rất cơ bản về thuật toán và những thuật toán thường gặp để giúp các bạn dễ hiểu, dễ áp dụng và tự tin trong quá trình tham gia phỏng vấn tìm việc cũng như tạo nền tảng cho quá trình học lập trình.
Thuật toán là gì?
Thuật toán/Thuật giải/Giải thuật/Algorithm nói chung đó là cách giải một bài toán bằng chương trình máy tính. Kỹ năng về thuật toán là nền tảng trong lập trình nên các lập trình viên phải nắm vững phần này thì mới làm việc tốt được.
Ví dụ: Để giải một phương trình bật nhất ax+b =0. Cần các bước:
Khai báo các biến a, b và x
Nhập hai tham số a và b
Kiểm tra a:
Nếu a =0
Kiểm tra b
Nếu b= 0 thì in ra phương trình có vô số nghiệm
Nếu b0 thì in ra phương trình vô nghiệm
Nếu a0
In ra phương trình có một nghiệm x=-b/a
Cái trên gọi là thuật toán để giải phương trình bậc nhất ax+b=0
Cách biểu diễn thuật toán
Đôi khi bạn biết cách giải nhưng lại không nắm được cách trình bày cũng là một vấn đề khác bạn phải đối mặt. Có 03 cách cơ bản để biểu diễn thuật toán:
– Sử dụng ngôn ngữ giả (Pseudo Code)– Sử dụng sơ đồ khối (Flow Chart)– Sử dụng code của một ngôn ngữ lập trình nào đó.1. Ngôn ngữ giả (Pseudo Code)
Ngôn ngữ giả, ở đây có nghĩa là không phải ngôn ngữ lập trình, bạn có thể sử dụng ngôn ngữ tiếng Anh hoặc tiếng Việt để biểu diễn thuật toán. Ví dụ ở trên tôi sử dụng tiếng Việt để biểu diễn thuật toán giải phương trình bậc nhất ax + b =0 . Ở các bài tiếp theo chúng ta sử dụng thường xuyên ngôn ngữ giả để biểu diễn thuật toán.
2. Sơ đồ khối (Flowchart)
Sơ đồ khối sử dụng các ký hiệu để biểu diễn các khối lệnh trong thuật toán.
a. Bảng ký hiệu của sơ đồ khối
b. Khối lệnh điều khiển (if)
c. Khối lệnh điều khiển (if..else)
d. Khối lệnh lặp
e. Ví dụ: Sử dụng sơ đồ khối để biểu diễn thuật giải để giải bài toán ax+b=0 ở trên.
3. Code
Bạn có thể sử dụng ngôn ngữ lập trình mình đã học để biểu diễn thuật toán.
Ví dụ: Sử dụng ngôn ngữ lập trình Java để biểu diễn thuật toán giải phương trình ax+b=0 ở trên.
package firstdegreeequation;
import java.util.Scanner;
public class First
Degree
Equation {
public static void main(String<> args) { System.out.println("Giai phuong trinh bac nhat ax + b =0"); int a, b; double x; Scanner sc= new Scanner(System.in); System.out.print("Nhap bien so a:"); a= sc.next
Int(); System.out.print("Nhap bien so b:"); b= sc.next
Int();
if(a==0) if(b==0) System.out.println("Phuong trinh co vo so nghiem"); else System.out.println("Phuong trinh vo nghiem"); else{ x=(double)-b/a; System.out.println("Phuong trinh co nghiem x=" + x); }}
}
Việc nắm rõ cách biểu diễn thuật toán ngoài việc giúp bạn biểu diễn thuật toán bạn muốn viết ra, nó còn giúp bạn đọc, hiểu các thuật toán do người khác viết hoặc đọc các đề thi tuyển.
Cách giải quyết một bài toán liên quan đến thuật toán
Có thể tóm tắt các bước để giải một bài toán liên quan đến thuật toán như sau:
– Tìm hiểu kỹ về yêu cầu– Tìm ra cách giải– Phân ra từng bước thực hiện– Biểu diễna. Tìm hiểu kỹ về yêu cầu
Đây làm bước đọc đề, bạn cần đọc kỹ để nắm bắt được yêu cầu và đảm bảo hiểu được yêu cầu.
b. Tìm ra cách giải
Bước này khó nhất, tùy thuật vào kỹ năng tư duy và kinh nghiệm của bạn. Phần lớn phụ thuộc nhiều và khả năng làm toán của bạn. Tuy nhiên, nếu bạn chịu khó đọc kỹ các bài toán liên quan hoặc lập trình nhiều kỹ năng này cũng tăng lên.
c. Phân ra từng bước thực hiện
Lập trình là quá trình chia nhỏ các bước thực hiện của một thuật toán đến mức có thể viết thành các lệnh trong ngôn ngữ lập trình. Nên bạn cần chia nhỏ các bước thực hiện của thuật giải ra thành từng bước nhỏ nhất có thể biểu diễn.
d. Biểu diễn
Tùy theo nhu cầu mà bạn có thể biểu diễn thuật toán theo các hình thức đã nêu ở trên.
Thuật toán và cấu trúc dữ liệu
Mỗi kiểu dữ liệu sẽ định hình trên đó các bài toán cơ bản và thuật giải trên đó. Do vậy, khi nói về thuật toán chúng ta thường phải đi kèm với cấu trúc dữ liệu. Trong các bài tiếp theo chúng ta sẽ làm quen với các thuật toán thông dụng trên các kiểu dữ liệu thường gặp như:
– Các thuật toán khácTrên đây là những nội dung cơ bản về thuật toán, hy vọng giúp bạn dễ dàng hơn trong việc học hoặc ôn tập về thuật toán.
Xã hội hiện tại đang chứng kiến một cuộc cách mạng to lớn trong lĩnh vực công nghệ. Những phát minh mới liên tục được cập nhật. Thường thì nguồn gốc của những phát minh này là từ những chương trình gạo cội có khả năng chi phối và thao túng các xu hướng công nghệ đang diễn ra. Trong số đó không thể không nói đến mã hóa và thuật toán, được sử dụng để phát triển các chương trình cạnh tranh như vậy.
Vì thế, đối với một chương trình thành công và có tầm ảnh hưởng, việc khai thác một thuật toán tốt nhất đúng và chính xác là điều tất yếu. Sau đây là 10 thuật toán hàng đầu được sử dụng rộng rãi trong lập trình và phát triển web.
1. Hashing
5. Phân tích liên kết (Link Analysis)
Thường được sử dụng trong lĩnh vực mạng, phân tích liên kết cung cấp khả năng tương quan giữa các thực thể khác nhau trong một miền quan trọng đối với các công cụ tìm kiếm. Thuật toán sử dụng một biểu diễn đồ họa và ma trận phức tạp, liên kết các căn cứ tương tự trong các miền hiện tại. Phân tích liên kết phổ biến trong các công cụ tìm kiếm như Google, trong các trang truyền thông xã hội như Facebook, Twitter, nơi việc tìm kiếm mở rộng được chú trọng.6. Phép toán Mô-đun (Modulo Arithmetic Algorithms)
Nhiều thuật toán mã hóa phức tạp nhưng nếu được phân tích trên nền số học mô-đun thì trở nên đơn giản vô cùng. Trong số học mô-đun, các số chúng ta đang xử lý chỉ là các số nguyên và các phép toán được sử dụng là cộng, trừ, nhân và chia. Sự khác biệt duy nhất giữa số học mô-đun và số học trên sách vở là trong số học mô-đun, tất cả các hoạt động được thực hiện liên quan đến số nguyên dương, tức là mô đun.Ví dụ:
Thuật toán Euclide cơ bản và mở rộngPhương trình hoàn hảo của Euler
Lũy thừa mô đun
Tính nghịch đảo theo mô đun
Định lý số dư của Trung Quốc
Định lý số dư của Trung Quốc và thực thi tính nghịch đảo của mô đun
7. Thuật toán xâu ký tự và phân tích cú pháp (String Matching and Parsing Algorithms)
Quy trình tạo xâu tương ứng luôn quan trọng đặc biệt đối với miền và phần tử mạng. Thuật toán xâu ký tự này sẽ phát huy khả năng tối đa trong các tình huống mà các xâu phải khớp trong một chuỗi dài hoặc khi xác nhận chuỗi bằng cách phân tích cú pháp qua giới hạn được xác định trước. Các thuật toán này thường được sử dụng trong phát triển web cho URL.8. Thuật toán biến đổi Fourier (Fourier Transform Algorithms)
Biến đổi Fourier hay Biến đổi Fourire nhanh là những thuật toán đơn giản nhưng rất mạnh. Chúng được sử dụng để chuyển đổi tín hiệu từ miền thời gian sang miền tần số và ngược lại. Toàn bộ các mạng kỹ thuật số như Internet, WiFi, điện thoại, máy tính, bộ định tuyến, vệ tinh, sử dụng thuật toán này theo để vận hành. Đây là những thuật toán bắt buộc phải biết nếu bạn chuyên sâu về mảng điện tử, điện toán hoặc viễn thông.
9. Thuật toán các tập không giao nhau (Disjoint Sets)
Thuật toán các tập không giao nhau là cấu trúc dữ liệu đóng vai trò như các cấu trúc trợ giúp trong một thuật toán để biểu diễn nhiều tập hợp trong mảng riêng lẻ, với mỗi mục là một phần tử của một trong nhiều tập hợp. Do đó, các bộ tách rời đại diện cho các phần tử được kết nối trong các thuật toán đồ thị hay phân đoạn một hình ảnh.10. Hệ số tích phân (Integer Factorization)
Thuật toán lũy thừa số nguyên là một thuật toán toán cung cấp hướng dẫn từng bước về cách lấy các thừa số nguyên tố của một số tổng hợp. Thuật toán này giải quyết các vấn đề phức tạp trong các nền tảng mã hóa yêu cầu bạn phải giải quyết các số nguyên phức hợp lớn.Nguồn tại Technotification
