Количество комбинаций (N выберите R) в C ++ - PullRequest
Новая
       21

Количество комбинаций (N выберите R) в C ++

9 голосов
/ 17 февраля 2012

Здесь я пытаюсь написать программу на 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;
}

Ответы [ 7 ]

25 голосов
/ 17 февраля 2012

Ваша формула полностью неверна, она должна быть 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

Если результат не подходит, вы можете рассчитать сумму логарифмов и получить число комбинаций неточно как двойное число.Или используйте целочисленную библиотеку произвольной точности.

Я ставлю здесь решение другого, тесно связанного с этим вопроса, потому что ideone.com в последнее время теряет фрагменты кода, а другой вопрос все еще остается.закрыто для новых ответов. 

#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";
}
4 голосов
/ 17 февраля 2017

Определение N выбрать R состоит в том, чтобы вычислить два произведения и разделить одно на другое,

(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 непрерывных чисел одно из них должно делиться на n, как и произведение этих чисел).

Например, для N выберите 3, по крайней мере, один из N, N-1, N-2 будет кратным 3, а для N выберите 4, по крайней мере, один из N, N-1, N- 2, N-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;
}
3 голосов
/ 29 мая 2014

Хороший способ реализовать n-choose-k состоит в том, чтобы основывать его не на факториале, а на функции «растущего продукта», тесно связанной с факториалом.

Повышение_продукта (m, n)умножает вместе m * (m + 1) * (m + 2) * ... * n, с правилами для обработки различных угловых случаев, таких как n> = m или n <= 1: </p>

См. здесь для реализации nCk, а также nPk как встроенных функций в интерпретируемом языке программирования, написанном на 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);
}

Этот код не использует операторы, такие как + и < потому что это тип generic (тип val представляет значение любого вида, например, различные виды чисел, включая целые числа "bignum"), и потому что оно написано на C (без перегрузки), и потому что оно является основой дляЛисп-подобный язык, у которого нет инфиксного синтаксиса.

Несмотря на это, эта реализация n-choose-k имеет простую структуру, которой легко следовать.

Легенда: le: меньше или равно;ge: больше или равно;trunc: усеченное деление;plus: сложение, mul: умножение, one: val набранная константа для числа один.

1 голос
/ 17 февраля 2012

линия 

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));
1 голос
/ 17 февраля 2012

Используйте double вместо int.

ОБНОВЛЕНИЕ:

Ваша формула также неверна.Вы должны использовать fact(n)/fact(r)/fact(n-r)

0 голосов
/ 31 декабря 2018

Рекурсивная функция здесь используется неправильно. fact() функция должна быть изменена на это: 

int fact(int n){
if(n==0||n==1) //factorial of both 0 and 1 is 1. Base case.
{
    return 1;
}else

    return (n*fact(n-1));//recursive call.

};

Рекурсивный вызов должен быть выполнен в else части.

NCR() функция должна быть изменена на это: 

int NCR(int n,int r){
    if(n==r) {
        return 1;
    } else if (r==0&&n!=0) {
        return 1;
    } else if(r==1)
    {
        return n;
    }
    else
    {
        return fact(n)/(fact(r)*fact(n-r));
    }
};
0 голосов
/ 06 марта 2015

это для справки, чтобы не превышать ограничение по времени при решении nCr в конкурентном программировании, я публикую это, поскольку это будет полезно для вас, поскольку вы уже получили ответ на свой вопрос, Получение простой факторизации биномиального коэффициента, вероятно, является наиболее эффективным способом его вычисления, особенно если умножение стоит дорого. Это, безусловно, относится к связанной с этим проблеме вычисления факториала (см., Например, Нажмите здесь ).

Вот простой алгоритм, основанный на сите Эратосфена, который вычисляет простую факторизацию. Идея в основном состоит в том, чтобы пройти через простые числа, как вы находите их, используя сито, а затем также рассчитать, сколько их кратных попадает в диапазоны [1, k] и [n-k + 1, n]. Сито по сути является алгоритмом 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
...