ホームページ >バックエンド開発 >C++ >C++ 関数の再帰の詳細な説明: 組み合わせの問題を再帰的に解決する

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

王林
王林オリジナル
2024-05-01 10:30:02941ブラウズ

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

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

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

はじめに

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

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

再帰アルゴリズム

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

#要素コレクション

    選択される要素の数
  • アルゴリズム ステップ:

ベースライン条件:
    選択される要素の数が 0 の場合、空のセット (つまり、要素を含まないセット) が返されます。
  1. 再帰的手順:
  2. 要素セットから要素を削除します。

      残りの要素セットに対して関数を再帰的に呼び出し、選択する要素の数を 1 つ減らします。
    • 現在の要素を再帰呼び出しの結果に追加します。
    # 実際的なケース:

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

問題:

一連の数字から 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;
}

プログラムの説明:

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

空のコレクションを初期化して組み合わせを保存します。
  • 再帰関数
  • findCombinations
  • を呼び出します。これは、考えられるすべての組み合わせを列挙し、結果を出力します。
  • 実行例:

入力:

5 3
出力:

012
013
014
023
024
034
123
124
134
234

以上がC++ 関数の再帰の詳細な説明: 組み合わせの問題を再帰的に解決するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。