Em mới học tới phần đệ quy quay lui có gặp 1 bài thế này :
cho 1 mảng các phần tử , liệt kê tất cả chuỗi con tăng dần dài nhất có trong mảng đó
vd :
V= {3, 1, 2, 3, 4, 6, 7, 9, 5, 4, 3, 4, 5, 6}
các chuỗi con có thể tìm được là : 1234 ,67,3456
code của em đây ạ :
static int str[] = {3, 1, 2, 3, 4, 6, 7, 9, 5, 4, 3, 4, 5, 6};
static boolean check[] = new boolean[str.length];
static int kq[] = new int[str.length];
static int dem = 0;
public static void main(String[] args) {
// sử dụng mảng check để kiểm tra phần tử đó đã được sử dụng để tạo chuỗi con chưa , true = chưa , false =rồi
for (int i = 0; i < str.length; i++) {
check[i] = true;
}
for (int i = 0; i < str.length - 1; i++) {
if (check[i]) {
if (str[i] == (str[i + 1] - 1)) {
kq[0] = str[i];
dequy(i, 1);
}
}
}
}
static void dequy(int phantu, int index) {
if ((phantu < str.length - 1) && (str[phantu] == (str[phantu + 1] - 1))) {
check[phantu + 1] = false;
kq[index] = str[phantu + 1];
dem++;
dequy(phantu + 1, index + 1);
} else {
String s = "";
if (dem >= 1) {
for (int j = 0; j < kq.length; j++) {
s += Integer.toString(kq[j]);
kq[j] = 0;
}
System.out.println(s);
dem = 0;
index = 0;
}
}
}
- Em muốn hỏi là bài này nếu ko dùng đệ quy thì sẽ phân tích giải thuật như thế nào ?
- Viết lại bài này dùng phương pháp quay lui?