5

与えられた数を素数の部分として表現できる方法の数を出力する必要があります。

明確にさせてください: 仮に私がこの数 7 を与えられたとしましょう. さて, まず第一に, 7 より小さい素数をすべて見つけなければなりません. 2, 3, 5 です.これらの数字を要約して (1 つの数字を何度でも使用できます)、結果が 7 になるようにしますか? たとえば、番号 7 には 5 つの方法があります。

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

私はこの仕事で完全に迷っています。最初に、使用可能な要素の配列を次のように作成することを考えました: { 2, 2, 2, 3, 3, 5 } (7/2 = 3 なので、2 は 3 回出現する必要があります。3 も同様で、2 になります。発生）。その後、配列をループして、配列内の距離を決定する「リーダー」を選択します。説明がひどいことはわかっているので、コードは次のとおりです。

#include <iostream>
#include <vector>

int primes_all[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

int main()
{
    int number;
    std::cin >> number;

    std::vector<int> primes_used;

    for(int i = 0; i < 25; i++) {
        if(primes_all[i] < number && number-primes_all[i] > 1) {
            for(int k = 0; k < number/primes_all[i]; k++)
                primes_used.push_back(primes_all[i]);
        }
        else break;
    }

    int result = 0;

    for(size_t i = 0; i < primes_used.size(); i++) {
        int j = primes_used.size()-1;
        int new_num = number - primes_used[i];

        while(new_num > 1 && j > -1)
        {
            if(j > -1) while(primes_used[j] > new_num && j > 0) j--;

            if(j != i && j > -1) {
                new_num -= primes_used[j];

                std::cout << primes_used[i] << " " << primes_used[j] << " " << new_num << std::endl;
            }

            j--;
        }

        if(new_num == 0) result++;
    }

    std::cout << result << std::endl;

    system("pause");
    return 0;
}

これは単に機能しません。単にその背後にある考え方が間違っているからです。制限に関する詳細は次のとおりです。

  • 制限時間：1秒
  • メモリ制限: 128 MB

また、指定できる最大数は 100 です。そのため、100 未満の素数の配列を作成しました。指定された数が大きくなるにつれて、結果は非常に速く成長し、後で BigInteger クラスが必要になりますが、それは問題ではありません。 .

いくつかの結果が知られています:

Input    Result

7        5
20       732
80       10343662267187

そう...何かアイデアはありますか？これは組み合わせの問題ですか？コードは必要ありません。単なるアイデアです。私はまだC++の初心者ですが、管理します

3 + 2 + 2 は 2 + 3 + 2 とは異なることに注意してください。また、指定された数自体が素数である場合はカウントされません。たとえば、指定された数値が 7 の場合、次の合計のみが有効です。

2 + 2 + 3
2 + 3 + 2
2 + 5
3 + 2 + 2
5 + 2
7 <= excluded
4

3 に答える 3

9

ここでは動的計画法があなたの友達です。

27という数字を考えてみましょう。

7 には 5 つの結果があり、20 には 732 の結果がある場合、27 には少なくとも (732 * 5) の結果があることがわかります。事前に計算された値を使用して、2 変数システム (1 + 26、2 + 25 ... など) を使用できます。25 または 26 を再計算する必要はありません。

于 2013-01-08T15:55:50.893 に答える
3

あなたが探している概念は、数の「素分割」です。数値の S パーティションは、ターゲットに到達するために数値を追加する方法です。たとえば、1+1+2+3 は 7 の分割です。すべての加数が素数の場合、その分割は素数分割です。

あなたの例は間違っていると思います。数字 7 は通常、2+2+3、2+5、および 7 の 3 つの素数分割を持つと見なされます。加数の順序は関係ありません。数論では、素数分割を数える関数はカッパなので、カッパ(7) = 3 と言えます。

カッパの通常の計算は 2 つの部分で行われます。最初の部分は、数値の素因数の合計を計算する関数です。たとえば、42=2·3·7 の場合、sopf(42)=12 となります。sopf(12)=5 であることに注意してください。これは、合計が数値の個別の因数のみを対象としているためです。したがって、12=2·2·3 であっても、合計の計算には 1 つの 2 しか含まれていません。

sopf を考えると、カッパを計算するための長い式があります。ここに入力する方法がわからないので、LaTeX 形式で与えます: \kappa(n) = \frac{1}{n}\left(\mathrm{sopf}(n) + \sum_{ j=1}^{n-1} \mathrm{sopf}(j) \cdot \kappa(nj)\right)。

カウントだけでなく、実際にパーティションのリストが必要な場合は、@corsiKa が指摘した動的プログラミング ソリューションがあります。

プライム パーティションについては、カウントとリストの両方を生成するソース コードを含め、私のブログで詳しく説明しています。

于 2013-01-08T16:07:09.820 に答える
0

これは、corsiKaが提案するような動的計画法を使用するが、彼が説明するアルゴリズムを使用しない効率的な実装です。

簡単に言うと、が個別のパス（存在する場合はシングルステップパスを含む）をn介して到達可能であり、素数である場合、へのすべてのパスに追加することによってへのパスを構築します。そのようなすべてを考慮すると、への有効なパスの完全なリストが作成されます。したがって、検出されたパスの数を合計するだけです。kpkn+ppnn < NN

#include <iostream>

int primes_all[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

const int N_max = 85;
typedef long long ways;
ways ways_to_reach_N[N_max + 1] = { 1 };

int main()
{
    // find all paths
    for( int i = 0; i <= N_max; ++i ) {
        ways ways_to_reach_i = ways_to_reach_N[i];

        if (ways_to_reach_i) {
            for( int* p = primes_all; *p <= N_max - i && p < (&primes_all)[1]; ++p ) {
                ways_to_reach_N[i + *p] += ways_to_reach_i;
            }
        }
    }

    // eliminate single-step paths
    for( int* p = primes_all; *p <= N_max && p < (&primes_all)[1]; ++p ) {
        --ways_to_reach_N[*p];
    }

    // print results
    for( int i = 1; i <= N_max; ++i ) {
        ways ways_to_reach_i = ways_to_reach_N[i];

        if (ways_to_reach_i) {
            std::cout << i << " -- " << ways_to_reach_i << std::endl;
        }
    }

    return 0;
}

typedefwaysを大きな整数型に置き換えることは、読者の練習問題として残されています。

于 2013-03-11T06:16:41.200 に答える