Tag: algorithm

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 algorithm và class 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] và 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] và 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 main và class Main.py cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo package algorithm và class 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] và 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] và 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 Algorithm và class 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] và 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] và 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 main và class Main.java cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo package algorithm và class 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] và 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] và 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.

Một số thuật toán cơ bản xung quanh số nguyên tố – 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ố kiến thức cơ bản xung quanh số nguyên tố.

Một số tự nhiên p (p > 1) là số nguyên tố nếu p có đúng 02 ước số là 1 và p.

Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, …

Chúng ta cùng nhau thực hiện một số giải thuật cơ bản bằng ngôn ngữ Java để giải quyết các bài toán con sau:

  • Kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không.
  • Liệt kê các số nguyên tố nằm trong phạm vi [1, n].

Kiểm tra tính nguyên tố

Giải thuật thứ nhất

Ý tưởng giải thuật

Chúng ta kiểm tra xem có tồn tại một số nguyên k (2 ≤ k ≤ n – 1) mà k là ước của n (n chia hết cho k) thì n không phải là số nguyên tố, ngược lại n là số nguyên tố.

Trên thực tế ta chỉ cần kiểm tra k từ 2 đến √n là được.

Bước 1.

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

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

Bước 2.

Chúng ta tạo package algorithm và class SoNguyenTo.java.

Chúng ta tiếp tục tạo phương thức kiemTraSNTFirst() với:

  • Tham số cho phương thức này là một số tự nhiên n.
  • Kiểu dữ liệu trả về là boolean. Phương thức trả về kết quả: (i) true nếu n là số nguyên tố; (ii) false nếu ngược lại.

Bước 3.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Những kỹ thuật lập trình cần chú ý:

  • Phương thức để tính căn bậc 2 của một số tự nhiên n là Math.sqrt().
  • Phương thức để lấy phần nguyên của một số thập phân là Math.round().
  • Thư viện Math định nghĩa các phương thức dùng tính toán các biểu thức toán học cơ bản. Các phương thức này đều là tĩnh nên được gọi trực tiếp bằng cú pháp Math.phương_thức().

Bước 4.

Chúng ta thực hiện thử nghiệm phương thức kiemTraSNTFirst() trong class Main.java như sau:

Bước 5.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Giải thuật thứ hai

Ý tưởng giải thuật

Chúng ta sẽ chỉ kiểm tra các số k có tính chất giống với một trong hai tính chất cơ bản sau của số nguyên tố:

  • Trừ số 2 và các số nguyên tố là số lẻ.
  • Trừ số 2, 3, các số nguyên tố có dạng 6k ± 1 (vì số có dạng 6k ± 2 thì chia hết cho 2, số có dạng 6k ± 3 thì chia hết cho 3).

Bước 1.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Bước 2.

Chúng ta thực hiện thử nghiệm phương thức kiemTraSNTSecond() trong class Main.java như sau:

Bước 3.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Liệt kê các số nguyên tố trong đoạn [1, N]

Giải thuật thứ nhất

Ý tưởng giải thuật

Chúng ta lần lượt xem xét các số m trong đoạn [1, n], rồi kiểm tra tính nguyên tố của m.

Bước 1.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Những kỹ thuật lập trình cần chú ý:

  • Java cung cấp cho chúng ta một số kiểu dữ liệu lưu trữ tập hợp các phần tử bên cạnh kiểu dữ liệu mảng. Chúng ta thường sử dụng một số dạng sau: (i) List để lưu trữ không giới hạn các phần tử có thể trùng nhau; (ii) Set để lưu trữ không giới hạn các phần tử không trùng nhau; (ii) Map để lưu trữ không giới hạn các phần tử theo từng cặp . Chúng ta sẽ dần tìm hiểu cụ thể hơn trong những bài tiếp theo.
  • Java cung cấp một phương pháp để xác định kiểu dữ liệu cho toàn bộ các phần tử trong danh sách: định nghĩa ngay từ ban đầu kiểu dữ liệu trong cặp dấu <>. Ví dụ ở đây là List.
  • Với tham số là một biến riêng lẻ, giá trị của tham số sẽ không bị thay đổi sau khi thực hiện phương thức.
  • Với tham số là một danh sách, các phần tử của danh sách có thể bị thay đổi sau khi thực hiện phương thức.

Bước 2.

Chúng ta thực hiện thử nghiệm phương thức lietKeSNTFirst() trong class Main.java như sau:

Những kỹ thuật lập trình cần chú ý:

  • Java cung cấp các dạng List khác nhau để chúng ta sử dụng tùy theo trường hợp: (i) ArrayList được sử dụng khi không quan tâm đến thứ tự trước sau của các phần tử; (ii) LinkedList được sử dụng khi quan tâm đến thứ tự trước sau của các phần tử.
  • Kiểu dữ liệu của các phần tử trong List đã được khai báo ban đầu thì không cần khai báo đối với ArrayList<>.
  • Số lượng phần tử của một danh sách là không giới hạn nên không cần khai báo trước số lượng phần tử ban đầu.

Bước 3.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Giải thuật thứ hai

Ý tưởng giải thuật

Chúng ta áp dụng sàng Eratosthenes (https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes ) để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên n:

  • Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,…, n).
  • Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
  • Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
  • Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p. Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

Bước 1.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Bước 2.

Chúng ta thực hiện thử nghiệm phương thức lietKeSNTSecond() trong class Main.java như sau:

Bước 3.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Tổng kết

Trong bài này, chúng ta đã cùng nhau tìm hiểu một số giải thuật cơ bản xung quanh số nguyên tố và thực hiện bằng ngôn ngữ Java.

Hy vọng rằng chúng ta có thể áp dụng phù hợp những kỹ thuật và chức năng này cho những bài tiếp theo.