3

サイズmとn：の2つの配列があるとします。

a[1] a[2] a[3] ..... a[m]

と

b[1] b[2] b[3] ..... b[n]

m + nこれらの2つの配列をマージして、要素の新しい配列で常に前に配置され、常に前に配置されるように、新しい配列を作成したいa[i]とa[i + 1]思いb[i]ますb[i + 1]。たとえば、a[1] a[2] b[1] b[2]... b[n] a[m]は有効な配列になりますが、そうでa[2] a[1] b[1] b[2] ... b[n] a[m]はありません。mとを与えられnた場合、繰り返しが許可されている場合、そのような組み合わせはいくつ可能になりますか？

私には問題を解決する直感があります：

- b[1] - b[2] - b[3] - ..... - b[n]

配列内のa[1]どの場所にも配置できますが、前と最後の場所を考えると、全体的な配置方法があります。そもそも（直前に）配置すれば、配置できるようになります。しかし、直後に配置すると、配置する方法があります。このアプローチは、すべての場所に再帰的に適用できます。しかし、繰り返しが許されている場合のアプローチ方法がわからない以外に、解を表す数式が見つかりません。n - 1bn + 1a[1]a[1]b[1]a[2]n + 1a[1]b[1]na[2]a[i]1 <=i <= n

4

2 に答える 2

3

この問題について考える1つの方法は、次のとおりです。要素を順番にリストするのではなく、各時点で、最初の未使用のAと最初の未使用のBのどちらを選択するかを選択することを検討できます。ピックA」と「ピックB」は、これらのシーケンスを生成するためのすべての可能な方法を生み出します。

すべての要素が異なると仮定すると、答えは、mAの後にnBが続くシーケンスを並べ替えることができるいくつかの方法によって与えられます。これはによって与えられます

   (m + n)!
 -----------
    m!  n!

ただし、重複する要素がいくつかある場合は、回答がありません。何か考えたら、必ずこの答えを更新します。

それまでの間、これがお役に立てば幸いです。

于 2013-01-11T05:07:15.577 に答える
1

あなたは星と棒の公式を探しています。配列Aの位置はビンです。各位置に、Aの対応する要素とBの任意の数の要素が挿入されます。（どの要素が選択されるかは、元の順序によってすでに決定されているため、区別できないものとして扱います。）Aに（n-1）個の要素（一方の端にビンを追加）があり、Bにk個の要素がある場合、式は次のようになります。二項係数

  n + k - 1  
(            )
      k

= ( (n+k-1)! / ( k! (n-1)! )
= (a.size() + b.size())! / (a.size()! * b.size()!)

これはtemplatetypedefの答えと同じです:)

実際にそのような大きな数の商を計算することは別の問題です。ほとんどの言語では、分子は通常整数のオーバーフローを生成します。C ++での1つの単純な戦略は、必ずしも最適ではありませんが、

unsigned long long gcd( unsigned long long &a, unsigned long long &b )
    { return b? gcd( b, a % b ) : a; }

std::vector< std::size_t > numerator( a.size() ); // factors of (a+b)!/b!
std::iota( numerator.begin(), numerator.end(), b.size()+1 );

for ( std::size_t afactor = 2; afactor != a.size()+1; ++ afactor ) {
    std::size_t reduced = afactor;
    for ( auto &&nfactor : numerator ) {
        auto common = gcd( afactor, nfactor );
        nfactor /= common;
        reduced /= common;
        if ( reduced == 1 ) goto next_afactor;
    }
    throw std::logic_error( "Fractional combinations" );
next_afactor: ;
}

return std::accumulate( numerator.begin(), numerator.end(), 1,
                        std::multiplies< std::size_t >() );
于 2013-01-11T05:10:44.710 に答える