Nhiệm vụ
Trong bảng chữ cái ngôn ngữ của bộ lạc «Tumba-Yumba» bốn chữ cái: "K", "L", "M" và "N". Cần hiển thị trên màn hình tất cả các từ gồm n chữ cái có thể được tạo từ các chữ cái trong bảng chữ cái này
Sự cố này là một sự cố brute-force bình thường có thể được rút gọn thành một sự cố nhỏ hơn.
Chúng ta sẽ lần lượt thay thế các chữ cái cho từ đó.
Vị trí đầu tiên của một từ có thể là một trong 4 chữ cái của bảng chữ cái (
K, L, M, N).
Đầu tiên, đặt chữ cái '
K' trước. Sau đó, để có được tất cả các biến thể có chữ cái đầu tiên '
K', bạn cần liệt kê tất cả sự kết hợp có thể có của các chữ cái trong
n-1 vị trí và .v.v. (xem hình)
Do đó, chúng tôi đã đưa ra một giải pháp đệ quy: trong một vòng lặp, duyệt qua tất cả các chữ cái đầu tiên có thể có (lần lượt đặt từng chữ cái của bảng chữ cái ở vị trí đầu tiên) và đối với mỗi trường hợp, hãy xây dựng tất cả các "đuôi" có thể có; độ dài n-1.
Lặp lại đệ quy các ký tự
Bạn cần dừng đệ quy và xuất từ đã hoàn thành khi phần còn lại trống (n = 0), tức là tất cả các chữ cái đã được chọn.
Quy trình đệ quy sẽ như sau:
def TumbaWords(từ, bảng chữ cái, n):
nếu n < 1:
in (từ)
trở lại
cho c trong bảng chữ cái:
TumbaWords(từ+c, bảng chữ cái, n - 1)