0

数X=A1 * A2 * ... * Anとすると、A1、A2、..、AnはXの因数です。一度に2を括弧で囲むこれらのN個の因数をいくつの方法で配置できますか？

Xに5つの要素があるとします。g、h、j、k式ghjkは5つの方法で評価できます。つまり（（（gh）j）k）、（g（h（jk）））、（g（（hj）k） ）、（（g（hj））k）および（（gh）（jk））

したがって、ghjkとして入力する場合

出力は5である必要があります

C / C ++でこれを行うにはどうすればよいですか？

与えられた1<N<34。。

4

3 に答える 3

0

「Xにはg、h、j、k、iの5つの要素がある」という意味だったと思いますが、上記のXには4つの要素しか入れていません。5 つのセットで 2 つの要素の組み合わせを探しているようです。

これは単純な S の組み合わせではないでしょうか。繰り返しなしで K を選択します。

ん！/ k!(ンク)!

ここで、n はセット内の要素の数、k は k-combination です。

あなたにとって、それは 5 つのセットのうち 2 つのサブセットになります: (n = 5, k = 2)

5！/ 2!*(5-2)! = 5! / (2! * 3!) = 10

(g,h)、(g,j)、(g,k)、(g,i)

(h,j)、(h,k)、(h,i)

(j、k)、(j、i)

(k,i)

したがって、5 つのセットの 2 つの要素の可能な組み合わせは、実際には 10 通りあります。

于 2013-03-18T17:47:10.490 に答える
0

因数の順序を変更せずに、因数の積をn括弧で囲むことができC(n-1)ます。C(k)k

C(k) = 1/(k+1) * \binom(2*k, k)
     = 1/(k+1) * (2k)!/(k!)²

因子の積を (完全に) 括弧で囲むことは、葉nを持つ二分木を構築することと同等であるため、n葉を持つ二分木のさまざまな構造の数でもありnます。

因子の順序の変更が許可されている場合は、因子の異なる順序の数を乗算する必要があります。これは単純n!に、繰り返し因子がない場合です。

n!/(a_1! * ... * a_k!)

kそれぞれ多重度を持つ別個の因子がある場合a_i。

于 2013-03-18T17:49:24.227 に答える
0

あなたの問題はカタロニア語の数字を使用しています: Cn は、連想式を括弧で囲む方法の数です。これは、n+1 個の葉を持つ可能な完全二分木の数でもあります (完全二分木 = 各ノードが正確に 2 つの子を持つ木、または葉です)。

したがって、再帰を使用してすべての組み合わせを生成できます。

#include <iostream>
#include <string>
#include <vector>

typedef std::vector<std::string> str_vector;

// Combine u and v, and add the result to w
// u and v contains all possible combinations with respectively m and n - m letters
// So w will contain combinations with n letters
void combine(str_vector& w, const str_vector& u, const str_vector& v)
{
    for(unsigned int t = 0; t < u.size(); t++)
        for(unsigned int i = 0; i < v.size(); i++)
            w.push_back("(" + u[t] + v[i] + ")");
}

// The function resolving our problem
// It output an array containing all possible combinations
// with n letters, starting with startLetter
str_vector problem(unsigned int n, char startLetter)
{
    if(n == 1)
        // Only one combination with one letter.
        // Array with 1 string which contains only one character
        return str_vector(1,std::string(1,startLetter));
    else
    {
        str_vector w;
        // Get all combinations for n-1 letters, and add them to w
        for(unsigned int t = 1; t < n; t++)
            combine(w, problem(t, startLetter), problem(n - t, startLetter + (char)t));
        return w;
    }
}

int main()
{
    // Get all possible combinations with 4 letters
    const str_vector& r = problem(4,'a');

    // Print all solutions
    for(unsigned int t = 0; t < r.size(); t++)
        std::cout << r[t] << "\n";
}

このコードは、最速でも最適化されたものでもありません。でも、とても読みやすいと思います。

組み合わせの数については、式は次のとおりです。

カタロニア番号

これは次のように簡略化できます。

       (2n)!
Cn = ---------
     n!² (n+1)

Cn を計算すると、n+1 個の識別子を持つ組み合わせの数が得られます。ただし、解決策は提供されません。

于 2013-03-18T17:49:56.617 に答える