19

ここでは、C++ でプログラムを作成して NCR を見つけようとします。しかし、結果に問題があります。それは正しくありません。プログラムの間違いを見つけるのを手伝ってくれませんか?

#include <iostream>
using namespace std;
int fact(int n){
    if(n==0) return 1;
    if (n>0) return n*fact(n-1);
};

int NCR(int n,int r){
    if(n==r) return 1;
    if (r==0&&n!=0) return 1;
    else return (n*fact(n-1))/fact(n-1)*fact(n-r);
};

int main(){
    int n;  //cout<<"Enter A Digit for n";
    cin>>n;
    int r;
         //cout<<"Enter A Digit for r";
    cin>>r;
    int result=NCR(n,r);
    cout<<result;
    return 0;
}
4

8 に答える 8

36

あなたの式は完全に間違ってfact(n)/fact(r)/fact(n-r)います.

マルチカテゴリ数の組み合わせの高速計算と、特にその質問に対する私のコメントを参照してください。（ああ、またその質問を再開してください。私が適切に答えることができます）

単一分割の場合は、実際には非常に扱いやすいです。

unsigned nChoosek( unsigned n, unsigned k )
{
    if (k > n) return 0;
    if (k * 2 > n) k = n-k;
    if (k == 0) return 1;

    int result = n;
    for( int i = 2; i <= k; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}

デモ: http://ideone.com/aDJXNO

結果が適合しない場合は、対数の合計を計算し、組み合わせの数を double として不正確に取得できます。または、任意精度の整数ライブラリを使用してください。

ideone.com は最近コード スニペットを失っており、もう 1 つの質問はまだ新しい回答が得られていないため、密接に関連するもう 1 つの質問に私の解決策を示します。

#include <utility>
#include <vector>

std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
    factor_table.resize(n+1);
    for( int i = 1; i <= n; ++i )
        factor_table[i] = std::pair<int, int>(i, 1);
    for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
        if (factor_table[j].second == 1) {
            int i = j;
            int ij = j2;
            while (ij <= n) {
                factor_table[ij] = std::pair<int, int>(j, i);
                ++i;
                ij += j;
            }
        }
    }
}

std::vector<unsigned> powers;

template<int dir>
void factor( int num )
{
    while (num != 1) {
        powers[factor_table[num].first] += dir;
        num = factor_table[num].second;
    }
}

template<unsigned N>
void calc_combinations(unsigned (&bin_sizes)[N])
{
    using std::swap;

    powers.resize(0);
    if (N < 2) return;

    unsigned& largest = bin_sizes[0];
    size_t sum = largest;
    for( int bin = 1; bin < N; ++bin ) {
        unsigned& this_bin = bin_sizes[bin];
        sum += this_bin;
        if (this_bin > largest) swap(this_bin, largest);
    }
    fill_sieve(sum);

    powers.resize(sum+1);
    for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
    for( unsigned bin = 1; bin < N; ++bin )
        for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
}

#include <iostream>
#include <cmath>
int main(void)
{
    unsigned bin_sizes[] = { 8, 1, 18, 19, 10, 10, 7, 18, 7, 2, 16, 8, 5, 8, 2, 3, 19, 19, 12, 1, 5, 7, 16, 0, 1, 3, 13, 15, 13, 9, 11, 6, 15, 4, 14, 4, 7, 13, 16, 2, 19, 16, 10, 9, 9, 6, 10, 10, 16, 16 };
    calc_combinations(bin_sizes);
    char* sep = "";
    for( unsigned i = 0; i < powers.size(); ++i ) {
        if (powers[i]) {
            std::cout << sep << i;
            sep = " * ";
            if (powers[i] > 1)
                std::cout << "**" << powers[i];
        }
    }
    std::cout << "\n\n";
}
于 2012-02-17T15:37:46.480 に答える
12

N choose R の定義は、2 つの積を計算し、一方を他方で割ることです。

(N * N-1 * N-2 * ... * N-R+1) / (1 * 2 * 3 * ... * R)

ただし、乗算はすぐに大きくなりすぎて、既存のデータ型をオーバーフローする可能性があります。実装の秘訣は、乗算と除算を次のように並べ替えることです。

(N)/1 * (N-1)/2 * (N-2)/3 * ... * (N-R+1)/R

各ステップで、結果が割り切れることが保証されています (n 個の連続する数値の場合、そのうちの 1 つが n で割り切れる必要があり、これらの数値の積もそうです)。

たとえば、N の場合は 3 を選択し、N、N-1、N-2 の少なくとも 1 つが 3 の倍数になり、N の場合は 4 を選択し、N、N-1、N-2、N の少なくとも 1 つになります。 -3 は 4 の倍数になります。

以下に示す C++ コード。

int NCR(int n, int r)
{
    if (r == 0) return 1;

    /*
     Extra computation saving for large R,
     using property:
     N choose R = N choose (N-R)
    */
    if (r > n / 2) return NCR(n, n - r); 

    long res = 1; 

    for (int k = 1; k <= r; ++k)
    {
        res *= n - k + 1;
        res /= k;
    }

    return res;
}
于 2017-02-16T22:32:40.023 に答える
3

n-choose-k を実装する良い方法は、階乗ではなく、階乗に密接に関連する「上昇積」関数に基づくことです。

raise_product(m, n) は、m * (m + 1) * (m + 2) * ... * n を乗算し、n >= m、または n <= 1 などのさまざまなコーナー ケースを処理するためのルールを使用します。

C で記述されたインタープリター型プログラミング言語の組み込み関数としての nCk および nPk の実装については、こちらを参照してください。

static val rising_product(val m, val n)
{
  val acc;

  if (lt(n, one))
    return one;

  if (ge(m, n))
    return one;

  if (lt(m, one))
    m = one;

  acc = m;

  m = plus(m, one);

  while (le(m, n)) {
    acc = mul(acc, m);
    m = plus(m, one);
  }

  return acc;
}

val n_choose_k(val n, val k)
{
  val top = rising_product(plus(minus(n, k), one), n);
  val bottom = rising_product(one, k);
  return trunc(top, bottom);
}

val n_perm_k(val n, val k)
{
  return rising_product(plus(minus(n, k), one), n);
}

+このコードではandのような演算子を使用していません。これ<はジェネリック型 (型valは "bignum" 整数を含むさまざまな種類の数値など、あらゆる種類の値を表す) であり、C で記述されている (オーバーロードなし) ためです。これは、中置構文を持たない Lisp に似た言語の基礎です。

それにもかかわらず、この n-choose-k 実装は、簡単に理解できるシンプルな構造を持っています。

凡例: le: 以下。ge: 以上; trunc: 切り捨て除算; plus: 加算、mul: 乗算、one:val数値 1 の型付き定数。

于 2014-05-29T18:54:30.887 に答える
1

doubleの代わりに使用しintます。

アップデート：

あなたの式も間違っています。使用する必要がありますfact(n)/fact(r)/fact(n-r)

于 2012-02-17T15:31:08.730 に答える
1

この線

else return (n*fact(n-1))/fact(n-1)*fact(n-r);

する必要があります

else return (n*fact(n-1))/(fact(r)*fact(n-r));

あるいは

else return fact(n)/(fact(r)*fact(n-r));
于 2012-02-17T15:38:13.263 に答える
-1

これは、競争力のあるプログラミングでnCrを解決しているときに制限時間を超えないようにするための参考用です.あなたの質問に対する回答がすでに得られているので、これを投稿します.二項係数の素因数分解はおそらく最も特に乗算が高価な場合、それを計算する効率的な方法。これは、階乗の計算に関連する問題にも当てはまります (たとえば、ここをクリックしてください)。

これは、素因数分解を計算するエラトステネスのふるいに基づく単純なアルゴリズムです。基本的には、ふるいを使用して見つけた素数を調べるだけでなく、[1, k] と [n-k+1,n] の範囲に含まれる倍数の数も計算します。Sieve は本質的に O(n \log \log n) アルゴリズムですが、乗算は行われません。素因数分解が見つかった後に必要な実際の乗算回数は、最悪でも O\left(\frac{n \log \log n}{\log n}\right) であり、おそらくそれよりも高速な方法があります。

prime_factors = []

n = 20
k = 10

composite = [True] * 2 + [False] * n

for p in xrange(n + 1):
if composite[p]:
    continue

q = p
m = 1
total_prime_power = 0
prime_power = [0] * (n + 1)

while True:

    prime_power[q] = prime_power[m] + 1
    r = q

    if q <= k:
        total_prime_power -= prime_power[q]

    if q > n - k:
        total_prime_power += prime_power[q]

    m += 1
    q += p

    if q > n:
        break

    composite[q] = True

prime_factors.append([p, total_prime_power])

 print prime_factors
于 2015-03-06T16:50:49.087 に答える