4

面接の準備をしているときに、次の問題が見つかりました。

3は1+1 + 1、1 + 2、2+1と書くことができます。4は、1 + 1 + 1 + 1、1 + 1 + 2、2 + 2、1 + 2 + 1、2 + 1 + 1、3 + 1、1+3と書くことができます。整数が与えられた場合、可能な式はいくつ存在しますか？（1+2と2+1は異なります）

したがって、これは、それを計算し、それを実行するすべての数値のセットを取得するためのブルートフォースアルゴリズムを作成するのはかなり簡単です。

private static Set<List<Integer>> getIntegersSum(int num) {
  Set<List<Integer>> returnSet = new HashSet<List<Integer>>();

  if (num == 0) {
   returnSet.add(new LinkedList<Integer>());
   return returnSet;
  }

  for (int i = 1; i <= num; i++) {
    Set<List<Integer>> listNMinI = getIntegersSum(num - i);
    for (List<Integer> l : listNMinI) {
      l.add(0, i);
      returnSet.add(l);
    }
  }

  return returnSet;
}

このアルゴリズムの複雑さを表す漸化式は次のとおりです。

T(0) = \Theta (1)
T(n) = O(n) + \Sum_{i=0}^{n-1} T(i)

この漸化式から大きな複雑さに到達する方法がよくわかりません。また、質問に対する閉じた形の解があるかどうかも知りたいです（各番号に対してそのような組み合わせがいくつあるか）。

また、各呼び出しの結果をキャッシュしてこのアルゴリズムをメモ化した場合の複雑さもわかりません（フィボナッチを高速化する方法と同様）。

4

1 に答える 1

2

そのような表現は2n-1-1あります。

この問題に取り組む方法はいくつかあります。

私はこの問題の結果を使用します：

n個のキャンディーがあります。n個のキャンディーすべてをk人に分割する方法はいくつありますか（0個のキャンディーを与えることができます）？

部分は別の人に行くので、順序は重要です。解は（n + k-1）C（k-1）です。ミックスにk-1個のセパレーターを追加し（合計をn + k-1にします）、キャンディーをk個の部分に分離するためにセパレーターを挿入する方法の数を見つけようとします。キャンディーとセパレーターを配置するためにn+k-1のボックスを一列に並べると考えてください。ボックスをkの部分に分割する、セパレーター用のk-1スロットを選択する方法をいくつか見つけたいと思います。

この問題に戻ると、このサブ問題に答える必要があります。

nをk個の正の数の合計として表現する方法はいくつありますか？

上記のキャンディ分割問題の結果を再利用できますが、項が0になるのを防ぐためにkを予約する必要があります。したがって、結果は（（n --k）+ k --1）C（k -1）になります。 （n-1）C（k-1）に簡略化します。（（n --k）は、k個の項ごとにkを片付けるためです）。

したがって、式には少なくとも2つの項、最大でnの項が含まれるため、最終結果はSum [i = 2..n]（n --1）C（i -1）になります。Sum [i = 1..n]（n-1）C（i-1）= 2 n-1であることがわかっているので、Sum [i = 2..n]（n-1）C（i-1） = 2n-1-1。

この問題に取り組む別の方法は、コメントの@MarkDickinsonによって説明されています。推論はもっと簡単です。

キャンディーの各ペアの間に、セパレーターがあるか、ないかのどちらかです。それはすぐに2^(n-1)可能性を与えます。何らかの理由で、OPは、部分が1つしかない単一のケースを除外しているため、1を引くと2^(n-1) - 1。

議論をより強固にするために。問題は正の項しか許可しないため、キャンディーの間に挿入できるセパレーターは1つだけであり、キャンディーの間に挿入できるのは2つの端ではなくキャンディーの間にのみです。したがって、セパレータが表示される場所は（n-1）個あります。

于 2012-12-22T17:29:02.030 に答える