라인 #1 반복
과제
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) 케이유. 폴리야코프