Thuật toán sinh
1. Cài đặt thuật toán sinh chuỗi nhị phân độ dài n bằng ngôn ngữ Java
package chap02;
public class GenerateBinaryDemo {
/**
* Main method.<br>
*
* Thực hiện sinh chuỗi nhị phân có chiều dài n (n = 4) và in ra màn hình.
*/
public static void main(String[] args) {
GenerateBinary objGenerate = new GenerateBinary(4);
objGenerate.GenerBinary();
}
}
class GenerateBinary {
// Các thuộc tính của lớp GenerateBinary
private int a[];
private int n;
private int i;
private int count = 1;
public int getN() {
return n;
}
public void setN(int n) {
this.n = n;
}
public GenerateBinary(int n0) {
this.n = n0;
a = new int[this.n];
for (int j = 0; j < this.n; j++) {
a[j] = 0;
}
}
/**
* Hiển thị dãy nhị phân độ dài n
*/
public void display() {
for (int j = 0; j < n; j++) {
System.out.print(" " + a[j]);
}
System.out.print("\n");
}
/**
* Hàm sinh dãy nhị phân độ dài n
*/
public void GenerBinary() {
// In ra cấu hình hiện tại
do {
i = n - 1;
System.out.print("Hoán vị thứ " + count);
display();
while (i >= 0 && a[i] == 1)
i = i - 1;
count++;
if (i >= 0) {
a[i] = 1;
for (int j = i + 1; j < n; j++)
a[j] = 0;
}
} while (i >= 0);
}
}
2. Cài đặt thuật toán sinh hoán vị bằng ngôn ngữ Java
package chap02;
public class HoanViDemo {
/**
* @param args
*/
public static void main(String[] args) {
HoanVi objHoanVi = new HoanVi(4);
objHoanVi.GenerateHoanVi();
}
}
class HoanVi {
private int a[];
private int n;
private int i;
public int getN() {
return n;
}
public void setN(int n) {
this.n = n;
}
/**
* Hàm khởi tạo
*/
public HoanVi(int n0) {
this.n = n0;
a = new int[this.n + 1];
for (int j = 1; j <= n; j++)
a[j] = j;
}
/**
* Hàm hiển thị
*/
public void display() {
for (int j = 1; j <= n; j++) {
System.out.print(a[j] + " ");
}
System.out.println();
}
public void GenerateHoanVi() {
int count = 1;
do {
System.out.print("Bước " + count + " ");
display();
i = n - 1;
while ((i > 0) && (a[i] > a[i + 1]))
i--;
if (i > 0) {
int k = n;
while (a[k] < a[i])
k = k - 1;
int temps = a[i];
a[i] = a[k];
a[k] = temps;
int r = n;
int s = i + 1;
while (r > s) {
int temp = a[s];
a[s] = a[r];
a[r] = temp;
r = r - 1;
s = s + 1;
}
}
count++;
} while (this.i > 0);
}
}
3. Cài đặt thuật toán sinh tổ hợp chập k của n phần tử bằng ngôn ngữ Java
package chap02;
public class ToHopDemo {
/**
* Hàm main.<br>
*
* @param args (not use)
*/
public static void main(String[] args) {
ToHop objToHop = new ToHop(3, 4);
objToHop.SinhToHop();
}
}
/*
* Định nghĩa lớp tổ hợp
*/
class ToHop {
private int a[];
private int k;
private int n;
private int i;
/**
* Hàm khởi tạo với điều kiện k < n.
* @param k (k < n)
* @param n
*/
public ToHop(int k, int n) {
this.k = k;
this.n = n;
a = new int[n + 1];
for (int j = 1; j <= k; j++) {
a[j] = j;
}
}
/**
* Hàm hiển thị kết quả
*/
public void display() {
for (int j = 1; j <= k; j++) {
System.out.print(a[j] + " ");
}
System.out.println();
}
/**
* Hàm sinh tổ hợp
*/
public void SinhToHop() {
do {
display();
i = k;
while ((i > 0) && (a[i] == n - k + i))
i = i - 1;
a[i] = a[i] + 1;
for (int j = i + 1; j <= k; j++)
a[j] = a[i] + j - i;
} while (i > 0);
}
}
Ngoài ra cũng có thể cài đặt 3 thuật toán trên bằng phương pháp quay lui như sau
1) Thuật toán sinh chuỗi nhị phân độ dài n
package chap02;
public class BinaryBackingDemo {
public static void main(String[] args) {
System.out.println("Sinh chuỗi nhị phân.");
BinaryBacking objBinaryBack = new BinaryBacking(10);
objBinaryBack.GenerateString(0);
}
}
class BinaryBacking {
private int n;
private int b[];
int count = 1;
/**
* Hàm khởi tạo
*/
public BinaryBacking(int n0) {
this.n = n0;
b = new int[this.n];
}
public void display() {
for (int j = 0; j < n; j++) {
System.out.print(b[j]+" ");
}
System.out.print("\n");
}
/**
* Hàm sinh chuỗi nhị phân
* @param i
*/
public void GenerateString(int i) {
int j;
count++;
for (j = 0; j <= 1; j++) {
b[i] = j;
if (i == n-1){
System.out.print(count+" ");
display();
}
else
GenerateString(i + 1);
}
}
}
2) Thuật toán sinh tổ hợp
package chap02;
public class ToHopBackTrakingDemo {
/**
* Hàm main
*/
public static void main(String[] args) {
System.out.println("Liệt kê số tổ hợp.");
ToHopBackTraking objToHopBackTraking = new ToHopBackTraking(3, 5);
objToHopBackTraking.backTrackingToHop(1);
}
}
class ToHopBackTraking {
private int a[];
private int n;
private int k;
/**
* Hàm khởi tạo.
*
* @param k
* (số phần tử tập con)
* @param n
* (số phần tử của tập)
*/
public ToHopBackTraking(int k, int n) {
this.n = n;
this.k = k;
a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = i;
}
}
/**
* Hàm hiển thị
*/
public void display() {
for (int i = 1; i <= k; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
/**
* Hàm quay lui liệt kê sinh tổ hợp
*/
public void backTrackingToHop(int i) {
for (int j = a[i - 1] + 1; j <= n - k + i; j++) {
a[i] = j;
if (i == k)
display();
else
backTrackingToHop(i + 1);
}
}
}
Post a Comment