6

重複の可能性:
素数部分としての数値

私はこの宿題を持っています。地獄のように大変で、与えられた数の個別の素数分割をすべて取得する必要があります。たとえば、番号 7 には 5 つの異なる主要なパーティション (または、2 つの主要なパーティションを表す 5 つの異なる方法) があります。

  • 5 + 2
  • 2 + 5
  • 3 + 2 + 2
  • 2 + 3 + 2
  • 2 + 2 + 3

ご覧のとおり、素数の場合、数値自体は除外されます。すべての個別のパーティションを印刷する必要はなく、それらの数だけを印刷する必要があります。

だから私はこれで少し迷っています。私はまったくコードを作成できませんでしたが、動的プログラミングのような観点からアプローチする必要があると思います。私はいくつかのヒントを求めているだけです。誰かがアイデアを持っていますか？前もって感謝します。

最大入力数は 100 です。また、プログラムの実行時間は 1 秒を超えることはできず、メモリ制限は 128 MB です。

4

4 に答える 4

2

これを解決するには、次の 3 つのアイデアを組み合わせる必要があります。

与えられた数が n だとします:

  • ここに示すように、n 未満のすべての素数を見つけます。

  • 素数配列と n からサブセットの合計を動的に計算します。こことここにいくつかのヒントがあります

  • 次に、手順 2 で取得した各回答の異なる順列の数を計算します。

もちろん、これは単なるヒントです。しかし、最終的なコードを作成するのに大いに役立つはずです。

于 2013-01-18T15:23:53.937 に答える
1

残念ながら、ここでブルートフォースをあまり改善することはできません。必ず行うべきことの 1 つは、エラトステネスのふるいを使用して、特定の数までのすべての素数を事前に計算することです。その後、数値 N を指定すると、最小の素数が素数のリストの各素数であるすべてのパーティションを再帰的に出力します (パーティションを繰り返さないように、最小のものにすることを忘れないでください)。

編集:パーティションの数だけを知る必要があることを知った後:最善の解決策は、動的プログラミングを使用することです。ここでも、2 次元の配列で memoize する必要があります。mem[MAX_SIZE][MAX_SIZE]最初のインデックスは解を計算する数値で、2 番目のインデックスはパーティションに使用する必要がある最小の素数のインデックスです。

于 2013-01-18T12:01:09.180 に答える
1

ウィキペディアのパーティションの数学、特にページの半分ほど下にある生成関数と制限付きパーティション生成関数のセクションを参照することをお勧めします。特定の被加数 (自然数の集合 T で指定) からなるパーティションの生成関数について言及しています。

数 n の順序に依存しない素数分割の数を R(n) とする。x について n 番目の偏微分を取り、x = 0 に設定することにより、母関数から R(n) を導き出すことができます。これは簡単ではないかもしれません。

1 つの注意点: これらのパーティションは順序に依存しません (つまり、1 + 2 と 2 + 1 は 1 つのパーティションとしてのみカウントされます)。

于 2013-01-18T12:56:44.697 に答える
1

したがって、答えではなくヒントの形で：

  • 他の場所で述べたように、素数を事前に計算できます。
  • より少ない数の結果を再利用できますか? では、5 の実際の順列を知っていると仮定すると、これは 7 の実際の順列を見つけるのに役立ちますか?
  • 結果に何らかの構造がありますか? もしそうなら、その構造を使用して計算の繰り返しを避けることができますか? たとえば、番号 7 に対して 5 つの順列を挙げていますが、これらは互いに類似性を示しています。これは一般的な傾向ですか?それは何ですか?
  • 内部構造を見つけ、より小さな結果を使用してより大きな結果を見つけることができると仮定すると、両方を行うことができます-完全な中間結果を保存することを完全に回避できますか?
  • 最後に、順序付けされた各組み合わせをリストする必要がありますか、それとも順序付けられた組み合わせの数を返すだけですか? ここで計算を保存できる場合があります。
于 2013-01-18T12:18:27.133 に答える