C++ 関数の再帰の詳細な説明: 組み合わせの問題を再帰的に解決する-C++-php.cn

C++ 関数の再帰の詳細な説明: 組み合わせの問題を再帰的に解決する

王林

リリース： 2024-05-01 10:30:02

オリジナル

931 人が閲覧しました

再帰は、関数がそれ自体を呼び出す組み合わせ問題を解決するために使用されるメソッドです。アルゴリズムのステップには、ベースライン条件 (選択される要素の数が 0 の場合に空のセットを返す) と再帰的ステップ (考えられるすべての組み合わせを列挙し、現在の要素を追加する) が含まれます。実際のケースでは、再帰関数を使用して、3 桁の数値を形成する数値セットから 3 つの数値を選択するすべての可能な組み合わせを解決します。

C++ 函数递归详解：递归求解组合问题

#C 関数の再帰の詳細な説明: 組み合わせの問題を再帰的に解決する

はじめに

再帰関数が自分自身を呼び出す処理であり、さまざまな問題を解決するために使用できます。この記事では、再帰を使用して組み合わせ問題を解決する手法を検討します。

組み合わせ問題 # 組み合わせ問題とは、要素の順序に関係なく、一連の要素から特定の数の要素を選択することを指します。たとえば、セットから 3 つの文字を選択して単語を形成します。

再帰アルゴリズム

再帰関数を使用して、組み合わせ問題を解決できます。この関数は 2 つのパラメータを受け入れます:

#要素コレクション

アルゴリズムステップ:

ベースライン条件:

要素セットから要素を削除します。
- 現在の要素を再帰呼び出しの結果に追加します。
# 実際的なケース:

実際の問題を解決するために再帰関数を使用してみましょう:

問題:

一連の数字から 3 つの数字を選択して 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;
}

ログイン後にコピー

プログラムの説明:

要素の数と対象の要素の数を入力してください。選ばれる。

空のコレクションを初期化して組み合わせを保存します。