(Trang 61)
| Sau bài này em sẽ:
|
|
Theo em kĩ thuật duyệt quay lui thường được áp dụng cho những loại bài toán nào? Em có thể nêu ra một vài ví dụ không? |
NHIỆM VỤ 1
Phân tích chuỗi ADN gồm chuỗi các nucleotit thuộc bốn dạng A, T, G, và X. Viết chương trình in ra tất cả các dạng mạch đơn của một đoạn phân tử ADN với chiều dài gồm n nucleotit, trong đó n được người dùng nhập từ bàn phím. Lưu ý đo sự bùng nổ của tổ hợp, chỉ nên kiểm thử chương trình với số n nhỏ hơn 10.
Hướng dẫn:
Phân tích:
Bài toán là tổng quát của bài toán sinh các dãy nhị phân mà chúng ta đã biết. Điểm khác biệt là cần sinh tổ hợp của 4 phần tử "A", "T", "G", "X". Chúng ta định nghĩa dictDNA là xấu nhị phân "ATGX" lưu các kí tự từ điển DNA.
Chúng ta sẽ thiết lập hàm sinh các dãy nucleotit này theo kĩ thuật quay lui, kết quả lưu trong dãy A. Dãy A ban đầu được khởi tạo bao gồm n kí tự rỗng. Hàm sinh dãy nucleotit là genDNASection(A, k) có tính năng sinh các phần tử tại vị trí thứ k.
Chương trình 1:
1 # Hàm trìinh đệ quy sinh các chuỗi ADN
2 def genDNASection(A,k):
3 if k == n:
4 print(A)
5 else:
6 for i in range(4):
7 A[k] = i
8 genDNASection(A,k+1)
10 #Chương trình chính
11 n = int(input("Hãy nhập độ dài đoạn ADN:"))
12 dictDNA = "ATGX"
13 A = [''] * n
14 genDNASection(A,0)
Giải thích:
– Tại dòng 13, khởi tạo mảng biểu diễn chuỗi ADN gồm n kí tự rỗng, rồi gọi hàm đệ quy ở dòng 14.
(Trang 62)
Trong hàm genDNASection, tham số k thể hiện vị trí nucleotit đã được thiết lập. Nếu k bằng chiều dài n thì đã hoàn thành 1 nghiệm bài toán (là chuỗi ADN gồm n nucleotit). Kiến chương trình sẽ in ra ở dòng 4. Nếu k < n thì lần lượt gán phần tử thứ k dòng A với 4 loại nucleotit (ATGX) và gọi đệ quy hàm genDNASection để sinh phần tử tiếp theo.
NHIỆM VỤ 2
Một câu trong các ngôn ngữ tự nhiên được xây dựng bằng cách sắp xếp các từ vựng lại với nhau. Xét trường hợp đơn giản: cho một tập hợp từ vựng, hãy viết chương trình sinh ra các câu văn gồm tất cả các từ đó, mỗi từ chỉ xuất hiện một lần.
Hướng dẫn:
Phân tích: Chúng ta có thể giải quyết bài toán sinh ra các câu văn ở trên bằng cách bắt đầu với một câu gồm tất cả các từ đã cho trong từ điển, sau đó thực hiện duyệt quay lui để hoán vị tất cả các vị trí của các từ.
Chương trình 2:
1 # Định nghĩa hàm đệ quy duyệt quay lui sinh ra các câu
2def genSentence(words, dictionary, k):
3 if k == len(dictionary):
4 sentence = ''.join(words) # Sinh câu từ danh sách từ vựng
5 print(sentence)
6 else:
7 for w in dictionary:
8 if not w in words:
9 words.append(w)
10 genSentence(words, dictionary, k + 1)
11 words.pop()
Chương trình chính sẽ chạy như sau:
1 dictionary = ["tôi", "quyết", "bạn"]
2 words = []
3 genSentence(words, dictionary, 0)
LUYỆN TẬP
1. Sửa lại chương trình trong Nhiệm vụ 1 với yêu cầu thay đổi là cần in ra kết quả là các xấu kí tự chỉ bao gồm các kí tự "A", "T", "G", "X".
2. Trong Nhiệm vụ 2, động tác "quay lui" nằm ở đâu? Việc hoán vị được thực hiện như thế nào?
VẬN DỤNG
1. Viết chương trình sử dụng kĩ thuật duyệt quay lui để kiểm tra xem một biểu thức có hợp lệ về sử dụng các dấu ngoặc đơn hay không.
2. Viết chương trình in ra tất cả các hoán vị của tập hợp S = {1, 2, ..., n} với n được nhập từ bàn phím.
3. Cho các hệ số ak, ak-1, ..., a1, a0, hãy viết chương trình sinh tất cả các đa thức bậc k có thể thành lập từ các hệ số trên, mỗi hệ số sử dụng một lần. Mỗi vị dụ của đa thức trên là akxk + ak-1xk-1 + ... + a1x + a0.
