Número de combinaciones (N elige R) en C ++

Aquí trato de escribir un progtwig en C ++ para encontrar NCR. Pero tengo un problema en el resultado. No es correcto. ¿Puedes ayudarme a encontrar el error en el progtwig?

#include  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(nr); }; int main(){ int n; //cout<>n; int r; //cout<>r; int result=NCR(n,r); cout<<result; return 0; } 

Su fórmula es totalmente incorrecta, se supone que es un fact(n)/fact(r)/fact(nr) , pero a su vez es una forma muy ineficiente de calcularlo.

Consulte Cálculo rápido del número de combinaciones de varias categorías y especialmente mis comentarios sobre esa pregunta. (Ah, y vuelve a abrir esa pregunta también para que pueda responderla correctamente)

El caso de división simple es realmente muy fácil de manejar:

 unsigned nChoosek( unsigned n, unsigned k ) { if (k > n) return 0; if (k * 2 > n) k = nk; if (k == 0) return 1; int result = n; for( int i = 2; i <= k; ++i ) { result *= (n-i+1); result /= i; } return result; } 

Demostración: http://ideone.com/aDJXNO

Si el resultado no encaja, puede calcular la sum de los logaritmos y obtener el número de combinaciones de forma inexacta como un doble. O use una biblioteca entera de precisión arbitraria.


Estoy poniendo mi solución en la otra pregunta estrechamente relacionada aquí, porque ideone.com ha estado perdiendo fragmentos de código últimamente, y la otra pregunta todavía está cerrada para nuevas respuestas.

 #include  #include  std::vector< std::pair > factor_table; void fill_sieve( int n ) { factor_table.resize(n+1); for( int i = 1; i <= n; ++i ) factor_table[i] = std::pair(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(j, i); ++i; ij += j; } } } } std::vector powers; template void factor( int num ) { while (num != 1) { powers[factor_table[num].first] += dir; num = factor_table[num].second; } } template 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  #include  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"; } 

Una buena forma de implementar n-choose-k es basarlo no en factorial, sino en una función de “aumento de producto” que está estrechamente relacionada con el factorial.

El rising_product (m, n) se multiplica m * (m + 1) * (m + 2) * … * n, con reglas para manejar varios casos de esquina, como n> = m, o n <= 1:

Vea aquí una implementación nCk así como nPk como funciones intrínsecas en un lenguaje de progtwigción interpretado escrito en C:

 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); } 

Este código no utiliza operadores como + y < porque es de tipo genérico (el tipo val representa un valor de cualquier tipo, como varios tipos de números, incluidos los enteros "bignum") y porque está escrito en C (sin sobrecarga) , y porque es la base de un lenguaje tipo Lisp que no tiene syntax infija.

A pesar de eso, esta implementación de n-choose-k tiene una estructura simple que es fácil de seguir.

Leyenda: le : menor que o igual; ge : mayor que o igual; trunc : división truncada; plus : addition, mul : multiplication, one : una val typed constant para el número uno.

La definición de N elige R es:

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

El numerador es el producto de elementos R, comenzando desde N con -1 incremento.

El denominador es el producto de elementos R, comenzando desde 1 con 1 incremento.

Todo lo que necesita es calcular estos dos productos y dividir uno con el otro. Sin embargo, en el código es posible que no desee calcular los dos productos en caso de que lleguen a ser demasiado grandes y se desborden. En cambio, para calcular 5, elija 3 que es (5 * 4 * 3) / (1 * 2 * 3), que desea hacer (5/1 * 4/2 * 3/3). Esto también garantiza que en cada paso los resultados sean divisibles (para n números continuos, uno de ellos debe ser divisible por n, así que es el producto de estos números).

El código C ++ se da a continuación. Algunos ahorradores de cómputo se usan al principio usando propiedades que N eligen R es igual a N eligen (NR)

 int NCR(int n, int r) { if (r == 0) return 1; if (r > n / 2) return NCR(n, n - r); // save some computation long res = 1; for (int k = 1; k <= r; ++k) { res *= n - k + 1; res /= k; } return res; } 

la línea

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

debiera ser

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

o incluso

 else return fact(n)/(fact(r)*fact(nr)); 

Use double lugar de int .

ACTUALIZAR:

Tu fórmula también es incorrecta. Debe usar fact(n)/fact(r)/fact(nr)

esto es como referencia para no exceder el límite de tiempo mientras se resuelve nCr en la progtwigción competitiva, estoy publicando esto, ya que será útil para ti ya que tienes respuesta para tu pregunta, obtener la factorización prima del coeficiente binomial es probablemente la más forma eficiente de calcularlo, especialmente si la multiplicación es costosa. Esto es ciertamente cierto del problema relacionado de calcular factorial (consulte Haga clic aquí para ver un ejemplo).

Aquí hay un algoritmo simple basado en el Tamiz de Eratóstenes que calcula la factorización prima. La idea es básicamente ir a través de los números primos cuando los encuentres usando el tamiz, pero luego también calcular cuántos de sus múltiplos caen en los rangos [1, k] y [n-k + 1, n]. El tamiz es esencialmente un algoritmo O (n \ log \ log n), pero no hay multiplicación. El número real de multiplicaciones necesarias una vez que se encuentra la factorización prima es, en el peor de los casos, O \ left (\ frac {n \ log \ log n} {\ log n} \ right) y probablemente haya formas más rápidas que eso.

 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