JavaScript Object Notation – JSON

Giới thiệu

Trong nội dung bài này, chúng ta cùng tìm hiểu một định dạng biểu diễn dữ liệu quen thuộc là JSON.

JavaScript Object Notation (JSON) là một kiểu dữ liệu mở.

Kiểu dữ liệu này bao gồm chủ yếu là text, có thể đọc được theo dạng cặp: thuộc tínhgiá trị.

JSON là một kiểu dữ liệu trung gian được dùng để luân chuyển thông tin giữa các thành phần của một chương trình.

Đặc điểm – Cú pháp

Cấu trúc JSON:

  • 1 đối tượng là 1 hổn hợp của các cặp: thuộc tínhgiá trị. 1 đối tượng bắt đầu bởi dấu ngoặc đơn trái { và kết thúc với dấu ngoặc đơn phải }. Từng tên được theo sau bởi dấu 2 chấm : và các cặp thuộc tínhgiá trị được tách ra bởi dấu phẩy ,.
  • 1 mảng là 1 tập hợp các giá trị. 1 mảng bắt đầu bởi dấu ngoặc vuông trái [ và kết thúc với dấu ngoặc vuông phải ]. Các giá trị được cách nhau bởi dấu phẩy ,.
  • Những thuộc tính được chúng ta định nghĩa phù hợp với yêu cầu của chương trình.
  • 1 giá trị có thể là 1 chuỗi string trong những trích dẫn kép hay là 1 số, hay true hay false hay null, hay là 1 đối tượng hay là 1 mảng. Những cấu trúc này có thể đã được lồng vào nhau.

Biểu diễn dữ liệu

Chúng ta thực hiện biểu diễn dữ liệu trong JSON theo đặc tả trong các Hệ quản trị cơ sở dữ liệu.

Bước 1.

Chúng ta có đặc tả cơ sở dữ liệu trong PostgreSQL như sau:

Bước 2.

Chúng ta đặc tả file category.json cho bảng category có bao gồm cả dữ liệu như sau:

Bước 3.

Chúng ta đặc tả file product.json cho bảng product có bao gồm cả dữ liệu như sau:

Bước 4.

Chúng ta cũng có thể đặc tả file complex.json cho cả 02 bảng categoryproduct lồng nhau.

Chú ý rằng với cách này thì cần chú ý về độ lớn của dữ liệu và sự phức tạp trong quá trình truy xuất.

Kết luận

Trong bài này chúng ta đã cùng tìm hiểu sơ bộ về định dạng JSON để đặc tả và lưu trữ dữ liệu.

Trong các bài tiếp theo chúng ta sẽ cùng nhau tìm hiểu cách thức truy xuất định dạng JSON với những kỹ thuật lập trình phù hợp.

Extensible Markup Language – XML

Giới thiệu

Trong nội dung bài này, chúng ta cùng tìm hiểu một định dạng biểu diễn dữ liệu quen thuộc là XML.

XML (eXtensible Markup Language), nghĩa là “Ngôn ngữ đánh dấu mở rộng”, là ngôn ngữ đánh dấu với mục đích chung do World Wide Web Consortium (W3C) đề nghị.

Đây là một tập con được kế thừa từ Standard Generalized Markup Language (SGML), có khả năng mô tả nhiều loại dữ liệu khác nhau.

Mục đích chính của XML là đơn giản hóa việc chia sẻ dữ liệu giữa các platform và các hệ thống được kết nối với mạng Internet.

Chính vì vậy, XML có tác dụng rất lớn trong việc chia sẻ, trao đổi dữ liệu giữa các hệ thống.

Đặc điểm

Đặc trưng làm XML hữu ích:

  • XML được dùng cho dữ liệu có cấu trúc.
  • XML là có thể mở rộng: chúng ta có thể tạo các thẻ theo qui ước riêng để phù hợp với ứng dụng.
  • XML mang dữ liệu chứ không hiển thị: chúng ta có thể lưu giữ dữ liệu mà không quan tâm đến cái cách nó sẽ được hiển thị.
  • XML là một chuẩn chung: XML được phát triển bởi tổ chức World Wide Web Consortium (W3C) như một chuẩn mở.
  • Về trực quan, XML khá giống với HTML.
  • XML có thể đọc và phân tích nguồn dữ liệu khá dễ dàng nên nó được sử dụng với mục đích chính là trao đổi dữ liệu giữa các chương trình, các hệ thống khác nhau.

Cú pháp

Cú pháp XML cơ bản cho một phần tử là

<tên thuộc_tính=“giá trị”>nội dung</tên>

Ví dụ nội dung của một file XML bao gồm 02 dòng:

<?xml version=“1.0” encoding=“UTF-8”?>

<category_list>Đây là thông tin danh mục</category_list>

Dòng đầu tiên là Khai báo XML (XML declaration): đó là một dòng không bắt buộc, với nhiệm vụ thông báo phiên bản XML đang được sử dụng (thường là phiên bản 1.0), và còn có thể chứa thông tin về mã hóa ký tự và các phụ thuộc bên ngoài.

Phần còn lại của XML chứa các phần tử lồng nhau, một số phần tử trong đó có các thuộc tínhnội dung.

Một phần tử thường bao gồm hai thẻ (tag): một thẻ bắt đầu và một thẻ kết thúc.

Thẻ bắt đầu bao gồm một cái tên đặt trong một cặp ngoặc nhọn như: <category_list>.

Thẻ kết thúc bao gồm chính cái tên đó đặt trong một cặp ngoặc nhọn với một dấu gạch chéo đứng trước như: </category_list>.

Nội dung của phần tử là tất cả những gì nằm giữa thẻ bắt đầuthẻ kết thúc, bao gồm văn bản và các phần tử (con) khác.

Biểu diễn dữ liệu

Chúng ta thực hiện biểu diễn dữ liệu trong XML theo đặc tả trong các Hệ quản trị cơ sở dữ liệu.

Bước 1.

Chúng ta có đặc tả cơ sở dữ liệu trong PostgreSQL như sau:

Bước 2.

Chúng ta đặc tả file category.xml cho bảng category có bao gồm cả dữ liệu như sau:

Bước 3.

Chúng ta đặc tả file product.xml cho bảng product có bao gồm cả dữ liệu như sau:

Bước 4.

Chúng ta cũng có thể đặc tả file complex.xml cho cả 02 bảng categoryproduct lồng nhau.

Chú ý rằng với cách này thì cần chú ý về độ lớn của dữ liệu và sự phức tạp trong quá trình truy xuất.

Kết luận

Trong bài này chúng ta đã cùng tìm hiểu sơ bộ về định dạng XML để đặc tả và lưu trữ dữ liệu.

Trong các bài tiếp theo chúng ta sẽ cùng nhau tìm hiểu cách thức truy xuất định dạng XML từ với những kỹ thuật lập trình phù hợp.

Phương pháp sinh – PHP

Giới thiệu

Trong nội dung bài này, chúng ta cùng nhau tìm hiểu một số bài toán cơ bản về phương pháp sinh.

Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp.

Hai điều kiện để có thể áp dụng phương pháp sinh:

  • Xác định được một thứ tự trên tập các cấu hình tổ hợp. Từ đó suy ra cấu hình đầu tiên và cấu hình cuối cùng.
  • Xây dựng được thuật toán từ một cấu hình trung gian. Từ đó sinh ra cấu hình kế tiếp.

Những bài toán được tìm hiểu trong bài này:

  • Sinh các dãy nhị phân độ dài n.
  • Liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.
  • Liệt kê các hoán vị của {1, 2, …, n} theo thứ tự từ điển.

Thiết kế chương trình

Bước 1.

Chúng ta tạo một PHP Project trong Eclipse IDE và đặt tên là PHPAlgorithmGenerationMethod.

Chúng ta tạo file index.php.

Bước 2.

Chúng ta tạo folder algorithmclass GenerationAlgorithm.php.

Chúng ta cũng định nghĩa những phương thức chính để thực hiện các bài toán đặt ra.

Phương thức generateBinarySequences()

Phương thức generateBinarySequences() được đặc tả để sinh một dãy nhị phân độ dài n.

Một dãy nhị phân độ dài n là một dãy x[1…n] trong đó x[i] ∈ {0, 1} (∀i : 1 ≤ i ≤ n).

Ví dụ: Khi n = 3, chúng ta có 8 dãy nhị phân độ dài 3 được liệt kê lần lượt như sau:

{000; 001; 010; 011; 100; 101; 110; 111}

Như vậy dãy đầu tiên sẽ là 00…0 và dãy cuối cùng sẽ là 11…1.

Ý tưởng giải thuật:

  • Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), tìm số 0 gặp đầu tiên.
  • Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
  • Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị 0 cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một dãy nhị phân.

Chúng ta thêm dãy nhị phân này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi đã sinh ra dãy 11…1.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateBinarySequences() trong file index.php.

Phương thức generateSubSets()

Phương thức generateSubSets() được đặc tả để liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ: với n = 5, k = 3, chúng ta ta phải liệt kê đủ 10 tập con:

1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5} 6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10. {3, 4, 5}

Như vậy tập con đầu tiên là {1, 2, …, k}.

Tập con kết thúc là {n - k + 1, n - k + 2, …, n}.

Ý tưởng giải thuật:

  • Tìm từ cuối dãy lên đầu cho tới khi gặp một phần tử x[i] chưa đạt giới hạn trên n - k + i.
  • Nếu tìm thấy: (i) Tăng x[i] đó lên 1; (ii) Gán tất cả các phần tử sau x[i] bằng giới hạn dưới x[i-1] + 1.
  • Nếu không tìm thấy tức là mọi phần tử đã đạt giới hạn trên, đây là tập con cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm k phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một tập con.

Chúng ta thêm tập con này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi tất cả các phần tử đã đạt giới hạn trên.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateSubSets() trong file index.php.

Phương thức generatePermutation()

Phương thức generatePermutation() được đặc tả để liệt kê các hoán vị của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ với n = 4, ta phải liệt kê đủ 24 hoán vị:

1.1234 2.1243 3.1324 4.1342 5.1423 6.1432 7.2134 8.2143 9.2314 10.2341 11.2413 12.2431 13.3124 14.3142 15.3214 16.3241 17.3412 18.3421 19.4123 20.4132 21.4213 22.4231 23.4312 24.4321

Như vậy hoán vị đầu tiên sẽ là <1, 2, …, n>.

Hoán vị cuối cùng là <n, n-1, …, 1>.

Ý tưởng giải thuật:

  • Xác định đoạn cuối giảm dần dài nhất.
  • Xác định chỉ số i của phần tử x[i] đứng liền trước đoạn cuối đó.
  • Nếu tìm thấy chỉ số i như trên: (i) tìm phần tử x[k] nhỏ nhất thoả mãn điều kiện x[k] > x[i]; (ii) Đảo giá trị x[k]x[i]; (iii) Lật ngược thứ tự đoạn cuối giảm dần (từ x[i+1] đến x[k]) trở thành tăng dần.
  • Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một hoán vị.

Chúng ta thêm hoán vị này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện xem xét nếu chưa gặp phải hoán vị cuối.

Việc kiểm tra được thực hiện từ Bước 3.3.1 đến 3.3.3.

Bước 3.3.1.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.2.

Chúng ta lùi dần k.

Bước 3.3.3.

Chúng ta thực hiện đổi chỗ x[k]x[i].

Bước 3.3.4.

Chúng ta điều chỉnh những phần tử sau x[i].

Bước 3.4.

Thuật toán sinh dừng lại khi toàn bộ dãy giảm dần.

Thử nghiệm

Chúng ta thử nghiệm phương thức generatePermutation() trong file index.php.

Kết luận

Trong nội dung bài này, chúng ta đã cùng tìm hiểu một số bài toán con đối với thuật toán sinh để liệt kê một danh sách theo yêu cầu cho trước.

Hi vọng chúng ta có thể hiểu thêm về tư duy thuật toán cũng như một số các kỹ thuật lập trình PHP để áp dụng cho các bài khác.

Phương pháp sinh – Python

Giới thiệu

Trong nội dung bài này, chúng ta cùng nhau tìm hiểu một số bài toán cơ bản về phương pháp sinh.

Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp.

Hai điều kiện để có thể áp dụng phương pháp sinh:

  • Xác định được một thứ tự trên tập các cấu hình tổ hợp. Từ đó suy ra cấu hình đầu tiên và cấu hình cuối cùng.
  • Xây dựng được thuật toán từ một cấu hình trung gian. Từ đó sinh ra cấu hình kế tiếp.

Những bài toán được tìm hiểu trong bài này:

  • Sinh các dãy nhị phân độ dài n.
  • Liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.
  • Liệt kê các hoán vị của {1, 2, …, n} theo thứ tự từ điển.

Thiết kế chương trình

Bước 1.

Chúng ta tạo một PyDev Project trong Eclipse IDE và đặt tên là PythonAlgorithmGenerationMethod.

Chúng ta tiếp tục tạo package mainclass Main.py cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo package algorithmclass GenerationAlgorithm.py.

Chúng ta cũng định nghĩa những phương thức chính để thực hiện các bài toán đặt ra.

Phương thức generateBinarySequences()

Phương thức generateBinarySequences() được đặc tả để sinh một dãy nhị phân độ dài n.

Một dãy nhị phân độ dài n là một dãy x[1…n] trong đó x[i] ∈ {0, 1} (∀i : 1 ≤ i ≤ n).

Ví dụ: Khi n = 3, chúng ta có 8 dãy nhị phân độ dài 3 được liệt kê lần lượt như sau:

{000; 001; 010; 011; 100; 101; 110; 111}

Như vậy dãy đầu tiên sẽ là 00…0 và dãy cuối cùng sẽ là 11…1.

Ý tưởng giải thuật:

  • Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), tìm số 0 gặp đầu tiên.
  • Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
  • Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng.

Bước 1 – 2.

Chúng ta định nghĩa một mảng gồm n phần tử.

Chúng ta gán giá trị 0 cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một dãy nhị phân.

Chúng ta thêm dãy nhị phân này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi đã sinh ra dãy 11…1.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateBinarySequences() trong class Main.py.

Phương thức generateSubSets()

Phương thức generateSubSets() được đặc tả để liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ: với n = 5, k = 3, chúng ta ta phải liệt kê đủ 10 tập con:

1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5} 6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10. {3, 4, 5}

Như vậy tập con đầu tiên là {1, 2, …, k}.

Tập con kết thúc là {n - k + 1, n - k + 2, …, n}.

Ý tưởng giải thuật:

  • Tìm từ cuối dãy lên đầu cho tới khi gặp một phần tử x[i] chưa đạt giới hạn trên n - k + i.
  • Nếu tìm thấy: (i) Tăng x[i] đó lên 1; (ii) Gán tất cả các phần tử sau x[i] bằng giới hạn dưới x[i-1] + 1.
  • Nếu không tìm thấy tức là mọi phần tử đã đạt giới hạn trên, đây là tập con cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm k phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một tập con.

Chúng ta thêm tập con này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi tất cả các phần tử đã đạt giới hạn trên.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateSubSets() trong class Main.py.

Phương thức generatePermutation()

Phương thức generatePermutation() được đặc tả để liệt kê các hoán vị của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ với n = 4, ta phải liệt kê đủ 24 hoán vị:

1.1234 2.1243 3.1324 4.1342 5.1423 6.1432 7.2134 8.2143 9.2314 10.2341 11.2413 12.2431 13.3124 14.3142 15.3214 16.3241 17.3412 18.3421 19.4123 20.4132 21.4213 22.4231 23.4312 24.4321

Như vậy hoán vị đầu tiên sẽ là <1, 2, …, n>.

Hoán vị cuối cùng là <n, n-1, …, 1>.

Ý tưởng giải thuật:

  • Xác định đoạn cuối giảm dần dài nhất.
  • Xác định chỉ số i của phần tử x[i] đứng liền trước đoạn cuối đó.
  • Nếu tìm thấy chỉ số i như trên: (i) tìm phần tử x[k] nhỏ nhất thoả mãn điều kiện x[k] > x[i]; (ii) Đảo giá trị x[k]x[i]; (iii) Lật ngược thứ tự đoạn cuối giảm dần (từ x[i+1] đến x[k]) trở thành tăng dần.
  • Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một hoán vị.

Chúng ta thêm hoán vị này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện xem xét nếu chưa gặp phải hoán vị cuối.

Việc kiểm tra được thực hiện từ Bước 3.3.1 đến 3.3.3.

Bước 3.3.1.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.2.

Chúng ta lùi dần k.

Bước 3.3.3.

Chúng ta thực hiện đổi chỗ x[k]x[i].

Bước 3.3.4.

Chúng ta điều chỉnh những phần tử sau x[i].

Bước 3.4.

Thuật toán sinh dừng lại khi toàn bộ dãy giảm dần.

Thử nghiệm

Chúng ta thử nghiệm phương thức generatePermutation() trong class Main.py.

Kết luận

Trong nội dung bài này, chúng ta đã cùng tìm hiểu một số bài toán con đối với thuật toán sinh để liệt kê một danh sách theo yêu cầu cho trước.

Hi vọng chúng ta có thể hiểu thêm về tư duy thuật toán cũng như một số các kỹ thuật lập trình Python để áp dụng cho các bài khác.

Phương pháp sinh – Csharp

Giới thiệu

Trong nội dung bài này, chúng ta cùng nhau tìm hiểu một số bài toán cơ bản về phương pháp sinh.

Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp.

Hai điều kiện để có thể áp dụng phương pháp sinh:

  • Xác định được một thứ tự trên tập các cấu hình tổ hợp. Từ đó suy ra cấu hình đầu tiên và cấu hình cuối cùng.
  • Xây dựng được thuật toán từ một cấu hình trung gian. Từ đó sinh ra cấu hình kế tiếp.

Những bài toán được tìm hiểu trong bài này:

  • Sinh các dãy nhị phân độ dài n.
  • Liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.
  • Liệt kê các hoán vị của {1, 2, …, n} theo thứ tự từ điển.

Thiết kế chương trình

Bước 1.

Chúng ta tạo một Console Project trong MonoDevelop và đặt tên là CsharpAlgorithmGenerationMethod.

Class Program.cs cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo folder Algorithmclass GenerationAlgorithm.cs.

Chúng ta cũng định nghĩa những phương thức chính để thực hiện các bài toán đặt ra.

Phương thức GenerateBinarySequences()

Phương thức GenerateBinarySequences() được đặc tả để sinh một dãy nhị phân độ dài n.

Một dãy nhị phân độ dài n là một dãy x[1…n] trong đó x[i] ∈ {0, 1} (∀i : 1 ≤ i ≤ n).

Ví dụ: Khi n = 3, chúng ta có 8 dãy nhị phân độ dài 3 được liệt kê lần lượt như sau:

{000; 001; 010; 011; 100; 101; 110; 111}

Như vậy dãy đầu tiên sẽ là 00…0 và dãy cuối cùng sẽ là 11…1.

Ý tưởng giải thuật:

  • Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), tìm số 0 gặp đầu tiên.
  • Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
  • Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị 0 cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một dãy nhị phân.

Chúng ta thêm dãy nhị phân này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi đã sinh ra dãy 11…1.

Thử nghiệm

Chúng ta thử nghiệm phương thức GenerateBinarySequences() trong class Program.cs.

Phương thức GenerateSubSets()

Phương thức GenerateSubSets() được đặc tả để liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ: với n = 5, k = 3, chúng ta ta phải liệt kê đủ 10 tập con:

1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5} 6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10. {3, 4, 5}

Như vậy tập con đầu tiên là {1, 2, …, k}.

Tập con kết thúc là {n - k + 1, n - k + 2, …, n}.

Ý tưởng giải thuật:

  • Tìm từ cuối dãy lên đầu cho tới khi gặp một phần tử x[i] chưa đạt giới hạn trên n - k + i.
  • Nếu tìm thấy: (i) Tăng x[i] đó lên 1; (ii) Gán tất cả các phần tử sau x[i] bằng giới hạn dưới x[i-1] + 1.
  • Nếu không tìm thấy tức là mọi phần tử đã đạt giới hạn trên, đây là tập con cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm k phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một tập con.

Chúng ta thêm tập con này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi tất cả các phần tử đã đạt giới hạn trên.

Thử nghiệm

Chúng ta thử nghiệm phương thức GenerateSubSets() trong class Program.cs.

Phương thức GeneratePermutation()

Phương thức GeneratePermutation() được đặc tả để liệt kê các hoán vị của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ với n = 4, ta phải liệt kê đủ 24 hoán vị:

1.1234 2.1243 3.1324 4.1342 5.1423 6.1432 7.2134 8.2143 9.2314 10.2341 11.2413 12.2431 13.3124 14.3142 15.3214 16.3241 17.3412 18.3421 19.4123 20.4132 21.4213 22.4231 23.4312 24.4321

Như vậy hoán vị đầu tiên sẽ là <1, 2, …, n>.

Hoán vị cuối cùng là <n, n-1, ..., 1>.

Ý tưởng giải thuật:

  • Xác định đoạn cuối giảm dần dài nhất
  • Xác định chỉ số i của phần tử x[i] đứng liền trước đoạn cuối đó.
  • Nếu tìm thấy chỉ số i như trên: (i) tìm phần tử x[k] nhỏ nhất thoả mãn điều kiện x[k] > x[i]; (ii) Đảo giá trị x[k]x[i]; (iii) Lật ngược thứ tự đoạn cuối giảm dần (từ x[i+1] đến x[k]) trở thành tăng dần.
  • Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùng

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một hoán vị.

Chúng ta thêm hoán vị này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện xem xét nếu chưa gặp phải hoán vị cuối.

Việc kiểm tra được thực hiện từ Bước 3.3.1 đến 3.3.3.

Bước 3.3.1.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.2.

Chúng ta lùi dần k.

Bước 3.3.3.

Chúng ta thực hiện đổi chỗ x[k]x[i].

Bước 3.3.4.

Chúng ta điều chỉnh những phần tử sau x[i].

Bước 3.4.

Thuật toán sinh dừng lại khi toàn bộ dãy giảm dần.

Thử nghiệm

Chúng ta thử nghiệm phương thức GeneratePermutation() trong class Program.cs.

Kết luận

Trong nội dung bài này, chúng ta đã cùng tìm hiểu một số bài toán con đối với thuật toán sinh để liệt kê một danh sách theo yêu cầu cho trước.

Hi vọng chúng ta có thể hiểu thêm về tư duy thuật toán cũng như một số các kỹ thuật lập trình Csharp để áp dụng cho các bài khác.

Phương pháp sinh – Java

Giới thiệu

Trong nội dung bài này, chúng ta cùng nhau tìm hiểu một số bài toán cơ bản về phương pháp sinh.

Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp.

Hai điều kiện để có thể áp dụng phương pháp sinh:

  • Xác định được một thứ tự trên tập các cấu hình tổ hợp. Từ đó suy ra cấu hình đầu tiên và cấu hình cuối cùng.
  • Xây dựng được thuật toán từ một cấu hình trung gian. Từ đó sinh ra cấu hình kế tiếp.

Những bài toán được tìm hiểu trong bài này:

  • Sinh các dãy nhị phân độ dài n.
  • Liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.
  • Liệt kê các hoán vị của {1, 2, …, n} theo thứ tự từ điển.

Thiết kế chương trình

Bước 1.

Chúng ta tạo một Java Project trong Eclipse IDE và đặt tên là JavaAlgorithmGenerationMethod.

Chúng ta tiếp tục tạo package mainclass Main.java cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo package algorithmclass GenerationAlgorithm.java.

Chúng ta cũng định nghĩa những phương thức chính để thực hiện các bài toán đặt ra.

Phương thức generateBinarySequences()

Phương thức generateBinarySequences() được đặc tả để sinh một dãy nhị phân độ dài n.

Một dãy nhị phân độ dài n là một dãy x[1…n] trong đó x[i] ∈ {0, 1} (∀i : 1 ≤ i ≤ n).

Ví dụ: Khi n = 3, chúng ta có 8 dãy nhị phân độ dài 3 được liệt kê lần lượt như sau:

{000; 001; 010; 011; 100; 101; 110; 111}

Như vậy dãy đầu tiên sẽ là 00…0 và dãy cuối cùng sẽ là 11…1.

Ý tưởng giải thuật:

  • Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), tìm số 0 gặp đầu tiên.
  • Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.
  • Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị 0 cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một dãy nhị phân.

Chúng ta thêm dãy nhị phân này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi đã sinh ra dãy 11…1.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateBinarySequences() trong class Main.java.

Phương thức generateSubSets()

Phương thức generateSubSets() được đặc tả để liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ: với n = 5, k = 3, chúng ta ta phải liệt kê đủ 10 tập con:

1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5} 6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10.{3, 4, 5}

Như vậy tập con đầu tiên là {1, 2, …, k}.

Tập con kết thúc là {n - k + 1, n - k + 2, …, n}.

Ý tưởng giải thuật:

  • Tìm từ cuối dãy lên đầu cho tới khi gặp một phần tử x[i] chưa đạt giới hạn trên n - k + i.
  • Nếu tìm thấy: (i) Tăng x[i] đó lên 1; (ii) Gán tất cả các phần tử sau x[i] bằng giới hạn dưới x[i-1] + 1.
  • Nếu không tìm thấy tức là mọi phần tử đã đạt giới hạn trên, đây là tập con cuối cùng.

Bước 1.

Chúng ta định nghĩa một mảng gồm k phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một tập con.

Chúng ta thêm tập con này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi tất cả các phần tử đã đạt giới hạn trên.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateSubSets() trong class Main.java.

Phương thức generatePermutation()

Phương thức generatePermutation() được đặc tả để liệt kê các hoán vị của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ với n = 4, ta phải liệt kê đủ 24 hoán vị:

1.1234 2.1243 3.1324 4.1342 5.1423 6.1432 7.2134 8.2143 9.2314 10.2341 11.2413 12.2431 13.3124 14.3142 15.3214 16.3241 17.3412 18.3421 19.4123 20.4132 21.4213 22.4231 23.4312 24.4321

Như vậy hoán vị đầu tiên sẽ là 〈1, 2, …, n〉.

Hoán vị cuối cùng là 〈n, n-1, …, 1〉.

Ý tưởng giải thuật:

  • Xác định đoạn cuối giảm dần dài nhất
  • Xác định chỉ số i của phần tử x[i] đứng liền trước đoạn cuối đó.
  • Nếu tìm thấy chỉ số i như trên: (i) tìm phần tử x[k] nhỏ nhất thoả mãn điều kiện x[k] > x[i]; (ii) Đảo giá trị x[k]x[i]; (iii) Lật ngược thứ tự đoạn cuối giảm dần (từ x[i+1] đến x[k]) trở thành tăng dần.
  • Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùng

Bước 1.

Chúng ta định nghĩa một mảng gồm n phần tử.

Bước 2.

Chúng ta gán giá trị là chỉ số vị trí tương ứng cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một hoán vị.

Chúng ta thêm hoán vị này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện xem xét nếu chưa gặp phải hoán vị cuối.

Việc kiểm tra được thực hiện từ Bước 3.3.1 đến 3.3.3.

Bước 3.3.1.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.2.

Chúng ta lùi dần k.

Bước 3.3.3.

Chúng ta thực hiện đổi chỗ x[k]x[i].

Bước 3.3.4.

Chúng ta điều chỉnh những phần tử sau x[i].

Bước 3.4.

Thuật toán sinh dừng lại khi toàn bộ dãy giảm dần.

Thử nghiệm

Chúng ta thử nghiệm phương thức generatePermutation() trong class Main.java.

Kết luận

Trong nội dung bài này, chúng ta đã cùng tìm hiểu một số bài toán con đối với thuật toán sinh để liệt kê một danh sách theo yêu cầu cho trước.

Hi vọng chúng ta có thể hiểu thêm về tư duy thuật toán cũng như một số các kỹ thuật lập trình Java để áp dụng cho các bài khác.

Thiết kế mô hình 3 lớp kết hợp Kết nối và truy vấn Cơ sở dữ liệu theo phương pháp Prepared Statement – Nội dung 3 – Kỹ thuật lập trình – Phần 2 – Tầng 2 – PHP

Giới thiệu

Trong nhóm bài này, chúng ta cùng nhau tìm hiểu việc thiết kế một kiến trúc để lập trình phần mềm theo mô hình 3 lớp.

Những nội dung chính sẽ được trình bày trong nhóm bài:

  • Thiết lập một cơ sở dữ liệu cơ bản trong PostgreSQL để áp dụng trong toàn bộ nhóm bài. Chúng ta có thể tham khảo để tự thực hiện đối với những hệ quản trị cơ sở dữ liệu khác như: MySQL / MariaDB; SQLServer; Oracle; …
  • Thiết kế kiến trúc lập trình phần mềm theo mô hình 3 lớp. Chúng ta cũng sẽ áp dụng một chút kiến thức về lập trình hướng đối tượng ở đây.
  • Kỹ thuật kết nối và truy vấn cơ sở dữ liệu theo phương pháp Prepared Statement. Đây là phương pháp được ưu tiên khuyến khích hơn phương pháp thông thường.
  • Những kỹ thuật lập trình cụ thể sẽ được trình bày lần lượt với các ngôn ngữ: Java / C# / Python / PHP.

Nội dung chính của bài này là trình bày phần thứ hai và tập trung vào Tầng 2 trong nội dung về kỹ thuật lập trình với ngôn ngữ PHP:

  • Phần 1. Xây dựng kiến trúc tổng quan của mô hình 3 lớp.
  • Phần 2. Kỹ thuật lập trình cụ thể cho từng tầng trong kiến trúc mô hình 3 lớp.

Class BaseService

Bước 1.

Chúng ta thiết kế lớp cơ sở BaseService như sau:

Bước 2.

Chúng ta đặc tả phương thức createConnection() đối với tác vụ kết nối đến PostgreSQL:

Bước 3.

Chúng ta đặc tả các phương thức chính trong class BaseService:

Class CategoryService

Chúng ta thiết kế lớp dẫn xuất CategoryService như sau:

Class ProductService

Chúng ta thiết kế lớp dẫn xuất ProductService như sau:

Kết luận

Trong bài này, chúng ta cùng nhau tìm hiểu việc thực hiện kỹ thuật lập trình cho phần thứ hai và tập trung vào Tầng 2.

Chúng ta có thể áp dụng những kiến thức trong nhóm bài để thực hiện một số bài tập:

  • Thêm / xóa / sửa / truy vấn dữ liệu trong bảng categoryproduct theo những yêu cầu thực tế khác nhau.
  • Thay đổi cơ sở dữ liệu PostgreSQL bởi các cơ sở dữ liệu khác: MySQL / MariaDB; Oracle; …

Nhóm bài này sẽ trở thành một trong những kiến thức nền để thực hiện các dạng phần mềm: Desktop / Web Application.