Module: (C++) 재귀


Problem

11/12

라인 #1 반복

Theory Click to read/hide

과제
Tumba-Yumba 부족 언어의 알파벳으로; 네 글자: "K", "L", "M" 및 "N". 이 알파벳의 문자로 만들 수 있는 n개의 문자로 구성된 모든 단어를 표시해야 합니다.

문제는 더 작은 문제로 축소될 수 있는 일반적인 무차별 대입 문제입니다.
단어를 순차적으로 문자로 대체합니다.
단어의 첫 번째 위치는 알파벳 4자(K. L, M, N) 중 하나일 수 있습니다.
문자 K를 먼저 넣겠습니다. 그런 다음 첫 번째 문자 K가 있는 모든 변형을 가져오려면 나머지 n - 1 위치 등에서 문자의 가능한 모든 조합을 열거해야 합니다. (그림 참조).
따라서 문제는 길이가 n - 1인 네 가지 문제를 해결하는 것으로 축소됩니다.
 
n자를 재귀적으로 반복
w[0]='K';; // 마지막 L-1 문자를 반복합니다. w[0]='L';; // 마지막 L-1 문자를 반복합니다. w[0]='M';; // 마지막 L-1 문자를 반복합니다. w[0]='N'; // 마지막 L-1 문자를 반복합니다. w - 작업 단어를 저장하는 문자열.
따라서 우리는 재귀를 얻었습니다. 재귀 절차의 형태로 문제의 해결책을 마련할 수 있습니다. 
재귀가 언제 끝날지 결정하는 것이 남아 있습니까? 모든 문자가 설정된 경우, 즉 설정된 문자의 수는 n입니다. 이 경우 결과 단어를 화면에 표시하고 절차를 종료해야 합니다.

C++ 프로그램은 다음과 같습니다.
<사업부> #include<iostream> 네임스페이스 표준 사용; void TumbaWords( string A, string &w, int N ) // w - 변경 가능한 매개변수(문자열 결과) // TumbaWords 프로시저는 알파벳을 문자열로 전달하고, // 단어 단어와 이미 설정된 문자 수(앞에 – 0). { 정수 i; if (N == w.size()) {   // 모든 문자가 이미 해당 단어로 설정된 경우     // 그런 다음 문자열을 출력하고 프로시저를 종료해야 합니다. cout << w<< 끝; 반품; } for ( i = 1; i < A.size(); i ++ ) {   // 위의 조건이 false인 경우(즉, 모든 문자가 간격을 두지 않고,   // 그런 다음 루프에서 알파벳의 모든 문자를 살펴보고 // 번갈아 가며 첫 번째 여유 공간에 문자를 놓습니다. w[N] = A[i]; TumbaWords( A, w, N+1 ); } } 기본() { 정수; 스트링워드; 정수; cin>> N; word.resize(n); // 문자열을 크기 n으로 증가 TumbaWords( "KLMN", 워드, 0 ); }
참고 w는 변경 가능한 매개변수(결과 문자열)입니다!

Problem

"tumba-yumba" 부족 언어의 알파벳으로; 네 글자: "K", "L", "M" 및 "N". 이 알파벳의 문자로 만들 수 있는 n개의 문자로 구성된 모든 단어를 표시해야 합니다.
(c) 케이유. 폴리야코프