Một kỹ thuật sử dụng mảng

Trong các ứng dụng thông thường thì rất ít khi sử dụng mảng mà thay vào đó chủ yếu là sử dụng danh sách. Tuy nhiên, trong trường hợp các phần tử là hữu hạn thì dùng mảng là tốt nhất. Trong bài viết này, mình viết là một kỹ thuật sử dụng mảng trong thuật toán đơn giản, sẽ có ích với người mới làm quen với kỹ thuật lập trình.

Alogrithm: Sắp xếp vun đống (heap sort)

Thực hiện vun đống

Trước hết ta hãy hình dung nếu chúng ta có một danh sách các đồ vật và mỗi đồ vật thì có một giá trị cân nặng cụ thể. Làm thế nào để chúng ta có thể sắp xếp lại chúng theo chiều cân nặng tăng dần chẳng hạn.

Rất may mắn có một người bạn giúp ta làm một việc như sau: người bạn đó sẽ sắp xếp số đồ vật của chúng ta thành một đống mà phần tử ở trên bao giờ cũng nhẹ hơn phần tử ở dưới. Như vậy, ta lấy được đồ vật nhỏ nhất và bỏ ra ngoài. Người bạn lại tiếp tục sắp lại đống đồ vật trên và ta lại chọn phần tử ở trên cao nhất - là phần tử nhẹ nhất trong đống nhưng nhẹ thứ hai trong danh sách các đồ vật. Cứ thế đến cuối cùng thì các phần tử được ta nhặt ra từ đống sẽ được sắp xếp.

Ngay lập tức ta thấy có một câu hỏi đặt ra là việc xếp lại cái đống đồ vật để cho ta chọn đồ vật nhẹ nhất có phức tạp và khó khăn hay không? Rất may nó lại khá đơn giản, post này sẽ giải thích kỹ hơn cho bạn.

Algorithm: Thuật toán sắp xếp nhanh (quick sort)

Hình động cảu thuật toán sắp xếp nhanh

Các thuật toán như sắp xếp nổi bọt, chèn và chọn đều có độ phức tạp trung bình về thời gian là O(n²). Với thuật toán sắp xếp nhanh trong trường hợp xuất nhất (khi danh sách đầu vào đã được sắp xếp rồi) thì độ phức tạp về thời gian sẽ là O(n²) còn trong trường hợp trung bình thì độ phức tạp về thời gian của nó là O(nlogn). Như vậy, trong các tình huống sắp xếp thông thường ta sẽ chọn thuật toán sắp xếp nhanh để cài đặt cho bài toán sắp xếp của mình. Quick sort cũng là một thuật toán đặc trưng của tư tưởng chia để trị.

Algorithm: Thuật toán sắp xếp chèn (insertion sort)

Sắp xếp chèn (insertion sort)

Khác hoàn toàn với thuật toán sắp xếp chọn (tại một vị trí ta đi chọn phần tử phù hợp), thuật toán chèn làm ngược lại là xét các phần tử với từng phần tử ta sẽ chèn nó vào vị trí đúng thứ tự của sắp xếp.

Algorithm: Thuật toán sắp xếp chọn (selection sort)

Hình động sắp xếp chọn

Từ cái tên của thuật toán ta có thể đoán ngay được ý tưởng của thuật toán. Thật đúng như vậy, giả sử chúng ta muốn sắp xếp một danh sách (mảng) theo chiều tăng dần thì rõ ràng phần tử đầu tiên của danh sách sẽ là phần tử nhỏ nhất, phần tử tiếp theo là phần tử nhỏ thứ 2, tiếp nữa là phần tử nhỏ thứ 3,... đến hết. Như vậy, ta xét từng vị trí và chọn phần tử tương ứng với vị trí đó.

Algorithm: Thuật toán sắp xếp nổi bọt (bubble sort)

Minh họa

Sắp xếp nổi bọt là thuật toán sắp xếp đơn giản nhất và dễ hình dung nhất. Ý tưởng của thuật toán như sau: có một danh sách các phần tử để sắp xếp được danh sách này ta sẽ chuyển dần các phần tử "nhẹ" lên trên và các phần tử nặng "xuống" dưới. Ok, bây giờ chúng ta sẽ xem thuật toán được triển khai như thế nào trong ngôn ngữ lập trình nhé.

Python: Sắp xếp (sorting)

Sắp xếp

Sắp xếp là thao tác thường xuyên khi ta sử dụng phần mềm (ví dụ như trong excel ta sắp xếp các bản ghi theo rất nhiều tiêu chí mà ta mong đợi). Trong bài này, mình sẽ hướng dẫn các hàm sắp xếp được xây dựng sẵn của Python. Các post sau chúng ta sẽ tự xây dựng thuật toán sắp xếp cho riêng mình (các thuật toán sắp xếp gồm có: sắp xếp nổi bọt, chèn, chọn, nhanh,...)

Python: Tìm giá trị của biểu thức Taylor.

Định lí Taylor cho ta một đa thức xấp xỉ một hàm khả vi tại một điểm cho trước (gọi là đa thức Taylor của hàm đó) có hệ số chỉ phụ thuộc vào các giá trị của đạo hàm tại điểm đó. Định lí còn cho ta một đánh giá chính xác sai số của xấp x.

Trong bài này, chúng ta sẽ tính giá trị của e và e^x theo khai triển Taylor-Maclaurin. Trước hết, ta xem khai triển của e và e^x:

Python: Kiểu dữ liệu chuỗi

Kiểu chuỗi

Chuỗi là kiểu dữ liệu có mặt trong tất cả các ngôn ngữ lập trình và các thao tác trên chuỗi cũng được sử dụng rất thường xuyên. Chính vì vậy, bài này ta sẽ đi tìm hiểu tất cả mọi thứ về chuỗi trong Python.

Python: Một số ví dụ về hàm

Hàm

Bài trước, ta đã viết ba chương trình đơn giản đó là kiểm tra một số xem có phải là số nguyên tố, chính phương và hoàn hảo hay không? Tuy nhiên, đó là các chương trình rất đơn giản. Bài này, chúng ta sẽ sử dụng hàm để thực hiện công việc như bài trước.

Khái niệm hàm trong ngôn ngữ lập trình thì mình không phải giới thiệu lại. Bạn chỉ cần hiểu đơn giản hàm là một hộp đen thực hiện một công việc nào đó. Với đầu vào như thế nào thì sẽ được đầu ra tương ứng. Ví dụ, đầu vào của hộp đen số nguyên tố là 11 sẽ có kết quả là True, còn đầu vào là 12 sẽ có đầu ra là False. Vậy, chúng ta sẽ đi tìm hiểu cách chế tạo hộp đen bằng Python nhé.

Tự học Python: Một vài chương trình đơn giản.

Ở bài số 1, chúng ta đã cài đặt môi trường Python, môi trường lập trình và chạy chương trình đầu tiên. Bây giờ mình sẽ viết một số chương trình ví dụ. Đơn giản nhất là chương trình kiểm tra một số có phải là số nguyên tố, hoàn hảo và chính phương hay không (đây là các bài toán cơ bản và đơn giản nhất có thể.

Tự học Python: Cài đặt và viết chương trình đầu tiên

Mình không phải quảng bá nhiều về Python, chỉ biết rằng Python hiện đang ở vị trí thứ 5 (tham khảo) trong bảng xếp hạng và có chiều hướng tăng. Đồng thời, cộng đồng Python cũng kêu gào rằng Python code Python rất ngắn gọn và phải gõ phím rất ít khi viết cùng một chương trình ở các ngôn ngữ khác. Chính vì thế, có thể sẽ rất phù hợp với những người lười đấy (theo nghĩa đen luôn). Đề xem có đúng như lời cộng đồng Python nói không, thì chẳng có cách nào khác chúng ta đi tự học và cố gắng học trong 21 ngày nhé (dài quá không?).