C++ 함수 재귀에 대한 자세한 설명: 조합 문제를 재귀적으로 해결

재귀는 함수가 자신을 호출하는 조합 문제를 해결하는 데 사용되는 방법입니다. 알고리즘 단계에는 기준 조건(선택할 요소 수가 0인 경우 빈 세트 반환)과 재귀 단계(가능한 모든 조합을 나열하고 현재 요소를 추가)가 포함됩니다. 실제 사례에서는 설정된 숫자에서 3개의 숫자를 선택하여 세 자리 숫자를 형성하는 가능한 모든 조합을 해결하기 위해 재귀 함수를 사용합니다.

C++ 함수 재귀 자세한 설명: 재귀적 해결 조합 문제

소개

재귀는 함수가 자신을 호출하는 프로세스이며 다양한 문제를 해결하는 데 사용할 수 있습니다. 이 글에서는 재귀를 사용하여 조합 문제를 해결하는 기술을 살펴보겠습니다.

조합 문제

조합 문제는 요소의 순서에 관계없이 요소 집합에서 특정 수의 요소를 선택하는 것을 말합니다. 예를 들어, 세트에서 3개의 문자를 선택하여 단어를 만듭니다.

재귀 알고리즘

재귀 함수를 사용하여 조합 문제를 해결할 수 있습니다. 이 함수는 두 개의 매개변수를 허용합니다:

• 요소 집합
• 선택할 요소 수

알고리즘 단계:

1. 기본 조건: 선택할 요소 수가 0이면 빈 집합 반환됩니다(즉, 요소가 없는 집합).

2. 재귀 단계:

   • 요소 세트에서 모든 요소를 ​​제거합니다.
   • 나머지 요소 집합에 대해 함수를 재귀적으로 호출하고 선택할 요소 수를 1씩 줄입니다.
   • 재귀 호출 결과에 현재 요소를 추가합니다.

실용 사례:

재귀 함수를 사용하여 실제 문제를 해결해 보겠습니다.

문제: 숫자 집합에서 3개의 숫자를 선택하여 세 자리 숫자를 만들고 가능한 모든 조합을 찾아보세요. .

해결책:

#include <iostream>
#include <vector>

using namespace std;

void findCombinations(vector<int> numbers, int n, int k) {
    if (k == 0) {
        for (int i : numbers) {
            cout << i;
        }
        cout << endl;
    } else {
        for (int i = 0; i < n; i++) {
            numbers.push_back(i);
            findCombinations(numbers, n, k - 1);
            numbers.pop_back();
        }
    }
}

int main() {
    int n; // 元素数量
    int k; // 需要选择的元素数量
    cin >> n >> k;

    vector<int> numbers;
    findCombinations(numbers, n, k);

    return 0;
}

프로그램 설명:

• 선택할 요소 수와 요소 수를 입력하세요.
• 조합을 저장하려면 빈 컬렉션을 초기화하세요.
• 가능한 모든 조합을 열거하고 결과를 출력하는 재귀 함수 findCombinations를 호출합니다.

실행 예:

입력:

5 3

출력:

012
013
014
023
024
034
123
124
134
234

위 내용은 C++ 함수 재귀에 대한 자세한 설명: 조합 문제를 재귀적으로 해결의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!