Problem

11/12

Lặp lại các dòng #1

Theory Click to read/hide

Nhiệm vụ
Trong bảng chữ cái ngôn ngữ của bộ tộc "Tumba-Yumba"; bốn chữ cái: "K", "L", "M" và "N". Bạn cần hiển thị tất cả các từ bao 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).
Hãy đặ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 các vị trí n - 1 còn lại v.v. (xem hình).
Như vậy, bài toán rút gọn thành việc giải bốn bài toán có độ dài n - 1.
 
Lặp lại n ký tự một cách đệ quy
w[0]='K'; // lặp qua L-1 ký tự cuối cùng w[0]='L'; // lặp qua L-1 ký tự cuối cùng w[0]='M'; // lặp qua L-1 ký tự cuối cùng w[0]='N'; // lặp qua L-1 ký tự cuối cùng w - một chuỗi ký tự lưu trữ từ đang hoạt động.
Do đó, chúng ta có đệ quy. Chúng ta có thể sắp xếp lời giải của bài toán dưới dạng một thủ tục đệ quy. 
Nó vẫn còn để xác định khi nào đệ quy sẽ kết thúc? Khi tất cả các ký tự được đặt, nghĩa là số lượng ký tự được đặt là n. Trong trường hợp này, bạn cần hiển thị từ kết quả trên màn hình và thoát khỏi quy trình.

Chương trình C++ sẽ trông như thế này.
#include<iostream> sử dụng không gian tên std; void TumbaWords( string A, string &w, int N ) // w - tham số có thể thay đổi (kết quả chuỗi) // Thủ tục TumbaWords được truyền bảng chữ cái dưới dạng chuỗi ký tự, // từ word và số lượng ký tự đã được thiết lập (trước – 0). { int tôi; nếu (N == w.size()) {   // nếu tất cả các ký tự đã được đặt thành từ,     // thì cần xuất ra 1 chuỗi và kết thúc thủ tục cout << w<< kết thúc; trở lại; } cho ( i = 1; i < A.size(); i ++ ) {   // nếu điều kiện trên là sai (nghĩa là không phải tất cả các ký tự đều cách nhau,   // sau đó trong vòng lặp, chúng ta duyệt qua tất cả các ký tự trong bảng chữ cái và // luân phiên đặt ký tự vào không gian trống đầu tiên w[N] = A[i]; Từ Tumba ( A, w, N+1 ); } } chủ yếu() { intn; từ chuỗi; intn; cin>> N; từ.resize(n); // tăng chuỗi lên kích thước n TumbaWords("KLMN", từ, 0 ); }
LƯU Ý rằng w là một tham số có thể thay đổi (chuỗi kết quả)!

Problem

Trong bảng chữ cái ngôn ngữ của bộ tộc «tumba-yumba» bốn chữ cái: "K", "L", "M" và "N". Bạn cần hiển thị tất cả các từ bao 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.
(c) K.Yu. Polyakov

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <string>
#include <iostream>
using namespace std;

void TumbaWords( string A, string &w, int N )
{                      
}

main()
{
  string word;
  int n;
  cin>>n;
  word.resize(n);
  TumbaWords ( "KLMN", word, 0 );
}

     

Program check result

To check the solution of the problem, you need to register or log in!